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

۷۳۰ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۷ دقیقه
گراف قویا همبند و برنامه تشخیص آن — راهنمای کاربردی

در این مطلب، روش نوشتن برنامه‌ای که تشخیص می‌دهد یک گراف قویا همبند است یا خیر، مورد بررسی قرار گرفته است. همچنین، پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و «پایتون» (Python) انجام شده است. فرض می‌شود یک گراف جهت‌دار به عنوان ورودی به برنامه داده شده است. هدف آن است که برنامه بررسی و مشخص کند که آیا گراف قویا هم‌بند است یا خیر. یک گراف جهت‌دار، قویا هم‌بند است اگر مسیری بین هر دو جفت از راس‌های آن وجود داشته باشد. برای مثال، گرافی که در تصویر زیر آمده، قویا هم‌بند محسوب می‌شود.

997696

گراف قویا همبند و برنامه تشخیص آن -- به زبان ساده

انجام چنین کاری در گراف غیرجهت‌دار آسان است. در این راستا، کافی است که پیمایش «جستجوی اول سطح» (Breadth-First Search | BFS) و «جستجوی اول عمق» (Depth-First Search | DFS) با آغاز از هر راسی انجام شود. اگر در پیمایش BFS یا DFS، همه راس‌ها مشاهده شدند، گراف غیر جهت‌دار همبند است.

این رویکرد برای گراف‌های جهت‌دار پاسخگو نیست. برای مثال، گراف زیر قویا همبند نیست. اگر پیمایش DFS یا BFS با شروع از راس صفر انجام شود، می‌توان به همه راس‌ها رسید، اما اگر از هر راس دیگری آغاز شود، نمی‌توان به همه راس‌ها رسید.

گراف قویا همبند و برنامه تشخیص آن -- به زبان ساده

یک ایده ساده آن است که از همه الگوریتم‌های کوتاه‌ترین مسیرها مانند پیدا کردن «بستار تعدی» (Transitive Closure) گراف یا «الگوریتم فلوید-وارشال» (Floyd Warshall) استفاده شود. پیچیدگی زمانی این روش، از درجه (O(v3 است. همچنین، می‌توان DFS را به تعداد V مرتبه با آغاز از هر راسی انجام داد. اگر DFS همه راس‌ها را ملاقات نکرد، گراف قویا همبند نیست. این الگوریتم، ((O(V*(V+E زمان می‌برد که مشابه با بستار تعدی برای گراف چگال است.

یک ایده بهتر، استفاده از الگوریتم «اجزای قویاً هم‌بند» (Strongly Connected Components | SCC) است. می‌توان همه SCC‌ها را در زمان (O(V+E پیدا کرد. اگر تعداد SCC‌ها برابر با یک باشد، گراف قویا هم‌بند است. الگوریتم SCC پس از پیدا کردن همه SCC‌ها، دیگر کاری انجام نمی‌دهد. در ادامه، الگوریتم ساده و مبتنی بر DFS «کساراجو» (Kosaraju) ارائه شده است که دو پیمایش در گراف انجام و تشخیص می‌دهد که گراف قویا همبند است یا خیر. روش کار این الگوریتم، در ادامه بیان شده است.

  1. همه راس‌ها را با «ملاقات نشده» مقداردهی اولیه کن.
  2. پیمایش DFS گراف را با شروع از هر راس دلخواه v آغاز کن. اگر در پیمایش DFS همه راس‌ها ملاقات نشدند، false را بازگردان.
  3. همه یال‌ها را معکوس کن (یا ترانهاده یا معکوس گراف را پیدا کن)
  4. همه راس‌ها را در گراف معکوس شده با عنوان «ملاقات نشده» علامت‌گذاری کن.
  5. پیمایش DFS گراف معکوس را از همان راس v (که در گام ۲ از آن استفاده شد) آغاز کن. اگر پیمایش DFS همه راس‌ها را ملاقات نکرد، مقدار false را بازگردان. در غیر این صورت، مقدار true را بازگردان.

ایده آن است که اگر همه گره‌ها از راس v دسترسی‌پذیر باشند، و هر گره‌ای بتواند به v برسد، گراف قویا هم‌بند است. در گام ۲، بررسی می‌شود که همه راس‌ها از راس v دسترسی‌پذیر هستند. در گام ۴، بررسی می‌شود که آیا می‌توان از همه راس‌ها به راس v رسید (در گراف معکوس، اگر همه راس‌ها از راس v دسترسی‌پذیر باشند، همه راس‌ها می‌توانند در گراف اصلی به راس v برسند). پیاده‌سازی الگوریتم بالا، در ادامه در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

برنامه تشخیص گراف قویا همبند در ++C

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

خروجی قطعه کد بالا، به صورت زیر است.

Yes
No

پیچیدگی زمانی روش ارائه شده در بالا، برابر با «جستجوی اول عمق» است و اگر گراف با استفاده از ماتریس مجاورت ارائه شده باشد، از درجه (O(V+E خواهد بود.

این رویکرد نیازمند دو بار پیمایش گراف است. می‌توان با استفاده از «الگوریتم تارژان مؤلفه‌های قویا هم‌بند» (Tarjan's Strongly Connected Components Algorithm)، با یک بار پیمایش گراف این کار را انجام داد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
geeksforgeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *