Je sais qu'il y a de nombreuses réponses existantes sur cette question. Cependant, je n'ai trouvé aucun d'entre eux l'apportant vraiment au point.
Certains soutiennent qu'un cycle est (presque) identique à un composant fortement connecté (s. Trouver tous les cycles dans un graphique dirigé ), vous pouvez donc utiliser des algorithmes conçus pour cet objectif.
Certains soutiennent que la recherche du cycle
de
J'aimerais maintenant avoir des suggestions sur la question de savoir si
http://www.me.utexas.edu/~bard/ IP / Documents / Cycles.pdf (trouvé ici sur SO) indique une méthode basée sur des bases de cycle. Moi personnellement, je ne trouve pas cela très intuitif, alors je cherche une solution différente.
de
EDIT: Mon avis initial était apparemment faux. S. prochaine réponse de "Moron".
de
Initial Opinion:
Mon opinion est que cela pouvait effectivement travailler de cette façon, car DFS-Visit (s. Pseudocode de DFS) entre fraîche chaque nœud qui n'a pas encore été visité. En ce sens, chaque sommet présente un début potentiel d'un cycle. De plus, en tant que DFS visit chaque bord une fois, chaque bord menant au point de départ d'un cycle est également couvert. Ainsi, en utilisant des fichiers DFS et de bord arrière, il convient de pouvoir détecter des cycles
4 Réponses :
Si un algorithme traversant visite chaque bord une seule fois, il ne peut pas trouver tous les cycles. Un bord pourrait faire partie de plusieurs cycles.
BTW, qu'est-ce qu'un back-bord?
Aussi, vous devriez peut-être reformuler votre question. Il est très difficile de lire.
Un bord arrière est un bord qui va d'un nœud à l'un de ses ancêtres dans un arbre de recherche. Par exemple. Les bords (A, B), (B, C) et (C, A) d'un graphique non dirigé, puis (A, B) ou (C, A) seront un bord arrière (si root = a). Ce n'est pas un bord d'arbre de l'arbre de recherche, et il est créé lorsque, lors de la visite DFS, un Edge passe d'un nouveau noeud à un nouveau noeud à un autre visité (gris), mais pas encore terminé, noeud.
à votre première réponse : Si un bord fait partie de plusieurs cycles, chaque cycle sera traversé une fois => Tous les back-arêtes seront détectés => Tous les cycles doivent être détectés Afaik.
Veuillez corriger-moi si je me trompe!
Désolé, je dois me corriger et être d'accord avec toi "Moron". Je limitais mes "cycles" aux triangles lors de l'exploration des exemples et de me concentrer fermement sur la détection de ces triangles. Cela signifie que "l'algorithme" a toujours suivi les bords qui conduisent directement à des triangles, bien que cela n'a pas besoin d'être le cas. Par exemple. 2 triangles, partageant un bord (cycle plus grand = rectangle), le rectangle peut être découvert d'abord en tant que cycle et les 2 triangles pourraient être manqués. Et vice versa.
J'ai déjà répondu à cette question, alors vérifiez ceci:
une aide source Trier toujours renvoyer un cycle maximal?
la partie pertinente de la réponse:
Effectuer une recherche de profondeur-première sur votre graphique.
vous êtes intéressé à reconnaître bords, c'est-à-dire dans la traversée, un bord qui repoussent dans un ancêtre (dans l'arbre DFS, qui est induit par bords de nœuds de visite pour le premier temps) du nœud visité. Pour Exemple, si la pile DFS a des nœuds [A-> b-> c-> d] et pendant que vous explorez d vous trouvez un bord d-> b, c'est un dos bord. Chaque bord du dos définit un cycle.
Plus important encore, les cycles induits par des bords de retour sont un ensemble de base de cycles du graphique. "Un ensemble de base de cycles ": vous pouvez construire tous les cycles du graphique juste en l'unioning et Cycles xornor de l'ensemble de base. Pour Exemple, considérez les cycles [A1-> A2-> A3-> A1] et [A2-> B1-> B2-> B3-> A2]. Vous pouvez le syndicat eux au cycle: [A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1].
Peut-être que cela peut vous aider d'une manière ou d'une autre, j'ai trouvé site où une couleur DFS de couleur pour un graphique dirigé est décrite. Vous pouvez donc envisager de corriger la traduction DFS à PHP que je présente ici.
Ce que j'ai ajouté, c'est un rôle pour créer une forêt et une autre partie pour trouver tous les cycles. Alors s'il vous plaît considérez qu'il n'est pas sûr de prendre ces deux parties de mon code comme corrects. P>
Un avec des connaissances sur la théorie du graphique pourrait être en mesure de tester à coup sûr. Il n'y a pas de commentaire dans la partie DFS car elle est décrite déjà dans le site de référence. Je suggère de prendre un exemple avec plus d'un arbre et de dessiner la forêt (besoin de 4 couleurs) dans un papier pour mieux comprendre. P>
Ceci est le code: P>
<?php
define(first,1); //Define how to start counting, from 0 or 1
//nodes are considered to be sequential
$G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1);
$N=key(array_slice($G, -1, 1, TRUE));//last key of g
$H=Array(Array());
$P = Array();
$P[first] = first;
$k = first;
$C = Array();//cycles
$L = Array();//loops
########################## ALGORITHM START #############################
#[Path Extension]
EC2_Path_Extension:
//scan adjacency list
foreach($G[$P[$k]] as $j => $adj_node)
//if there is an adjacent node bigger than P[1] and this nodes does not belong in P
if( ($adj_node > $P[first]) and (in_array($adj_node, $P))===false and
(count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false)
{
$k++;
$P[$k] = $G[$P[$k-1]][$j];
goto EC2_Path_Extension;
}
#[EC3 Circuit Confirmation]
EC3_Circuit_Confirmation:
if(!in_array($P[first], $G[$P[$k]]))
goto EC4_Vertex_Closure;
//otherwise
if (count($P)===1)
$L[] = current($P);
else
$C[] = implode($P);
#[EC4 Vertex Closure]
EC4_Vertex_Closure:
if($k===first)
goto EC5_Advance_Initial_Vertex;
$H[$P[$k]] = Array();
$H[$P[$k-1]][] = $P[$k];
unset($P[$k]);
$k--;
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[first] === $N)
goto EC6_Terminate;
$P[first]++;
$k=first;
//Reset H
$H=Array(Array());
goto EC2_Path_Extension;
EC6_Terminate:
########################### ALGORITHM END ##################################
echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n";
echo count($C)." cycles found!\n".implode("\n",$C)."\n";
/*** Original graph found in the paper ***/
//$G[first] = Array(2); $G[] = Array(2,3,4);
//$G[] = Array(5); $G[] = Array(3); $G[] = Array(1);
?>
Ma suggestion est d'utiliser l'algorithme de Tarjan pour trouver un ensemble de composants fortement connectés, ainsi que l'algorithme Hierholzer pour trouver tous les cycles dans le composant fortement connecté.
Voici le lien de la mise en œuvre Java avec un cas de test: http://stones333.blogspot.com/2013 /12/find-cycles-in-directed-graph-dag.html