Détection de cycles dans un graphique à L'aide de DFS: 2 approches différentes et quelle est la différence
Notez qu'un graphique est représenté comme une liste de contiguïté.
J'ai entendu parler de 2 approches pour trouver un cycle dans un graphe:
Conservez un tableau de valeurs booléennes pour savoir si vous avez déjà visité un nœud. Si vous êtes à court de nouveaux nœuds (sans toucher à un nœud que vous avez déjà été), revenez en arrière et essayez une branche différente.
Celui de Clrs de Cormen ou Skiena: pour la recherche en profondeur d'abord dans les graphiques non orientés, il existe deux types de bords, de l'arbre et à l'arrière. Le graphique a un cycle si et seulement s'il existe un bord arrière.
Quelqu'un peut-il expliquer quels sont les bords arrière d'un graphique et quelle est la diffirence entre les 2 méthodes ci-dessus.
Merci.
Mise à Jour: Voici le code pour détecter les cycles dans les deux cas. Graph est une classe simple qui représente tous les nœuds de graphe sous forme de nombres uniques pour plus de simplicité, chaque nœud a ses nœuds voisins adjacents (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;
}
}
Code Java pour détecter les cycles dans un graphe non-dirigé:
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;
}
}
}
}
Code Java pour détecter les cycles dans un graphe orienté:
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;
}
}
3 réponses
Pour Répondre à ma question:
Le graphique a un cycle si et seulement s'il existe un bord arrière. Un bord arrière est un avantage qui est d'un nœud à lui-même (selfloop) ou l'un de ses ancêtre dans l'arbre produit par DFS formant un cycle.
Les deux approches ci-dessus signifient en fait la même chose. Cependant, cette méthode ne peut être appliquée qu'aux Graphiques non orientés .
La raison pour laquelle cet algorithme ne fonctionne pas pour les graphes dirigés est que dans un graphe dirigé 2 chemins différents au même sommet ne font pas un cycle. Par exemple: A-->B, B-->C, A-->C - ne faites pas un cycle alors que dans les non orientés: A--B, B--C, C--A fait.
Trouver un cycle dans les graphiques non orientés
Un graphe non orienté a un cycle si et seulement si une recherche en profondeur (DFS) trouve un bord qui pointe vers un sommet déjà visité (un bord arrière).
Trouver un cycle dans les graphes orientés
En plus des sommets visités, nous devons garder une trace des sommets actuellement pile de récursivité de la fonction pour la traversée DFS. Si nous atteignons un sommet qui est déjà dans la pile de récursion, alors il existe un cycle dans l'arbre.
Mise à Jour: Code de travail est dans la question ci-dessus.
Par souci d'achèvement, il est possible de trouver des cycles dans un graphe dirigé en utilisant DFS (de 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
Voici le code que j'ai écrit en C basé sur DFS pour savoir si un graphe non orienté donné est connecté/cyclique ou non. avec une sortie d'échantillon à la fin. J'espère que ce sera utile :)
#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);
}
Exemple De Sortie:
majid@majid-K53SC:~/Desktop$ gcc BFS.c
majid@majid-K53SC:~/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!
majid@majid-K53SC:~/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!
majid@majid-K53SC:~/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!
*/