determine whether an undirected graph is a tree

Question

I have written an algorithm to determine "whether an undirected graph is a tree"
Assumptions : graph G is represented as adjacency list, where we already know the number of vertices which is 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”
            }
     }

Is it right??
Is the time complexity of this algorithm Big0h(n)??

Answer 1

I think the counting of edges is not correct. You should also count edges (i,j) for witch M[j]=1 but j is not the parent of i (so you would also need to keep the parent of each node). Maybe is better to count the edges at the end, by summing the sizes of the adjacency lists and dividing by 2.

Answer 2

You want to do a Depth First Search. An undirected graph has only back edges and tree edges. So you can just copy the DFS algorithm and if you find a back edge then it's not a tree.