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

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