برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی

1// A C++ Program to detect cycle in an undirected graph 
2#include<iostream> 
3#include <list> 
4#include <limits.h> 
5using namespace std; 
6  
7// Class for an undirected graph 
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[], int parent); 
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 
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    adj[w].push_back(v); // Add v to w’s list. 
29} 
30  
31// A recursive function that uses visited[] and parent to detect 
32// cycle in subgraph reachable from vertex v. 
33bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
34{ 
35    // Mark the current node as visited 
36    visited[v] = true; 
37  
38    // Recur for all the vertices adjacent to this vertex 
39    list<int>::iterator i; 
40    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
41    { 
42        // If an adjacent is not visited, then recur for that adjacent 
43        if (!visited[*i]) 
44        { 
45           if (isCyclicUtil(*i, visited, v)) 
46              return true; 
47        } 
48  
49        // If an adjacent is visited and not parent of current vertex, 
50        // then there is a cycle. 
51        else if (*i != parent) 
52           return true; 
53    } 
54    return false; 
55} 
56  
57// Returns true if the graph contains a cycle, else false. 
58bool Graph::isCyclic() 
59{ 
60    // Mark all the vertices as not visited and not part of recursion 
61    // stack 
62    bool *visited = new bool[V]; 
63    for (int i = 0; i < V; i++) 
64        visited[i] = false; 
65  
66    // Call the recursive helper function to detect cycle in different 
67    // DFS trees 
68    for (int u = 0; u < V; u++) 
69        if (!visited[u]) // Don't recur for u if it is already visited 
70          if (isCyclicUtil(u, visited, -1)) 
71             return true; 
72  
73    return false; 
74} 
75  
76// Driver program to test above functions 
77int main() 
78{ 
79    Graph g1(5); 
80    g1.addEdge(1, 0); 
81    g1.addEdge(0, 2); 
82    g1.addEdge(2, 0); 
83    g1.addEdge(0, 3); 
84    g1.addEdge(3, 4); 
85    g1.isCyclic()? cout << "Graph contains cycle\n": 
86                   cout << "Graph doesn't contain cycle\n"; 
87  
88    Graph g2(3); 
89    g2.addEdge(0, 1); 
90    g2.addEdge(1, 2); 
91    g2.isCyclic()? cout << "Graph contains cycle\n": 
92                   cout << "Graph doesn't contain cycle\n"; 
93  
94    return 0; 
95}

1// A Java Program to detect cycle in an undirected graph 
2import java.io.*; 
3import java.util.*; 
4  
5// This class represents a directed graph using adjacency list 
6// representation 
7class Graph 
8{ 
9    private int V;   // No. of vertices 
10    private LinkedList<Integer> adj[]; // Adjacency List Represntation 
11  
12    // Constructor 
13    Graph(int v) { 
14        V = v; 
15        adj = new LinkedList[v]; 
16        for(int i=0; i<v; ++i) 
17            adj[i] = new LinkedList(); 
18    } 
19  
20    // Function to add an edge into the graph 
21    void addEdge(int v,int w) { 
22        adj[v].add(w); 
23        adj[w].add(v); 
24    } 
25  
26    // A recursive function that uses visited[] and parent to detect 
27    // cycle in subgraph reachable from vertex v. 
28    Boolean isCyclicUtil(int v, Boolean visited[], int parent) 
29    { 
30        // Mark the current node as visited 
31        visited[v] = true; 
32        Integer i; 
33  
34        // Recur for all the vertices adjacent to this vertex 
35        Iterator<Integer> it = adj[v].iterator(); 
36        while (it.hasNext()) 
37        { 
38            i = it.next(); 
39  
40            // If an adjacent is not visited, then recur for that 
41            // adjacent 
42            if (!visited[i]) 
43            { 
44                if (isCyclicUtil(i, visited, v)) 
45                    return true; 
46            } 
47  
48            // If an adjacent is visited and not parent of current 
49            // vertex, then there is a cycle. 
50            else if (i != parent) 
51                return true; 
52        } 
53        return false; 
54    } 
55  
56    // Returns true if the graph contains a cycle, else false. 
57    Boolean isCyclic() 
58    { 
59        // Mark all the vertices as not visited and not part of 
60        // recursion stack 
61        Boolean visited[] = new Boolean[V]; 
62        for (int i = 0; i < V; i++) 
63            visited[i] = false; 
64  
65        // Call the recursive helper function to detect cycle in 
66        // different DFS trees 
67        for (int u = 0; u < V; u++) 
68            if (!visited[u]) // Don't recur for u if already visited 
69                if (isCyclicUtil(u, visited, -1)) 
70                    return true; 
71  
72        return false; 
73    } 
74  
75  
76    // Driver method to test above methods 
77    public static void main(String args[]) 
78    { 
79        // Create a graph given in the above diagram 
80        Graph g1 = new Graph(5); 
81        g1.addEdge(1, 0); 
82        g1.addEdge(0, 2); 
83        g1.addEdge(2, 0); 
84        g1.addEdge(0, 3); 
85        g1.addEdge(3, 4); 
86        if (g1.isCyclic()) 
87            System.out.println("Graph contains cycle"); 
88        else
89            System.out.println("Graph doesn't contains cycle"); 
90  
91        Graph g2 = new Graph(3); 
92        g2.addEdge(0, 1); 
93        g2.addEdge(1, 2); 
94        if (g2.isCyclic()) 
95            System.out.println("Graph contains cycle"); 
96        else
97            System.out.println("Graph doesn't contains cycle"); 
98    } 
99} 
100// This code is contributed by Aakash Hasija

1# Python Program to detect cycle in an undirected graph 
2  
3from collections import defaultdict 
4   
5#This class represents a undirected graph using adjacency list representation 
6class Graph: 
7   
8    def __init__(self,vertices): 
9        self.V= vertices #No. of vertices 
10        self.graph = defaultdict(list) # default dictionary to store graph 
11  
12   
13    # function to add an edge to graph 
14    def addEdge(self,v,w): 
15        self.graph[v].append(w) #Add w to v_s list 
16        self.graph[w].append(v) #Add v to w_s list 
17   
18    # A recursive function that uses visited[] and parent to detect 
19    # cycle in subgraph reachable from vertex v. 
20    def isCyclicUtil(self,v,visited,parent): 
21  
22        #Mark the current node as visited  
23        visited[v]= True
24  
25        #Recur for all the vertices adjacent to this vertex 
26        for i in self.graph[v]: 
27            # If the node is not visited then recurse on it 
28            if  visited[i]==False :  
29                if(self.isCyclicUtil(i,visited,v)): 
30                    return True
31            # If an adjacent vertex is visited and not parent of current vertex, 
32            # then there is a cycle 
33            elif  parent!=i: 
34                return True
35          
36        return False
37           
38   
39    #Returns true if the graph contains a cycle, else false. 
40    def isCyclic(self): 
41        # Mark all the vertices as not visited 
42        visited =[False]*(self.V) 
43        # Call the recursive helper function to detect cycle in different 
44        #DFS trees 
45        for i in range(self.V): 
46            if visited[i] ==False: #Don't recur for u if it is already visited 
47                if(self.isCyclicUtil(i,visited,-1))== True: 
48                    return True
49          
50        return False
51  
52# Create a graph given in the above diagram 
53g = Graph(5) 
54g.addEdge(1, 0) 
55g.addEdge(0, 2) 
56g.addEdge(2, 0) 
57g.addEdge(0, 3) 
58g.addEdge(3, 4) 
59  
60if g.isCyclic(): 
61    print "Graph contains cycle"
62else : 
63    print "Graph does not contain cycle "
64g1 = Graph(3) 
65g1.addEdge(0,1) 
66g1.addEdge(1,2) 
67  
68  
69if g1.isCyclic(): 
70    print "Graph contains cycle"
71else : 
72    print "Graph does not contain cycle "
73   
74#This code is contributed by Neelam Yadav