Determinar si un gráfico no dirigido es un árbol
-
27-10-2019 - |
Pregunta
He escrito un algoritmo para determinar "si un gráfico no dirigido es un árbol"
Suposiciones: Graph G se representa como Lista de adyacencia, donde ya sabemos el número de vértices que es 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”
}
}
¿¿Es correcto??
¿Es la complejidad del tiempo de este algoritmo Big0H (N)?
Solución
Creo que el conteo de bordes no es correcto. También debe contar los bordes (i, j) para la bruja m [j] = 1 pero j no es el padre de I (por lo que también necesitaría mantener al padre de cada nodo). Tal vez sea mejor contar los bordes al final, sumando los tamaños de las listas de adyacencia y dividiendo por 2.
Otros consejos
Quieres hacer un Primera búsqueda de profundidad. Un gráfico no dirigido solo tiene bordes traseros y bordes de árboles. Por lo tanto, puede copiar el algoritmo DFS y si encuentra un borde posterior, entonces no es un árbol.