Determina se un grafico non indirizzato è un albero
-
27-10-2019 - |
Domanda
Ho scritto un algoritmo per determinare "se un grafico non diretto è un albero"
Presupposti: il grafico G è rappresentato come elenco di adiacenza, in cui conosciamo già il numero di vertici che è n
Is_graph_a_tree(G,1,n) /* using BFS */
{
-->Q={1} //is a Queue
-->An array M[1:n], such that for all i, M[i]=0 /* to mark visited vertices*/
-->M[1]=1
-->edgecount=0 // to determine the number of edges visited
-->While( (Q is not empty) and (edgecount<=n-1) )
{
-->i=dequeue(Q)
-->for each edge (i,j) and M[j] =0 and edgecount<=n-1
{
-->M[j]=1
-->Q=Q U {j}
-->edgecount++
}
}
If(edgecount != n-1)
--> print “G is not a tree”
Else
{
-->If there exists i such that M[i]==0
Print “ G is not a tree”
Else
Print “G is tree”
}
}
È giusto??
La complessità temporale di questo algoritmo Big0H (N) ??
Soluzione
Penso che il conteggio dei bordi non sia corretto. Dovresti anche contare i bordi (i, j) per Witch M [J] = 1 ma J non è il genitore di I (quindi dovresti anche mantenere il genitore di ciascun nodo). Forse è meglio contare i bordi alla fine, sommando le dimensioni degli elenchi di adiacenza e dividendo per 2.
Altri suggerimenti
Vuoi fare un Prima ricerca di profondità. Un grafico non diretto ha solo bordi e bordi degli alberi. Quindi puoi semplicemente copiare l'algoritmo DFS e se trovi un bordo posteriore, non è un albero.