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

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

در این مطلب، برنامه تشخیص وجود دور در گراف جهت دار در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «پایتون» (Python) ارائه شده است. همچنین، در مطلب «برنامه بررسی وجود دور در گراف بدون جهت -- راهنمای کاربردی» نیز به روش تشخیص دور در گراف‌های بدون جهت پرداخته شده است. در ادامه، مساله تشخیص دور در گراف جهت‌دار، همراه با مثالی تشریح می‌شود. یک گراف جهت‌دار (Directed Graph) داده شده است و هدف بررسی این است که آیا گراف دارای دور است یا خیر. تابع باید در صورتی که گراف داده شده حاوی دستکم یک دور باشد مقدار True و در غیر این صورت مقدار False را بازگرداند. برای مثال، گراف زیر دارای سه دور از 0->2->0، 0->1->2->0 و 3->3 است. بنابراین تابع باید مقدار true را باز گرداند. می‌توان از «پیمایش اول عمق» (Depth First Traversal | DFS) برای شناسایی دور در گراف استفاده کرد. DFS برای گراف هم‌بند یک درخت تولید می‌کند. در گراف در صورتی که یال پشتی وجود داشته باشد، دور ایجاد می‌شود. یال پشتی، یالی است که از یک گره به خودش (خود-حلقه‌ای) و یا به والدین خود در درخت تولید شده توسط DFS متصل است. در گرافی که در ادامه می‌آید، سه یال پشتی وجود دارد که با ضرب‌در علامت گذاری شده‌اند. می‌توان مشاهده کرد که ۳ یال پشتی نشانگر ۳ دور نمایش داده شده در گراف هستند.

997696

برنامه تشخیص وجود دور در گراف جهت دار

برای یک گراف غیر هم‌بند، جنگل DFS به عنوان خروجی گرفته می‌شود. برای شناسایی دور، می‌توان وجود یک چرخه در درخت‌های مجزا را با بررسی یال پشتی بررسی کرد. برای شناسایی یال پشتی، می‌توان راس‌های موجود در پشته بازگشتی تابع برای پیمایش DFS را دنبال کرد. اگر به راسی رسید که در حال حاضر در پشته بازگشتی قرار دارد، دور در درخت وجود دارد. یالی که راس کنونی را به راس موجود در پشته بازگشتی متصل می‌کند، یال پشتی است. در اینجا، از آرایه []recStack برای پیگیری راس‌ها در پشته بازگشتی استفاده می‌شود.

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

1// A C++ Program to detect cycle in a graph 
2#include<iostream> 
3#include <list> 
4#include <limits.h> 
5  
6using namespace std; 
7  
8class Graph 
9{ 
10    int V;    // No. of vertices 
11    list<int> *adj;    // Pointer to an array containing adjacency lists 
12    bool isCyclicUtil(int v, bool visited[], bool *rs);  // used by isCyclic() 
13public: 
14    Graph(int V);   // Constructor 
15    void addEdge(int v, int w);   // to add an edge to graph 
16    bool isCyclic();    // returns true if there is a cycle in this graph 
17}; 
18  
19Graph::Graph(int V) 
20{ 
21    this->V = V; 
22    adj = new list<int>[V]; 
23} 
24  
25void Graph::addEdge(int v, int w) 
26{ 
27    adj[v].push_back(w); // Add w to v’s list. 
28} 
29  
30// This function is a variation of DFSUytil() in https://www.geeksforgeeks.org/archives/18212 
31bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack) 
32{ 
33    if(visited[v] == false) 
34    { 
35        // Mark the current node as visited and part of recursion stack 
36        visited[v] = true; 
37        recStack[v] = true; 
38  
39        // Recur for all the vertices adjacent to this vertex 
40        list<int>::iterator i; 
41        for(i = adj[v].begin(); i != adj[v].end(); ++i) 
42        { 
43            if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) ) 
44                return true; 
45            else if (recStack[*i]) 
46                return true; 
47        } 
48  
49    } 
50    recStack[v] = false;  // remove the vertex from recursion stack 
51    return false; 
52} 
53  
54// Returns true if the graph contains a cycle, else false. 
55// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212 
56bool Graph::isCyclic() 
57{ 
58    // Mark all the vertices as not visited and not part of recursion 
59    // stack 
60    bool *visited = new bool[V]; 
61    bool *recStack = new bool[V]; 
62    for(int i = 0; i < V; i++) 
63    { 
64        visited[i] = false; 
65        recStack[i] = false; 
66    } 
67  
68    // Call the recursive helper function to detect cycle in different 
69    // DFS trees 
70    for(int i = 0; i < V; i++) 
71        if (isCyclicUtil(i, visited, recStack)) 
72            return true; 
73  
74    return false; 
75} 
76  
77int main() 
78{ 
79    // Create a graph given in the above diagram 
80    Graph g(4); 
81    g.addEdge(0, 1); 
82    g.addEdge(0, 2); 
83    g.addEdge(1, 2); 
84    g.addEdge(2, 0); 
85    g.addEdge(2, 3); 
86    g.addEdge(3, 3); 
87  
88    if(g.isCyclic()) 
89        cout << "Graph contains cycle"; 
90    else
91        cout << "Graph doesn't contain cycle"; 
92    return 0; 
93}

برنامه تشخیص وجود دور در گراف جهت دار در جاوا

1// A Java Program to detect cycle in a graph 
2import java.util.ArrayList; 
3import java.util.LinkedList; 
4import java.util.List; 
5  
6class Graph { 
7      
8    private final int V; 
9    private final List<List<Integer>> adj; 
10  
11    public Graph(int V)  
12    { 
13        this.V = V; 
14        adj = new ArrayList<>(V); 
15          
16        for (int i = 0; i < V; i++) 
17            adj.add(new LinkedList<>()); 
18    } 
19      
20    // This function is a variation of DFSUytil() in  
21    // https://www.geeksforgeeks.org/archives/18212 
22    private boolean isCyclicUtil(int i, boolean[] visited, 
23                                      boolean[] recStack)  
24    { 
25          
26        // Mark the current node as visited and 
27        // part of recursion stack 
28        if (recStack[i]) 
29            return true; 
30  
31        if (visited[i]) 
32            return false; 
33              
34        visited[i] = true; 
35  
36        recStack[i] = true; 
37        List<Integer> children = adj.get(i); 
38          
39        for (Integer c: children) 
40            if (isCyclicUtil(c, visited, recStack)) 
41                return true; 
42                  
43        recStack[i] = false; 
44  
45        return false; 
46    } 
47  
48    private void addEdge(int source, int dest) { 
49        adj.get(source).add(dest); 
50    } 
51  
52    // Returns true if the graph contains a  
53    // cycle, else false. 
54    // This function is a variation of DFS() in  
55    // https://www.geeksforgeeks.org/archives/18212 
56    private boolean isCyclic()  
57    { 
58          
59        // Mark all the vertices as not visited and 
60        // not part of recursion stack 
61        boolean[] visited = new boolean[V]; 
62        boolean[] recStack = new boolean[V]; 
63          
64          
65        // Call the recursive helper function to 
66        // detect cycle in different DFS trees 
67        for (int i = 0; i < V; i++) 
68            if (isCyclicUtil(i, visited, recStack)) 
69                return true; 
70  
71        return false; 
72    } 
73  
74    // Driver code 
75    public static void main(String[] args) 
76    { 
77        Graph graph = new Graph(4); 
78        graph.addEdge(0, 1); 
79        graph.addEdge(0, 2); 
80        graph.addEdge(1, 2); 
81        graph.addEdge(2, 0); 
82        graph.addEdge(2, 3); 
83        graph.addEdge(3, 3); 
84          
85        if(graph.isCyclic()) 
86            System.out.println("Graph contains cycle"); 
87        else
88            System.out.println("Graph doesn't "
89                                    + "contain cycle"); 
90    } 
91} 
92  
93// This code is contributed by Sagar Shah.

برنامه تشخیص وجود دور در گراف جهت دار در پایتون

1# Python program to detect cycle  
2# in a graph 
3  
4from collections import defaultdict 
5  
6class Graph(): 
7    def __init__(self,vertices): 
8        self.graph = defaultdict(list) 
9        self.V = vertices 
10  
11    def addEdge(self,u,v): 
12        self.graph[u].append(v) 
13  
14    def isCyclicUtil(self, v, visited, recStack): 
15  
16        # Mark current node as visited and  
17        # adds to recursion stack 
18        visited[v] = True
19        recStack[v] = True
20  
21        # Recur for all neighbours 
22        # if any neighbour is visited and in  
23        # recStack then graph is cyclic 
24        for neighbour in self.graph[v]: 
25            if visited[neighbour] == False: 
26                if self.isCyclicUtil(neighbour, visited, recStack) == True: 
27                    return True
28            elif recStack[neighbour] == True: 
29                return True
30  
31        # The node needs to be poped from  
32        # recursion stack before function ends 
33        recStack[v] = False
34        return False
35  
36    # Returns true if graph is cyclic else false 
37    def isCyclic(self): 
38        visited = [False] * self.V 
39        recStack = [False] * self.V 
40        for node in range(self.V): 
41            if visited[node] == False: 
42                if self.isCyclicUtil(node,visited,recStack) == True: 
43                    return True
44        return False
45  
46g = Graph(4) 
47g.addEdge(0, 1) 
48g.addEdge(0, 2) 
49g.addEdge(1, 2) 
50g.addEdge(2, 0) 
51g.addEdge(2, 3) 
52g.addEdge(3, 3) 
53if g.isCyclic() == 1: 
54    print "Graph has a cycle"
55else: 
56    print "Graph has no cycle"
57  
58# Thanks to Divyanshu Mehta for contributing this code

خروجی

Graph contains cycle

پیچیدگی زمانی این روش، مشابه با پیچیدیگی زمانی پیمایش DFS و برابر با (O(V+E است.

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

^^

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

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