判断图是否为树

题目

输入二维数组，a[i][j]=1 表示从i结点指向j结点。

eg1

0 1 1 0

1 0 0 1

1 0 0 0

0 1 0 0

是一棵树，树为：

       a
       
      /  \
      
    b    c
    
  /
  
d

eg2

0 1 1 0

1 0 0 1

1 0 1 0

0 1 1 0

不是一颗树，是有环(a-b-d-c-a)的图：

       a
       
      /  \
      
    b    c
    
  /      /
  
d  - — -

关键点

判断一张图是否是一颗树的两个关键点：

• 不存在环路(对于有向图，不存在环路也就意味着不存在强连通子图)
• 满足边数加一等于顶点数的规律(不考虑重边和指向自身的边)

方法

1. DFS

2. 如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。时间复杂度O(ve)，v是顶点数，e是边数。

   第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

   第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点，则存在环，否则没有环。这个复杂度也很高

3. 结合树的特性(边数+1 = 顶点数)和并查集来做，代码见下文。

实现

import java.util.ArrayList;
import java.util.List;

public class TreeJudgeUnionB {
    private static class Edge {
        int start;
        int end;

        public Edge(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    // the number of edges
    private int n;

    // edge list
    private List<Edge> edges = new ArrayList<>();

    // the index of group
    private int[] group;

    // the size of tree
    private int[] size;

    public TreeJudgeUnionB(int n, List<Edge> edges) {
        this.n = n;
        this.edges = edges;

        group = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            group[i] = i;
            size[i] = 1;
        }
    }

    private int find(int i) {
        // find the root of a tree which contains i node
        while (i != group[i]) {
            i = group[i];
        }

        return i;
    }

    private boolean union(int groupI, int groupJ) {
        int iRoot = find(groupI);
        int jRoot = find(groupJ);
        if (iRoot != jRoot) {
            if (size[iRoot] < size[jRoot]) {
                group[iRoot] = jRoot;
                size[jRoot] += size[iRoot];
            } else {
                group[jRoot] = iRoot;
                size[iRoot] += size[jRoot];
            }

            return true;
        } else {
            return false;
        }
    }

    public boolean isTree() {
        for (Edge edge : edges) {
            if (!union(edge.start, edge.end)) {
                System.out.println("input two nodes in the same tree");
                return false;
            }
        }

        boolean hasRoot = false;
        for (int i = 0; i < group.length; i++) {
            if (i == group[i]) {
                if (!hasRoot) {
                    hasRoot = true;
                } else {
                    System.out.println("exist more than one tree root");
                    return false;
                }
            }
        }

        printGroup();

        return hasRoot;

    }

    public void printGroup() {
        for (int i = 0; i < n; i++) {
            System.out.print(group[i] + ", ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        int n = 5;
        List<Edge> edges = new ArrayList<>();
        addEdge(edges, 0, 1);
        addEdge(edges, 0, 2);
        addEdge(edges, 2, 3);
        addEdge(edges, 2, 4);
        isTree(n, edges); // true

        n = 5;
        edges.clear();
        addEdge(edges, 0, 1);
        addEdge(edges, 1, 2);
        addEdge(edges, 0, 2);
        addEdge(edges, 2, 3);
        addEdge(edges, 2, 4);
        isTree(n, edges); // false

        n = 4;
        edges.clear();
        addEdge(edges, 0, 1);
        addEdge(edges, 2, 3);
        isTree(n, edges);  // false

        n = 7;
        edges.clear();
        addEdge(edges, 0, 1);
        addEdge(edges, 1, 2);
        addEdge(edges, 4, 5);
        addEdge(edges, 3, 4);
        addEdge(edges, 2, 3);
        addEdge(edges, 0, 6);
        isTree(n, edges);  // true
    }

    protected static void addEdge(List<Edge> edges, int i, int j) {
        edges.add(new Edge(i, j));
    }

    protected static void isTree(int n, List<Edge> edges) {
        TreeJudgeUnionB treeJudgeUnionA = new TreeJudgeUnionB(n, edges);

        boolean isTree = treeJudgeUnionA.isTree();

        System.out.println("This is a tree? " + isTree);
    }
}