گراف قویا همبند و برنامه تشخیص آن — راهنمای کاربردی

1// C++ program to check if a given directed graph is strongly  
2// connected or not 
3#include <iostream> 
4#include <list> 
5#include <stack> 
6using namespace std; 
7  
8class Graph 
9{ 
10    int V;    // No. of vertices 
11    list<int> *adj;    // An array of adjacency lists 
12  
13    // A recursive function to print DFS starting from v 
14    void DFSUtil(int v, bool visited[]); 
15public: 
16    // Constructor and Destructor 
17    Graph(int V) { this->V = V;  adj = new list<int>[V];} 
18    ~Graph() { delete [] adj; } 
19  
20    // Method to add an edge 
21    void addEdge(int v, int w); 
22  
23    // The main function that returns true if the graph is strongly 
24    // connected, otherwise false 
25    bool isSC(); 
26  
27    // Function that returns reverse (or transpose) of this graph 
28    Graph getTranspose(); 
29}; 
30  
31// A recursive function to print DFS starting from v 
32void Graph::DFSUtil(int v, bool visited[]) 
33{ 
34    // Mark the current node as visited and print it 
35    visited[v] = true; 
36  
37    // Recur for all the vertices adjacent to this vertex 
38    list<int>::iterator i; 
39    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
40        if (!visited[*i]) 
41            DFSUtil(*i, visited); 
42} 
43  
44// Function that returns reverse (or transpose) of this graph 
45Graph Graph::getTranspose() 
46{ 
47    Graph g(V); 
48    for (int v = 0; v < V; v++) 
49    { 
50        // Recur for all the vertices adjacent to this vertex 
51        list<int>::iterator i; 
52        for(i = adj[v].begin(); i != adj[v].end(); ++i) 
53        { 
54            g.adj[*i].push_back(v); 
55        } 
56    } 
57    return g; 
58} 
59  
60void Graph::addEdge(int v, int w) 
61{ 
62    adj[v].push_back(w); // Add w to v’s list. 
63} 
64  
65// The main function that returns true if graph is strongly connected 
66bool Graph::isSC() 
67{ 
68    // St1p 1: Mark all the vertices as not visited (For first DFS) 
69    bool visited[V]; 
70    for (int i = 0; i < V; i++) 
71        visited[i] = false; 
72  
73    // Step 2: Do DFS traversal starting from first vertex. 
74    DFSUtil(0, visited); 
75  
76     // If DFS traversal doesn’t visit all vertices, then return false. 
77    for (int i = 0; i < V; i++) 
78        if (visited[i] == false) 
79             return false; 
80  
81    // Step 3: Create a reversed graph 
82    Graph gr = getTranspose(); 
83  
84    // Step 4: Mark all the vertices as not visited (For second DFS) 
85    for(int i = 0; i < V; i++) 
86        visited[i] = false; 
87  
88    // Step 5: Do DFS for reversed graph starting from first vertex. 
89    // Staring Vertex must be same starting point of first DFS 
90    gr.DFSUtil(0, visited); 
91  
92    // If all vertices are not visited in second DFS, then 
93    // return false 
94    for (int i = 0; i < V; i++) 
95        if (visited[i] == false) 
96             return false; 
97  
98    return true; 
99} 
100  
101// Driver program to test above functions 
102int main() 
103{ 
104    // Create graphs given in the above diagrams 
105    Graph g1(5); 
106    g1.addEdge(0, 1); 
107    g1.addEdge(1, 2); 
108    g1.addEdge(2, 3); 
109    g1.addEdge(3, 0); 
110    g1.addEdge(2, 4); 
111    g1.addEdge(4, 2); 
112    g1.isSC()? cout << "Yes\n" : cout << "No\n"; 
113  
114    Graph g2(4); 
115    g2.addEdge(0, 1); 
116    g2.addEdge(1, 2); 
117    g2.addEdge(2, 3); 
118    g2.isSC()? cout << "Yes\n" : cout << "No\n"; 
119  
120    return 0; 
121}

1// Java program to check if a given directed graph is strongly 
2// connected or not 
3import java.io.*; 
4import java.util.*; 
5import java.util.LinkedList; 
6  
7// This class represents a directed graph using adjacency 
8// list representation 
9class Graph 
10{ 
11    private int V;   // No. of vertices 
12    private LinkedList<Integer> adj[]; //Adjacency List 
13  
14    //Constructor 
15    Graph(int v) 
16    { 
17        V = v; 
18        adj = new LinkedList[v]; 
19        for (int i=0; i<v; ++i) 
20            adj[i] = new LinkedList(); 
21    } 
22  
23    //Function to add an edge into the graph 
24    void addEdge(int v,int w) {  adj[v].add(w); } 
25  
26    // A recursive function to print DFS starting from v 
27    void DFSUtil(int v,Boolean visited[]) 
28    { 
29        // Mark the current node as visited and print it 
30        visited[v] = true; 
31  
32        int n; 
33  
34        // Recur for all the vertices adjacent to this vertex 
35        Iterator<Integer> i = adj[v].iterator(); 
36        while (i.hasNext()) 
37        { 
38            n = i.next(); 
39            if (!visited[n]) 
40                DFSUtil(n,visited); 
41        } 
42    } 
43  
44    // Function that returns transpose of this graph 
45    Graph getTranspose() 
46    { 
47        Graph g = new Graph(V); 
48        for (int v = 0; v < V; v++) 
49        { 
50            // Recur for all the vertices adjacent to this vertex 
51            Iterator<Integer> i = adj[v].listIterator(); 
52            while (i.hasNext()) 
53                g.adj[i.next()].add(v); 
54        } 
55        return g; 
56    } 
57  
58    // The main function that returns true if graph is strongly 
59    // connected 
60    Boolean isSC() 
61    { 
62        // Step 1: Mark all the vertices as not visited 
63        // (For first DFS) 
64        Boolean visited[] = new Boolean[V]; 
65        for (int i = 0; i < V; i++) 
66            visited[i] = false; 
67  
68        // Step 2: Do DFS traversal starting from first vertex. 
69        DFSUtil(0, visited); 
70  
71        // If DFS traversal doesn't visit all vertices, then 
72        // return false. 
73        for (int i = 0; i < V; i++) 
74            if (visited[i] == false) 
75                return false; 
76  
77        // Step 3: Create a reversed graph 
78        Graph gr = getTranspose(); 
79  
80        // Step 4: Mark all the vertices as not visited (For 
81        // second DFS) 
82        for (int i = 0; i < V; i++) 
83            visited[i] = false; 
84  
85        // Step 5: Do DFS for reversed graph starting from 
86        // first vertex. Staring Vertex must be same starting 
87        // point of first DFS 
88        gr.DFSUtil(0, visited); 
89  
90        // If all vertices are not visited in second DFS, then 
91        // return false 
92        for (int i = 0; i < V; i++) 
93            if (visited[i] == false) 
94                return false; 
95  
96        return true; 
97    } 
98  
99    public static void main(String args[]) 
100    { 
101        // Create graphs given in the above diagrams 
102        Graph g1 = new Graph(5); 
103        g1.addEdge(0, 1); 
104        g1.addEdge(1, 2); 
105        g1.addEdge(2, 3); 
106        g1.addEdge(3, 0); 
107        g1.addEdge(2, 4); 
108        g1.addEdge(4, 2); 
109        if (g1.isSC()) 
110            System.out.println("Yes"); 
111        else
112            System.out.println("No"); 
113  
114        Graph g2 = new Graph(4); 
115        g2.addEdge(0, 1); 
116        g2.addEdge(1, 2); 
117        g2.addEdge(2, 3); 
118        if (g2.isSC()) 
119            System.out.println("Yes"); 
120        else
121            System.out.println("No"); 
122    } 
123} 
124// This code is contributed by Aakash Hasija 

1# Python program to check if a given directed graph is strongly  
2# connected or not 
3  
4from collections import defaultdict 
5   
6#This class represents a directed graph using adjacency list representation 
7class Graph: 
8   
9    def __init__(self,vertices): 
10        self.V= vertices #No. of vertices 
11        self.graph = defaultdict(list) # default dictionary to store graph 
12   
13    # function to add an edge to graph 
14    def addEdge(self,u,v): 
15        self.graph[u].append(v) 
16      
17   
18    #A function used by isSC() to perform DFS 
19    def DFSUtil(self,v,visited): 
20  
21        # Mark the current node as visited  
22        visited[v]= True
23  
24        #Recur for all the vertices adjacent to this vertex 
25        for i in self.graph[v]: 
26            if visited[i]==False: 
27                self.DFSUtil(i,visited) 
28  
29  
30    # Function that returns reverse (or transpose) of this graph 
31    def getTranspose(self): 
32  
33        g = Graph(self.V) 
34  
35        # Recur for all the vertices adjacent to this vertex 
36        for i in self.graph: 
37            for j in self.graph[i]: 
38                g.addEdge(j,i) 
39          
40        return g 
41  
42          
43    # The main function that returns true if graph is strongly connected 
44    def isSC(self): 
45  
46        # Step 1: Mark all the vertices as not visited (For first DFS) 
47        visited =[False]*(self.V) 
48          
49        # Step 2: Do DFS traversal starting from first vertex. 
50        self.DFSUtil(0,visited) 
51  
52        # If DFS traversal doesnt visit all vertices, then return false 
53        if any(i == False for i in visited): 
54            return False
55  
56        # Step 3: Create a reversed graph 
57        gr = self.getTranspose() 
58          
59        # Step 4: Mark all the vertices as not visited (For second DFS) 
60        visited =[False]*(self.V) 
61  
62        # Step 5: Do DFS for reversed graph starting from first vertex. 
63        # Staring Vertex must be same starting point of first DFS 
64        gr.DFSUtil(0,visited) 
65  
66        # If all vertices are not visited in second DFS, then 
67        # return false 
68        if any(i == False for i in visited): 
69            return False
70  
71        return True
72  
73# Create a graph given in the above diagram 
74g1 = Graph(5) 
75g1.addEdge(0, 1) 
76g1.addEdge(1, 2) 
77g1.addEdge(2, 3) 
78g1.addEdge(3, 0) 
79g1.addEdge(2, 4) 
80g1.addEdge(4, 2) 
81print "Yes" if g1.isSC() else "No"
82  
83g2 = Graph(4) 
84g2.addEdge(0, 1) 
85g2.addEdge(1, 2) 
86g2.addEdge(2, 3) 
87print "Yes" if g2.isSC() else "No"
88  
89#This code is contributed by Neelam Yadav