déterminer si un graphe non orienté est un arbre

Question

J'ai écrit un algorithme pour déterminer « si un graphe non orienté est un arbre »
Hypothèses: graphe G est représenté comme liste de contiguïté, où nous connaissons déjà le nombre de sommets qui est 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”
            }
     }

Est-il juste ??
La complexité temporelle de cet algorithme Big0h (n) ??

Answer 1

Je pense que le comptage des bords est incorrect. Vous devez également compter les bords (i, j) pour M sorcière [j] = 1, mais j est pas le parent de i (vous devez également garder le parent de chaque nœud). Peut-être vaut mieux compter les bords à la fin, en additionnant les tailles des listes de contiguïté et en divisant par 2.

Answer 2

Vous voulez faire un profondeur Première recherche . Un graphe non orienté ne possède que des bords arrière et des bords d'arbres. Ainsi, vous pouvez simplement copier l'algorithme DFS et si vous trouvez un bord de l'époque, ce n'est pas un arbre.