は、無向グラフが木であるかどうかを決定する

Question

「無向グラフが木であるかどうか」を決定するアルゴリズムを書いた
前提：グラフ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）ですか？

Answer 1

私はエッジのカウントが正しくないと思います。また、魔女M [j] = 1ではエッジ（i、j）を数えますが、jはiの親ではありません（したがって、各ノードの親を保持する必要もあります）。 は多分隣接リストのサイズを合計すると、あなたがDepth First Searchをしたい2.

Answer 2

で割って、最後にエッジをカウントすることをお勧めします。無向グラフには、バックエッジとツリーエッジのみがあります。したがって、DFSアルゴリズムをコピーするだけで、後端が見つかった場合はツリーではありません。