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?

score 7 · Answer 1 · answered Dec 04 '12 at 05:13

7

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.

answered Dec 04 '12 at 05:13

Roman Dzhabarov

521
4
10

2

Sure, but in order for DFS or BFS to terminate on a graph that may contain cycles, you will need to record somewhere whether each vertex has already been visited -- and if you see a previously-visited vertex, you already know the graph has a cycle, without having to count edges! :-P – j_random_hacker Dec 05 '12 at 19:57
Just checking that graph doesn't have cycles is not sufficient. Suppose you have isolated verticies or several connected components. – Roman Dzhabarov Dec 05 '12 at 20:03
Absolutely agree with the >>will need to record somewhere whether each vertex has already been visited. If you have knowlege of E and V in advance you may first just check E + 1 == V if not even do not do traversing. – Roman Dzhabarov Dec 05 '12 at 20:05
When did I say that DFS/BFS should only be run on one component? As with your solution, it needs to be run on each component. – j_random_hacker Dec 05 '12 at 20:06
:-) ok, I'm fine with do dfs(anyvertex); and then if no cycles and all visited => tree, otherwise not. – Roman Dzhabarov Dec 05 '12 at 20:14
In DFS you can check for back-edges. Use a counter and increase for pre-vertex visit on entering and increase on post-vertex visit on exiting. On completion of DFS, if an edge (u,v) exists where pre(u) > pre(v) and post(u) < post(v) you have a backedge, and therefore a cycle. O(|V| + |E|). – JStrahl Dec 19 '13 at 09:41

score 6 · Accepted Answer · edited May 23 '17 at 12:03

6

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.

edited May 23 '17 at 12:03

Community

1
1

answered Dec 04 '12 at 00:18

RonaldBarzell

3,822
1
16
23

If the graph is undirected, this will not work. Using BFS and counting distance, while traversing we can eliminate nodes which are 1 distance away and add the rest to the queue. Now checking to see if the node was visited will suffice. – Pradeep Feb 13 '20 at 12:41

Juan Lopes · Answer 3 · 2012-12-05T18:05:24.760

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
'''

Algorithm to determine if a graph is a tree

3 Answers3