Algorithm to determine if a graph is a tree

Question

What is a simple algorithm to determine if a graph, given as an adjacency matrix, is a tree?

Answer 1

A tree is a graph without cycles, so to detect if your graph is a tree, check to see if it has any cycles. This can be done by traversing the matrix, retaining a history of every visited node and upon visiting a node, checking to see if it was in the set of nodes visited.

Here's a previous SO post about detecting cycles. It's a starting point: How to detect if a directed graph is cyclic?

You can also study up on graph traversals and adjacency matrices, to give you a better grounding in what you need to do.

If after all of this, you still need help, you can post what you have so far.

Answer 2

You can count amount of edges (E) and amount of verticies (V) if E + 1 = V you can assume that it's a tree. You also need to check that there is one connected component. To figure out that it only contains one component you may use either DFS or BFS.

Answer 3

Some code (in Python):

def is_tree(G):
    n = len(G)
    M = [False]*n

    def dfs_tree(u, v):
        M[v] = True

        return all(w==u or not M[w] and dfs_tree(v, w) for w in range(n) if G[v][w])

    return dfs_tree(0, 0) and all(M)

print is_tree([
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0],
])

'''
 0-1 
 |
 2

 True
'''


print is_tree([
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
])

'''
 0-1 
 |/
 2 

 False
'''