無向グラフがツリーであるかどうかを判断します

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の親ではありません（各ノードの親を維持する必要もあります）。隣接リストのサイズを合計して2で割ることにより、最後にエッジを数える方が良いかもしれません。

Answer 2

あなたはしたいです 深さの最初の検索. 。無向グラフには、背面のエッジとツリーエッジのみがあります。したがって、DFSアルゴリズムをコピーするだけで、バックエッジが見つかった場合はツリーではありません。