J'ai passé plusieurs heures à chercher un pseudocode qui calculerait les types de bords dans un graphique. Je n'ai pas trouvé de version complète, j'en ai donc écrit une nouvelle. Je vais le partager en tant que réponse à ce post, afin que d'autres puissent l'atteindre si nécessaire.Recherche de tous les types de bords dans un graphique. Arborescence, avant, arrière ou bords croisés
edgeTypes(G, Source)
time = 1
Stack s
for each(node in G.vertices)
node.start = 0
node.finish = 0
s.push(Source)
while(!s.isEmpty())
node = s.peek()
if(node.start > 0)
node.finish = time++
s.pop()
else
node.start = time++
for each(neig in node.neighbors)
if(neig.start == 0)
|node, neig|.type = 'tree'
else if(neig.finish == 0)
|node, neig|.type = 'back'
else if(node.start < neig.start)
|node, neig|.type = 'forward'
else |node, neig|.type = 'cross'
if(neig.start == 0)
s.push(neig)