Как узнать, из каких вершин сделан цикл в неориентированном графе, если в графе только один цикл?

Question

Как узнать, из каких вершин сделан цикл в неориентированном графе, если в графе только один цикл?

как найти из каких вершин сделан цикл в неориентированном графе, если в графе есть только один цикл?

У меня есть код для нахождения цикла в графе, но сейчас мне нужен код, который найдет, из чего сделан цикл вершин.

Вот код (в C ++) для поиска цикла:

bool dfs(int x)
{
state[x] = 1;
for(int j = 0; j < ls[x].size(); j++)
{
if(state[ls[x][j]] == 1 and parent[x] != ls[x][j])
{
t = 0; // Graph contains cycle.
return t;
}
if(state[ls[x][j]] == 0)
{
parent[ls[x][j]] = x;
dfs(ls[x][j]);
}
}
}

void detect_cycle()
{
memset(state, 0, sizeof state);
memset(parent, 0, sizeof parent);
for(int i = 1; i <= n; i++)
if(state[i] == false)
dfs(i);
}

Благодарю.

Вот окончательный код. Спасибо, парни.

bool dfs(int x)
{
state[x] = 1;
for(int j = 0; j < ls[x].size(); j++)
{
if(state[ls[x][j]] == 1 and parent[x] != ls[x][j])
{
if(t)
{
printf("Cycle entry: %d\n", ls[x][j]);
printf("Cycle contains: %d, %d ", ls[x][j], x);
int cycleNode = parent[x];
while(cycleNode != ls[x][j])
{
printf("%d ", cycleNode);
cycleNode = parent[cycleNode];
}
}
t = 0;
return t;
}
if(state[ls[x][j]] == 0)
{
parent[ls[x][j]] = x;
dfs(ls[x][j]);
}
}
}

1

algorithm c++graph-algorithm

Решение

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

Наивный метод — просто отбросить любой узел со степенью 1, пока все узлы не получат степень 2. Это цикл в графе.

5

когда вы запускаете dfs, если вершина отмечена ранее, чем dfs (), должен быть цикл.

     A
/
B
|  \
C  E
\ /
D

если в графе есть только один цикл, то вершина, помеченная перед, является входом в цикл, как B ниже, какой бы ни была начальная вершина dfs.
и в вашем коде,

if(state[ls[x][j]] == 1 and parent[x] != ls[x][j])
{
t = 0; // Graph contains cycle.
return t;
}

во-первых if() {}, parent и t не нужны, измените на:

if(state[ls[x][j]] == 1 and parent[x] != ls[x][j])
{
cout<<"cycle's entry:"<<j<<endl;
// Graph contains cycle.
return false;
}

кроме того, ваш код нужен return true; вне for из dfs(),

0

Источник

Accepted Answer

Если я прав, то parent [] — это массив (parent [i] — номер узла, который вы прожили прямо перед посещением i-го).

Затем вы знаете, что если график содержит цикл (вы посещаете узел, который вы уже посетили), вы знаете по крайней мере один узел в цикле (предположим, что это k-й узел). В этом случае родительский узел [k] также принадлежит циклу, а родительский [parent [k]] и т. Д.

Итак, мы получаем следующий код:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

vector <int> state;
vector <vector <int> > ls; //graph
vector <int> parent;
bool t = 1;
int theNodeInTheCycle;

void dfs(int x)
{
state[x] = 1;
for(int j = 0; j < ls[x].size(); j++)
{
if(state[ls[x][j]] == 1 && parent[x] != ls[x][j])
{
parent[ls[x][j]] = x;
theNodeInTheCycle = ls[x][j]; //ls[x][j] belongs to the cycle since state[ls[x][j]]==1
t = 0;
}
if(state[ls[x][j]] == 0)
{
parent[ls[x][j]] = x;
dfs(ls[x][j]);
}
}
}

vector <int> GetCycle ()
{
vector <int> cycle;
int firstNodeInTheCycle = theNodeInTheCycle;
do
{
theNodeInTheCycle = parent[theNodeInTheCycle];
cycle.push_back (theNodeInTheCycle);
} while (theNodeInTheCycle != firstNodeInTheCycle);

reverse (cycle.begin (), cycle.end ()); //to get them in the right order
return cycle;
}

int main()
{
int n; cin>>n; //the number of nodes (from 0 to n-1)
int m; cin>>m; //the number of edges

state.resize (n);
ls.resize (n);
parent.resize (n);

for (int i = 0; i < m; ++i)
{
int a, b; cin>>a>>b;
ls[a].push_back(b);
ls[b].push_back(a);
}

for (int i = 0; i<n; ++i)
if (state[i]==0)
dfs(i);

if (t==0)
{
vector <int> cycle = GetCycle ();
for (int i = 0; i < cycle.size (); ++i)
cout<<cycle[i]<<" ";
cout<<"\n";
}
else cout<<"No cycle\n";
}

0