Originariamente inviata da
Nikopol
Ciao,
immagina di avere un grafo con 5 vertici rappresentato da una lista di coppie (vertice, id).
Il primo ciclo inizializza id a 0 :
[(1,0),(2,0),(3,0)(4,0),(5,0)]
Supponiamo che il grafo non sia fortemente connesso ma i vertici 1,2 e 3 siano connessi così come 4 e 5
Simulando l'algoritmo avremo che
k == 1
Si entra nel ciclo for e alla prima iterazione si ha garanzia (per come abbiamo inizializzato gli id) di entrare nel if.
Dentro l'if si esegue una visita in profondita impostando a k, ovvero a 1, tutti gli id dei nodi connessi al vertice 1 (1, 2 e 3):
[(1,1),(2,1),(3,1)(4,0),(5,0)]
Al termine della DFS si incrementa k a 2
Si prosegue con il for; per i che vale 2 e 3 non si entra nell if, quindi non si fa niente.
Quando i vale 4, id vale di nuovo 0
Si entra nel if e si esegue di nuovo la DFS impostando id a 2 dei vertici connessi a 4 (4 e 5):
[(1,1),(2,1),(3,1)(4,2),(5,2)]
Al termine della DFS si incremente k a 3
prosegue il for ma non essendoci più vertici con id == 0 il ciclo termina con k == 3
Si restituisce k == 2 ovvero false, il grafo non è fortemente connesso.
Ipotizzando invece che il grafo sia fortemente connesso:
k==1
alla prima iterazione si entra nell'if
DFS imposta a k, ovvero a 1, gli id di tutti i vertici connessi al vertice 1, (tutti quanti):
[(1,1),(2,1),(3,1)(4,1),(5,1)]
Al termine della DFS k viene incrementato a 2
Prosegue il for ma questa volta nessun altro id vale 0 e quindi il for termina senza fare più niente
Si restituisce k == 2 ovvero true, il grafo è fortemente connesso
In altre parole k-1 indica quante componenti connesse hai trovato nel grafo; se ne hai trovata solo 1 (grafo fortemente connesso) allora k vale 2.
Permessi di invio
Rispondi quotando