Обнаружение циклов в графе с использованием DFS: 2 разных подхода и какая разница
Обратите внимание, что граф представлен в виде списка смежности.
Я слышал о двух подходах к поиску цикла в графике:
-
Храните массив логических значений, чтобы отслеживать, посещали ли вы ранее node. Если у вас закончились новые узлы, чтобы перейти (без удара node вы уже были), тогда просто отступите назад и попробуйте другую ветку.
-
Один из Cormen CLRS или Skiena: для поиска по глубине в неориентированных графах есть два типа ребер, дерево и спина. Граф имеет цикл тогда и только тогда, когда существует задний край.
Может кто-нибудь объяснить, каковы обратные края графа и какова разница между указанными выше методами.
Спасибо.
Update:
Здесь код для обнаружения циклов в обоих случаях. График - это простой класс, который представляет все узлы графа как уникальные числа для простоты, каждый node имеет соседние соседние узлы (g.getAdjacentNodes(int)):
public class Graph {
private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};
public int[] getAdjacentNodes(int v) {
return nodes[v];
}
// number of vertices in a graph
public int vSize() {
return nodes.length;
}
}
Java-код для обнаружения циклов в неориентированном графе:
public class DFSCycle {
private boolean marked[];
private int s;
private Graph g;
private boolean hasCycle;
// s - starting node
public DFSCycle(Graph g, int s) {
this.g = g;
this.s = s;
marked = new boolean[g.vSize()];
findCycle(g,s,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v, int u) {
marked[v] = true;
for (int w : g.getAdjacentNodes(v)) {
if(!marked[w]) {
marked[w] = true;
findCycle(g,w,v);
} else if (v != u) {
hasCycle = true;
return;
}
}
}
}
Java-код для определения циклов в ориентированном графе:
public class DFSDirectedCycle {
private boolean marked[];
private boolean onStack[];
private int s;
private Graph g;
private boolean hasCycle;
public DFSDirectedCycle(Graph g, int s) {
this.s = s
this.g = g;
marked = new boolean[g.vSize()];
onStack = new boolean[g.vSize()];
findCycle(g,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v) {
marked[v] = true;
onStack[v] = true;
for (int w : g.adjacentNodes(v)) {
if(!marked[w]) {
findCycle(g,w);
} else if (onStack[w]) {
hasCycle = true;
return;
}
}
onStack[v] = false;
}
}
Ответы
Ответ 1
Отвечая на мой вопрос:
Граф имеет цикл тогда и только тогда, когда существует задний край. Задний край - это край, который от node к себе (selfloop) или к одному из его предков в дереве, создаваемом DFS, образуя цикл.
Оба подхода выше фактически означают одно и то же. Однако этот метод может применяться только к неориентированным графам.
Причина, по которой этот алгоритм не работает для ориентированных графов, заключается в том, что в ориентированном графе 2 разные пути к одной и той же вершине не производят цикл. Например: A → B, B → C, A → C - не производят цикл, тогда как в ненаправленных: A - B, B - C, C - A.
Найти цикл в неориентированных графах
Неориентированный граф имеет цикл тогда и только тогда, когда поиск глубины (DFS) находит ребро, которое указывает на уже посещенную вершину (задний край).
Найти цикл в ориентированных графах
В дополнение к посещенным вершинам нам нужно отслеживать вершины, находящиеся в настоящее время в стеке рекурсии функции для обхода DFS. Если мы достигнем вершины, которая уже находится в стеке рекурсии, тогда в дереве есть цикл.
Update:
Рабочий код находится в разделе вопросов выше.
Ответ 2
Для завершения можно найти циклы в ориентированном графе с использованием DFS (из wikipedia):
L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop (not a DAG)
if n is not marked (i.e. has not been visited yet) then
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
unmark n temporarily
add n to head of L
Ответ 3
Вот код, который я написал в C на основе DFS, чтобы узнать, связан ли данный неориентированный граф/циклический или нет. с некоторым количеством выходных данных в конце. Надеюсь, это будет полезно:)
#include<stdio.h>
#include<stdlib.h>
/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;
/****DFS Function Declaration****/
void DFS();
/****DFSearch Function Declaration****/
void DFSearch(int cur);
/****Main Function****/
int main()
{
int i,j;
printf("\nEnter no of Vertices: ");
scanf("%d",&n);
printf("\nEnter the Adjacency Matrix(1/0):\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]);
printf("\nThe Depth First Search Traversal:\n");
DFS();
for(i=1;i<=n;i++)
printf("%c,%d\t",'a'+seq[i]-1,i);
if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!");
if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!");
if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!");
if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!");
printf("\n\n");
return 0;
}
/****DFS Function Definition****/
void DFS()
{
int i;
for(i=1;i<=n;i++)
if(!visited[i])
{
if(i>1) connected=0;
DFSearch(i);
}
}
/****DFSearch Function Definition****/
void DFSearch(int cur)
{
int i,j;
visited[cur]=++count;
seq[count]=cur;
for(i=1;i<count-1;i++)
if(A[cur][seq[i]])
acyclic=0;
for(i=1;i<=n;i++)
if(A[cur][i] && !visited[i])
DFSearch(i);
}
Результат вывода:
[email protected]:~/Desktop$ gcc BFS.c
[email protected]:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 10
Enter the Adjacency Matrix(1/0):
0 0 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0
The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10
It is a Not-Connected, Cyclic Graph!
[email protected]:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 4
Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1
The Depth First Search Traversal:
a,1 c,2 b,3 d,4
It is a Connected, Acyclic Graph!
[email protected]:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 5
Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5
It is a Not-Connected, Acyclic Graph!
*/
