একটি অনির্দেশিত গ্রাফে চক্র সনাক্ত করুন

অনির্দেশিত গ্রাফে কোন চক্র আছে কিনা তা সনাক্ত করতে, আমরা প্রদত্ত গ্রাফের জন্য 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.