Как напечатать цикл содержит узел в ориентированном графе в C ++ - PullRequest
Новая
       36

Как напечатать цикл содержит узел в ориентированном графе в C ++

0 голосов
/ 01 апреля 2020

Я пишу программу, которая обнаружит цикл в ориентированном графе и напечатает узлы, которые построили цикл. Я пытаюсь использовать рекурсивный метод с использованием C ++, не понимая, как печатать эти узлы после обнаружения цикла. Вот мой код: 

#include <bits/stdc++.h>
using namespace std;

void addedge(list<int>,int ,int );
void cycle_check(list<int>*,int);

//  Make a pair between vertex x and vertex y
void addedge(list<int> *ls,int x,int y){
ls[x].push_back(y);
return;
} 

void check_cycle_util(list<int> *ls,bool *visit,int curr_node,int &temp){
visit[curr_node]=true;
list<int>::iterator it;
for(it=ls[curr_node].begin();it!=ls[curr_node].end();it++){
    if(!visit[*it]){
        check_cycle_util(ls,visit,*it,temp);
    }
    else{
        if(temp==0){
            temp=1;
            cout<<"There is a cycle in the graph\n";
            break;
            }
        }
    }
}
//checking the cycles in a graph 
void cycle_check(list<int>*ls,int num){
bool *visit=new bool[num];
int temp=0;
for(int i=0;i<num;i++)
    visit[i]=false;
for(int i=0;i<num;i++){
    if(!visit[i] && temp==0){
        check_cycle_util(ls,visit,i,temp);
        }
    }
}

int main(){
int num;
cout<<"Enter the no. of vertices :";
cin>>num;
list<int> *ls=new list<int>[num];
addedge(ls,0,1);
addedge(ls,2,3);
addedge(ls,3,4);
addedge(ls,4,5);
addedge(ls,1,2);
addedge(ls,1,4);
addedge(ls,3,0);
cycle_check(ls,6);

return 0;
}

1 Ответ

0 голосов
/ 01 апреля 2020

Я думаю, вы могли бы изучить Алгоритм Тариана Сжатия Точек, он используется для поиска сильно связанных компонентов.

Основная идея состоит в том, чтобы использовать одно и то же значение, чтобы отметить все точки сильно связанного компонента. Таким образом, точки с одинаковым значением находятся в одном и том же цикле.

Основные шаги таковы:

  1. Сначала мы определим два массива для точек, один из них - отметка времени массив, это означает порядковый номер в DFS. Другой - это массив младших отметок, это означает минимальное значение временной отметки точки через DFS, другими словами, значение одной точки является минимальным значением среди временной отметки самой точки и младших отметок связанных точек.

  2. Используйте DFS, чтобы назначить массив нижних отметок, а затем все точки, имеющие одинаковую отметку, находятся в одном цикле.

Ps: Потому что мой Engi sh не очень хорош, так что я не могу объяснить алгоритм очень ясно. Поэтому я рекомендую вам ознакомиться с другой статьей, чтобы узнать об этом алгоритме.

Это пример использования стека для сохранения пути:

путь - это вектор, определенный как глобальная переменная 

visit[curr_node]=true;
path.push_back(curr_node);
/* other code */
if(temp==0){
            temp=1;
            cout<<"There is a cycle in the graph\n";
            break;
            for(auto i=path.size()-1;path[i]!=curr_node||i==path.size();--i){
                 cout<<path[i];
            }
  }
}
path.pop_back();
...