图论相关算法

• DFS
• BFS
• Topological Sort
• Union-find
• Djikstra

Binary Search Tree

• inorder是有序的

DFS

一定要用visited set来辅助，避免在某条path中重复经过某点造成StackOverflow。

BFS

只要题目提到"最短"，就要优先想到BFS。
也需要visited set！

Dijkstra

基于BFS的变种，注意不需要visited set，因为某个节点会在不同的路径多次被访问到。
需要int[] dis记录已经找到最短路径的节点以及其对应的dis
https://leetcode.com/problems/the-maze-ii/description/

Union-Find

通常是基于int[] parent，图中的每个点是一个integer。
想想如果对于String做Union-Find怎么办呢？一个做法是对每个unique string赋一个id，用HashMap保存String到id的映射关系，就行了。
但仔细想来，不用id也行。我们只需要通过一种途径，似的可以找到每个String对应的Node即可。所以可以用HashMap保存String到Node的映射关系，然后用Node做Union-Find。
Node可以定义成类似这样：

    private class GraphNode{
        T value;
        GraphNode parent;

        GraphNode(T value){
            this.value = value;
            parent = this;
        }
    }

    private GraphNode root(GraphNode node){
        while (node != node.parent){
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }

具体参考"399. Evaluate Division"的Union-Find解法。