Graph

and Tree

1. A tree is an undirected graph in which any two vertices are connected by exactly one path.

2. Any connected graph who has n nodes with n-1 edges is a tree.

3. The degree of a vertex of a graph is the number of edges incident to the vertex.

4. A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.

5. A path graph is a tree with two or more vertices that is not branched at all. (a list)

6. A tree is called a rooted tree if one vertex has been designated the root.

7. The height of a rooted tree is the number of edges on the longest downward path between root and a leaf.

Topological Sorting

用于有前序依赖的排序

Prerequiste

1. 必须为有向无环图 （有环图无法进行拓扑排序）
2. 可以获得入度和出度

排序方法

每次找到入度为0的node，对其进行BFS，一般复杂度为O(n)，因为每个点只过一遍

1. 遍历整个图，构建一个node和入度组成的map?
2. 把入度为0的点加入Queue中（也需要遍历）
3. 从Queue中取点，然后把每个点的相应入度进行更新

Course Schedule

• BFS
  • 把课程看成图上的点，每个先决课程都会指向下一个课，这样通过行遍历一次，可以获取每个课程的入度inCounts
  • 所有入度为0的点，即为不需要任何先决课程的点。加入到队列中来。
  • 每次弹出一个点，则代表完成了这个课程，就可以再通过一次行遍历更新inCounts数组中的值。再遇到inCount为0的点。则加入到队列中来。
  • 在这个过程中，每弹出一个点，就记录可以完成的课程数。最后可以通过这个数，看是否所有课程都完成了。
• DFS
  • 找环的思路

public boolean canFinish(int numCourses, int[][] prerequisites) {

        if (numCourses <= 0) return false;
        if (prerequisites.length == 0 || prerequisites[0].length == 0) return true;

        int[] inCounts = new int[numCourses];
        Queue<Integer> queue = new LinkedList<Integer>();

        for (int i = 0; i < prerequisites.length; i++) {
            int ready = prerequisites[i][0];
            inCounts[ready]++;
        }

        for (int i = 0; i < numCourses; i++) {
            if (inCounts[i] == 0) {
                queue.offer(i);
            }
        }

        //use total to check
        int total = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            total++;
            //update inCounts
            for (int i = 0; i < prerequisites.length; i++) {
                int ready = prerequisites[i][0];
                int pre = prerequisites[i][1];

                if (pre == course) {
                    inCounts[ready]--;
                    if (inCounts[ready] == 0) {
                        queue.add(ready);
                    }
                }
            }
        }

        return total == numCourses;
    }

follow ups

• when prerequisites contains a lots
  • 因为prerequisites有可能很大，所以在Queue那个while循环里要尽量避免用，利用空间复杂度换时间，用一个二维数组来存放点之间的关系，这样的话就可以保证这个循环不会超过n次
  • 因为这个matrix数组只是单纯计算两个点之间是否存在依赖关系，所以可以用来判断，并且在BFS中，不需要去修改他们的关系，因为每个点只会被用到过一次

Minimum Height Tree

考虑一个简化的问题，如果这个graph是path graph，那么要找到MHT，只需要找到这个path graph的终点即可。所以用双指针的办法即可解决。 而对于graph来说，可以类似的，如果能找到leaves让他们同时向中间移动，并更新相应移动过的点的degree(topological Sorting)，如果遇到相遇的点，就保留其中一个。直到最后只剩下两个点或者有一个点出界了为止