J'apprends la traversée de graphes dans The Algorithm Design Manual de Steven S. Skiena. Dans son livre, il a fourni le code permettant de parcourir le graphique à l'aide de dfs. Ci-dessous le code.
dfs(graph *g, int v)
{
edgenode *p;
int y;
if (finished) return;
discovered[v] = TRUE;
time = time + 1;
entry_time[v] = time;
process_vertex_early(v);
p = g->edges[v];
while (p != NULL) {
/* temporary pointer */
/* successor vertex */
/* allow for search termination */
y = p->y;
if (discovered[y] == FALSE) {
parent[y] = v;
process_edge(v,y);
dfs(g,y);
}
else if ((!processed[y]) || (g->directed))
process_edge(v,y);
}
if (finished) return;
p = p->next;
}
process_vertex_late(v);
time = time + 1;
exit_time[v] = time;
processed[v] = TRUE;
}
Dans un graphe non orienté, il semble que le code ci-dessous traite l'arête deux fois (en appelant la méthode process_edge (v, y). L'une en parcourant le sommet v et l'autre en traitant le sommet y).
J'ai donc ajouté la condition parent[v]!=y dans else if ((!processed[y]) || (g->directed)).
Il traite le bord une seule fois. Cependant, je ne suis pas sûr de savoir comment modifier ce code pour qu'il fonctionne avec le bord parallèle et le bord à boucle automatique. Le code doit traiter le bord parallèle et la boucle automatique.
Réponses:
2 pour la réponse № 1Réponse courte:
Remplacer votre (parent[v]!=y) pour (!processed[y]) au lieu de l'ajouter à la condition.
Réponse détaillée:
A mon avis il y a une erreur dans leimplémentation écrite dans le livre, que vous avez découvert et corrigé (sauf pour les bords parallèles. Plus d’informations ci-dessous) L’implémentation est supposée être correcte pour les graphes dirigés et non dirigés, la distinction entre eux étant enregistrée dans le g->directed propriété booléenne.
Dans le livre, juste avant la mise en oeuvre, l'auteur écrit:
L'autre propriété importante d'une profondeur d'abordla recherche est qu'il partitionne la les arêtes d’un graphe non orienté en exactement deux classes: les arêtes des arbres et les arrières le les arêtes de l’arbre découvrent de nouveaux sommets et sont celles encodées dans la relation parent. Retour les bords sont ceux dont l'autre extrémité est un ancêtre du sommet en expansion, alors ils pointent dans l'arbre.
Donc la condition (!processed[y]) est supposé gérer les graphes non dirigés (comme la condition (g->directed) est de gérer les graphes orientés) en permettant aualgorithme pour traiter les arêtes qui sont arrière et l'empêcher de retraiter celles qui sont des arbres (dans la direction opposée). Comme vous l'avez remarqué, cependant, les arêtes de l'arborescence sont traitées comme des arrières-bords lorsqu'elles sont lues par l'enfant avec cette condition. Vous devez donc simplement remplacer cette condition par votre suggestion. (parent[v]!=y).
La condition (!processed[y]) sera toujours vrai pour un graphe non orienté lorsquel'algorithme le lit tant qu'il n'y a pas d'arêtes parallèles (plus de détails sur pourquoi c'est vrai - *). S'il y a des arêtes parallèles - ces arêtes parallèles lues après la première "copie" d'entre elles donneront false et le bord ne sera pas traité, quand ildevrait être. Toutefois, la condition que vous proposez distinguera les arêtes des arbres du reste (arrières, arêtes parallèles et boucles automatiques) et permettra à l’algorithme de ne traiter que celles qui ne sont pas des arbres dans la direction opposée.
Pour se référer aux bords de soi, ils devraient être bien avec les nouvelles et les anciennes conditions: ce sont des bords avec y==v. Arriver à eux, y est découvert (parce que v est découvert avant de traverser ses bords), non traité (v n'est traité que comme dernière ligne - après avoir traversé ses bords) et il n'est pas v"le parent (v n'est pas son propre parent).
*Passer au travers v"s bords, l'algorithme lit cette condition pour y cela a été découvert (pour ne pas "entrer dans le premier bloc conditionnel). Comme cité ci-dessus (dans le livre il y a une demi-preuve pour cela aussi que je vais inclure à la fin de cette note), p est soit une arête ou un bord arrière. Comme y est découvert, il ne peut pas être une arête de v à y. Ce peut être un bord arrière pour un ancêtre quisignifie que l’appel est dans un appel récursif qui a commencé à traiter cet ancêtre à un moment donné. L’appel de cet ancêtre n’a pas encore atteint la dernière ligne, la marquant comme traitée (elle est donc toujours marquée comme non traitée) et elle peut être un arbre de y à v, auquel cas la même situation est vraie - et y est toujours marqué comme non traité.
La semi-preuve pour chaque bord étant un bord d'arbre ou un bord arrière:
Pourquoi un bord ne peut-il pas aller à un nœud frère ou cousin?au lieu d'un ancêtre? Tous les nœuds accessibles depuis un sommet donné v sont développés avant de terminer avec le traversal from v, de telles topologies sont donc impossibles pour les graphes non dirigés.
1 pour la réponse № 2
Vous avez raison.
Citant le book "s (2nd edition) errata:
(*) Page 171, ligne -2 - Le code DFS a un bogue, où chaque bord de l'arbre est traité deux fois dans des graphes non dirigés. Le test doit être renforcé pour être:
else if (((!processed[y]) && (parent[v]!=y)) || (g->directed))
Quant aux cycles - voir ici