Bestimmen Sie, ob ein ungerichteter Diagramm ein Baum ist
-
27-10-2019 - |
Frage
Ich habe einen Algorithmus geschrieben, um festzustellen, ob ein ungerichteter Diagramm ein Baum ist.
Annahmen: Graph G wird als Adjazenzliste dargestellt, in der wir bereits die Anzahl der Eckpunkte kennen, die n sind
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”
}
}
Ist es richtig??
Ist die Zeitkomplexität dieses Algorithmus Big0h (n) ??
Lösung
Ich denke, die Zählung von Kanten ist nicht korrekt. Sie sollten auch Kanten (i, j) für Hexe M [j] = 1 zählen, aber J ist nicht der Elternteil von I (Sie müssten also auch den Elternteil jedes Knotens behalten). Vielleicht ist es besser, die Kanten am Ende zu zählen, indem sie die Größen der Adjazenzlisten summieren und durch 2 dividieren.
Andere Tipps
Sie möchten eine machen Tiefe erste Suche. Eine ungerichtete Grafik hat nur Rückkanten und Baumkanten. Sie können also einfach den DFS -Algorithmus kopieren und wenn Sie eine Rückkante finden, ist es kein Baum.