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

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

در این مطلب، برنامه بررسی وجود دور در گراف بدون جهت در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «پایتون» (Python) و «جاوا» (Java) ارائه شده است. در ادامه، مساله تعریف و همراه با مثالی حل می‌شود. یک گراف بدون جهت داده شده است. هدف آن است که بررسی شود آیا دوری در گراف وجود دارد یا نه. برای مثال، گراف زیر دارای دور ۱-۲-۰-۱ است.

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

پیش از این، در مطلبی با عنوان «برنامه تشخیص وجود دور در گراف جهت دار -- راهنمای کاربردی»، روش پیدا کردن دور در گراف جهت دار مورد بررسی قرار گرفت. پیچیدگی زمانی الگوریتم مجموعه‌های مجزا برابر با (O(ELogV است. می‌توان همچون گراف جهت‌دار، از «جستجوی اول عمق» (Depth First Search | DFS) برای شناسایی دور در گراف‌های بدون جهت در زمان (O(V+E استفاده کرد. پیمایش گراف داده شده با استفاده از DFS انجام می‌شود. برای هر راس بازدید شده V، اگر راس همسایه u وجود دارد که پیش از این بازدید شده باشد و u والد v نباشد، دور در گراف وجود دارد. اگر چنین راس مجاوری برای هیچ راسی یافت نشود، گفته می‌شود که گراف فاقد دور است. فرض این رویکرد آن است که هیچ دو یال موازی بین دو راس وجود نداشته باشد.

برنامه بررسی وجود دور در گراف بدون جهت در ++C

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

خروجی

Graph contains cycle
Graph doesn't contain cycle

پیچیدگی زمانی

برنامه، یک پیمایش ساده DFS را در گراف انجام می‌دهد و گراف با استفاده از لیست هم‌جواری نشان داده می‌شود.

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

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

^^

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

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