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: le graphe G est représenté comme une liste d'adjacence, où l'on connaît 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 vrai?
La complexité temporelle de cet algorithme Big0h (n) ??

Answer 1

Je pense que le comptage des arêtes n'est pas correct. Vous devez également compter les arêtes (i, j) pour M [j] = 1 mais j n'est pas le parent de i (donc vous devrez également garder le parent de chaque nœud). Peut-être est préférable de compter les bords à la fin, en additionnant les tailles des listes d'adjacence et en divisant par 2.

Answer 2

Vous voulez faire un Depth First Search. Un graphe non orienté n'a que des arêtes arrière et des arêtes d'arbre. Vous pouvez donc simplement copier l'algorithme DFS et si vous trouvez un bord arrière, ce n'est pas un arbre.