La détection de cycles dans un graphe à l'aide de DFS: 2 approches différentes et quelle est la différence
Noter qu'un graphe est représenté par une liste d'adjacence.
J'ai entendu parler de 2 approches pour trouver un cycle dans un graphe:
-
Garder un tableau de valeurs booléennes pour garder une trace de savoir si vous avez visité un nœud avant. Si vous manquez de nouveaux nœuds à l'aller (sans frapper un nœud que vous avez déjà), puis revenir en arrière et essayer une autre branche.
-
L'un de Cormen du PLC ou Skiena: Pour la profondeur de recherche dans les graphes non dirigés, il y a deux types d'arêtes de l'arbre et à l'arrière. Le graphe a un cycle si et seulement si il existe une arête arrière.
Quelqu'un peut-il expliquer ce que sont le dos de arêtes d'un graphe et quelle est la diffirence entre les 2 méthodes.
Grâce.
Mise à jour:
Voici le code pour détecter les cycles dans les deux cas. Le graphique est une simple classe qui représente l'ensemble de graphe de nœuds comme des numéros uniques pour des raisons de simplicité, chaque nœud a ses voisines nœuds voisins (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;
}
}
- Je pense qu'il y a une erreur dans le graphe ordonné code. Dans le cas de parcours d'un graphe en forme de O, avec la racine en haut et avec toutes les arêtes dirigées vers le bas, cet algorithme détecte cycle (d'abord la traversée de la gauche de O vers le bas et marquer tous les nœuds marqués, puis la partie droite de O jusqu'à ce que je vais arriver à fond, ce qui est déjà marqué). Je voudrais ajouter, il y a marqué[v]= false; juste après findCycle(g,w); Qu'en pensez-vous?
- Dans
DFSCycle
la condition à vérifier pour le cycle est incorrect. Il devrait êtreif(i != u) // If an adjacent is visited and not parent of current vertex, then there is a cycle. { hasCycle = true; return; }
- Ne devrait pas
} else if (v != u) {
être} else if (w != u) {
?
Vous devez vous connecter pour publier un commentaire.
Répondre à ma question:
Le graphe a un cycle si et seulement si 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 la même chose. Cependant, cette méthode ne peut être appliquée qu'à non orienté graphiques.
La raison pour laquelle cet algorithme ne fonctionne pas pour les graphes orientés, c'est que dans un graphe orienté 2 chemins différents pour le même sommet, ne pas faire un cycle. Par exemple:-->B, B-->C,-->C - ne pas faire un cycle alors que les non-directifs: A--B, B-C, C-A ne.
Trouver un cycle non-directifs graphiques
Un graphe non-dirigé a un cycle si et seulement si la profondeur d'abord de recherche (DFS) trouve un avantage à un déjà-sommet visité (un bord arrière).
Trouver un cycle dans les graphes orientés
Dans les plus visités sommets nous avons besoin de garder une trace de sommets actuellement dans la récursivité de la pile de la fonction DFS traversée. 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 de réalisation, il est possible de trouver des cycles dans un graphe orienté à l'aide de DFS (à partir de wikipédia):
Voici le code que j'ai écrit en C en fonction de DFS pour savoir si une graphe non-dirigé est connecté/cyclique ou non. avec quelques exemples de la production à la fin. Espère que ça vous sera utile 🙂
Exemple De Sortie:
Je pense que le code ci-dessus ne fonctionne que pour la connexion d'un digraphe puisque nous partons dfs du noeud source seulement, car si le bigramme n'est pas connecté, il peut être un cycle à l'autre élément qui peut passer inaperçu!