График: Как обнаружить циклы в нецелевом графе с помощью DFS

Question

График: Как обнаружить циклы в нецелевом графе с помощью DFS

Ниже приведена моя реализация DFS, теперь я хочу реализовать ее так, чтобы я мог определить, присутствуют ли в графике какие-либо циклы или нет (приведенный ниже код в основном используется для определения количества подключенных элементов).

#include <iostream>
#include <vector>
using namespace std;

vector <int> adj[10];
int visited[10];
bool flag=false;

void dfs(int s) {
visited[s] = 0;
for(int i = 0;i < adj[s].size();++i)    {
if(visited[adj[s][i]] == -1)
dfs(adj[s][i]);
else if (visited[adj[s][i]] ==1){
flag=true;
// cout<<"g";
return;
}
}
visited[s]=1;
}

void initialize() {
for(int i = 0;i < 10;++i)
visited[i] = -1;
}

int main() {
int nodes, edges, x, y ;
cin >> nodes;                       //Number of nodes
cin >> edges;                       //Number of edges
for(int i = 0;i < edges;++i) {
cin >> x >> y;
adj[x].push_back(y);                   //Edge from vertex x to vertex y
adj[y].push_back(x);                   //Edge from vertex y to vertex x
}

initialize();                           //Initialize all nodes as not visited

for(int i = 1;i <= nodes;++i) {
if(visited[i] == false)     {
dfs(i);
}

}
if (flag)
cout<<"Graph contains cycles"<<endl;
else
cout<<"No cycles"<<endl;
return 0;
}

Я не уверен, как реализовать это, кто-нибудь может мне помочь с этим.

редактироватьЯ пытался это реализовать. Не знаю, где я иду не так

0

c++dfs graph-theory stl

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

После вызова инициализации я изменил цикл:

for(int i = 0;i < nodes;++i) {
if(visited[i] == -1)     {
dfs(i);
}
}

Ваш код не начал проверку, потому что каждый элемент в visited был установлен на -1 и поэтому пропустил. Так что с этим изменением это работает.

Предлагаю посмотреть размер ваших глобальных переменных adj а также vistedсделайте их локальными, если это возможно. Когда введено 11 или более узлов, этот код перестанет работать.

Изменить вопрос «Можете ли вы сказать мне, как я проверяю отключенный график?»

Измените тот же цикл на это:

int nr_of_graphs = 0;
for(int i = 0;i < nodes;++i) {
if(visited[i] == -1)     {
++nr_of_graphs;
dfs(i);
}
}
cout << "Nr of disconnected subgraphs " << nr_of_graphs << endl;

dfs(i) вызывается для каждого еще не посещенного узла. Поэтому посчитайте, сколько раз эта функция вызывается из main, чтобы получить количество отключенных подграфов.

1