判断有向或无向图是否为树

1. Overview

In graph theory, a tree is a special case of graphs. In this tutorial, we’ll explain how to check if a given graph forms a tree.

We’ll explain the concept of trees, and what it means for a graph to form a tree.

Also, we’ll discuss both directed and undirected graphs. Finally, we’ll present a simple comparison between the steps in both cases.

2. Tree Definition

We say that a graph forms a tree if the following conditions hold:

1. The tree contains a single node called the root of the tree. Therefore, we say that node is the parent of node if we reach from after starting to traverse the tree from the selected root. Similarly, we say that is a child of . It’s worth noting that we can choose multiple nodes as the root of the tree.
2. Each node, except the root, must have a single parent. In other words, each node must be reached only from its parent when traversing the tree starting from the root.
3. Starting from the root, we must be able to visit all the nodes of the tree. Therefore, the tree should always be connected.

However, the process of checking these conditions is different in the case of a directed or undirected graph. Therefore, we’ll discuss the algorithm of each graph type separately.

3. Directed Graphs

3.1. Checking Steps

In the case of directed graphs, we must perform a series of steps:

1. Find the root of the tree, which is the vertex with no incoming edges. If no node exists, then return . If more than one node exists, then the graph is not connected, and we should return as well.
2. Perform a DFS to check that each node has exactly one parent. If not, return .
3. Make sure that all nodes are visited. If the DFS check didn’t visit all nodes, then return .
4. Otherwise, the graph is a tree.

3.2. Check Algorithm

Let’s take a look at the algorithm to check whether a directed graph is a tree.

algorithm checkIfDirectedGraphIsTree(n, edges):
    // INPUT
    //   n = number of nodes
    //   edges = edges of the graph
    // OUTPUT
    //   true if the graph is a tree, false otherwise

    incomingEdges <- a collection of n zeroes
    for edge in edges:
        incomingEdges[edge.to] <- incomingEdges[edge.to] + 1

    numberOfRoots <- 0
    root <- null
    for u <- 1 to n:
        if incomingEdges[u] = 0:
            root <- u
            numberOfRoots <- numberOfRoots + 1

    if numberOfRoots != 1:
        return false

    visited <- [false for i in 1 to n]
    if not directedDFS(root, visited):
        return false

    for u <- 1 to n:
        if not visited[u]:
            return false

    return true

First, we iterate over all the edges and increase the number of incoming edges for the ending node of each edge () by one. Next, we find the root node that doesn’t have any incoming edges (step 1).

After that, we perform a DFS check (step 2) to make sure each node has exactly one parent (see the section below for the function). We pass the root node to start from, and the array filled with values. If the function returns , then the algorithm should return as well.

Finally, we check that all nodes are marked as visited (step 3) from the function. If the DFS check left some nodes without marking them as visited, then we return . Otherwise, we return .

The complexity of the discussed algorithm is , where is the number of vertices, and is the number of edges inside the graph.

3.3. DFS Check

To check that each node has exactly one parent, we perform a DFS check. Let’s take a look at the algorithm:

algorithm directedDFS(u, visited):
    // INPUT
    //   u = the node to start from
    //   visited = array for tracking visited nodes
    // OUTPUT
    //   true if each node has exactly one parent, false otherwise

    if visited[u] = true:
        return false

    visited[u] <- true
    for child in neighbors(u):
        result <- directedDFS(child, visited)
        if result = false:
            return false

    return true

First, we check whether we’ve visited the current node before. If so, we return . Otherwise, we mark this node as visited.

Next, we iterate over all the children of the current node and call the function recursively for each child. If some child causes the function to return , then we immediately return . Otherwise, the function returns .

The complexity of this algorithm is , where is the number of vertices, and is the number of edges inside the graph.

4. Undirected Graphs

4.1. Checking Steps

In the case of undirected graphs, we perform three steps:

1. Perform a DFS check from any node to make sure that each node has exactly one parent. If not, return .
2. Check that all nodes are visited. If the DFS check wasn’t able to visit all nodes, then return .
3. Otherwise, the graph is a tree.

4.2. Check Algorithm

Consider the algorithm to check whether an undirected graph is a tree:

algorithm checkIfUndirectedGraphIsTree(n):
    // INPUT
    //   n = number of nodes
    // OUTPUT
    //   true if the graph is a tree, false otherwise

    visited <- collection of n false values
    if not undirectedDFS(1, -1, visited):
        return false

    for u <- 1 to n:
        if not visited[u]:
            return false

    return true

First, we call the function (step 1) and pass the root node as the node with index 1. Also, we pass the parent node as -1, indicating that the root doesn’t have any parent node. We will pass the array filled with values as well. The algorithm for the function is seen in the next section.

If the function returns , then the algorithm should return . Otherwise, we check that all nodes are visited (step 2). If the DFS check didn’t visit some node, then we’d return .

Finally, if all the above conditions are met, then we return .

The complexity of the described algorithm is , where is the number of vertices, and is the number of edges inside the graph.

4.3. DFS Check

Let’s take a look at the DFS check algorithm for an undirected graph.

algorithm undirectedDFS(u, parent, visited):
    // INPUT
    //   u = the node to start from
    //   parent = the parent of node u
    //   visited = array for tracking visited nodes
    // OUTPUT
    //   true if the graph is a tree, false otherwise

    if visited[u] = true:
        return false

    visited[u] <- true
    for child in neighbors(u):
        if child != parent:
            result <- undirectedDFS(child, u, visited)
            if result = false:
                return false

    return true

The algorithm is fairly similar to the one discussed above for directed graphs. Firstly, we check to see if the current node has been visited before. If so, then we return immediately. Otherwise, we mark the current node as visited.

Secondly, we iterate over the children of the current node and call the function recursively for each child. However, in the case of undirected graphs, the edge from the parent is a bi-directional edge.

Therefore, we’ll get the parent as a child node of . In this case, we should ignore the parent node and not revisit it. The reason for this is that it will cause the algorithm to see that the parent is visited twice, although it wasn’t.

The complexity of the discussed algorithm is as well, where is the number of vertices, and is the number of edges inside the graph.

5. Comparison

Let’s take a simple comparison between the steps in both the directed and undirected graphs.

Step

Directed Graphs

Undirected Graphs

Choosing the Root

The root is the node with
no incoming edges.

Any node can be chosen
as the root.

DFS Check

No node must be visited
more than once.

No node must be visited
more than once.
Also, the parent shouldn’t be
considered as a child.

Connectivity Check

Check that all nodes are visited.

Check that all nodes are visited.

Time Complexity

6. Conclusion

In this tutorial, we discussed the idea of checking whether a graph forms a tree or not. First, we presented the general conditions for a graph to form a tree. Next, we discussed both the directed and undirected graphs and how to check whether they form a tree.

Finally, we provided a simple comparison between the two cases.