एक अप्रत्यक्ष ग्राफ में चक्र का पता लगाएं

यह पता लगाने के लिए कि अप्रत्यक्ष ग्राफ में कोई चक्र है या नहीं, हम दिए गए ग्राफ के लिए DFS ट्रैवर्सल का उपयोग करेंगे। प्रत्येक देखे गए शीर्ष v के लिए, जब हमें कोई आसन्न शीर्ष u मिलता है, जैसे कि आप पहले ही जा चुके हैं, और u शीर्ष v का जनक नहीं है। तब एक चक्र का पता लगाया जाता है।

हम मान लेंगे कि किसी भी शीर्ष युग्म के लिए समानांतर किनारे नहीं हैं।

Input and Output:
Adjacency matrix
   
    0 1 0 0 0
    1 0 1 1 0
    0 1 0 0 1
    0 1 0 0 1
    0 0 1 1 0

Output:
The graph has cycle.

एल्गोरिदम

dfs(vertex, visited, parent)

Input: The start vertex, the visited set, and the parent node of the vertex.
Output: True a cycle is found.Begin
   add vertex in the visited set
   for all vertex v which is adjacent with vertex, do
      if v = parent, then
         return true
      if v is not in the visited set, then
         return true
      if dfs(v, visited, vertex) is true, then
         return true
   done
   return false
End hasCycle(graph)

Input: The given graph.

Output: True when a cycle has found.Begin
   for all vertex v in the graph, do
      if v is not in the visited set, then
         go for next iteration
      if dfs(v, visited, φ) is true, then     //parent of v is null
         return true
      return false
   done
End

उदाहरण

#include<iostream>
#include<set>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {0, 1, 0, 0, 0},
   {1, 0, 1, 1, 0},
   {0, 1, 0, 0, 1},
   {0, 1, 0, 0, 1},
   {0, 0, 1, 1, 0}
};

bool dfs(int vertex, set<int>&visited, int parent) {
   visited.insert(vertex);
   for(int v = 0; v<NODE; v++) {
      if(graph[vertex][v]) {
         if(v == parent)    //if v is the parent not move that direction
            continue;
         if(visited.find(v) != visited.end())    //if v is already visited
            return true;
         if(dfs(v, visited, vertex))
            return true;
      }
   }
   return false;
}

bool hasCycle() {
   set<int> visited;       //visited set
   for(int v = 0; v<NODE; v++) {
      if(visited.find(v) != visited.end())    //when visited holds v, jump to next iteration
         continue;
      if(dfs(v, visited, -1)) {    //-1 as no parent of starting vertex
         return true;
      }
   }
   return false;
}

int main() {
   bool res;
   res = hasCycle();
   if(res)
      cout << "The graph has cycle." << endl;
   else
      cout << "The graph has no cycle." << endl;
}

आउटपुट

The graph has cycle.