Определите, является ли неисправный график деревом
-
27-10-2019 - |
Вопрос
Я написал алгоритм, чтобы определить «является ли неориентированный график деревом»
Допущения: график G представлен как список смежности, где мы уже знаем количество вершин, которое является 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”
}
}
Это правильно??
Является ли временная сложность этого алгоритма big0h (n) ??
Решение
Я думаю, что подсчет краев неверен. Вы также должны подсчитать края (i, j) для ведьмы M [j] = 1, но J не является родителем I (так что вам также нужно сохранить родитель каждого узла). Возможно, лучше подсчитать края в конце, суммируя размеры списков смежности и делясь на 2.
Другие советы
Вы хотите сделать Глубина первый поиск. Анкет Неправный график имеет только края задней части и края деревьев. Таким образом, вы можете просто скопировать алгоритм DFS, и если вы найдете задний край, то это не дерево.