Comprensione dell'algoritmo di individuazione del ponte di Tarjan

Question

Comprensione dell'algoritmo di individuazione del ponte di Tarjan

#1 da (1 voti)

2

L'algoritmo di Tarjan per la ricerca di ponti in un grafico si trova qui: link .

Tuttavia, non capisco la condizione per verificare se un lato è un ponte. Ho capito che L (w) = w è una condizione necessaria, ma penso che la condizione per H (w) < w + ND (w) è ridondante, poiché è sempre garantito che sia vero (quando si fa il traversamento di preordine, tutti i vertici nel sottoalbero di w vengono visitati consecutivamente e numerati consecutivamente, e H (W) deve essere nel sottoalbero di w, rendendo H (W) < w + ND (W) sempre vero).

Quindi sono curioso di sapere se H (W) < La condizione w + ND (W) è addirittura necessaria e, in tal caso, puoi fornire un caso esemplificativo in cui è necessario?

graph graph-traversal

posta Lawrence 16.06.2014 - 10:02

fonte

1 risposta

Leggi altre domande sui tag graph graph-traversal

Modifica del codice sorgente e compatibilità GPLv3 Verifica dei token di accesso

score 1 · Answer 1

Il test L (), sì, gestisce cicli o cicli. Gestisce anche i collegamenti incrociati in rami non correlati nell'albero di copertura che si trovano a sinistra (o hanno un numero di preordine inferiore).

Ma ecco perché penso che tu abbia bisogno del test H (). Il test H () gestisce i collegamenti incrociati ai rami nell'albero di copertura non correlati e a destra (o con un numero di preordine superiore).

Ecco un esempio. Supponiamo che il tuo grafico sia:

  A
B   C
|   |
D - E

Dove lo spanning tree in forma di elenco è [A [B [D]] [C [E]]]. Ma c'è anche un cross-border da D a E che è giusto rispetto a D.

Si noti che H (D) sarà il valore di preordine per E, il numero più alto dell'albero spanning. Senza quel margine A-C sarebbe un ponte. Non è però a causa del test su H (D).