Undirected Graph, BFS

directed graph BFS 里靠 indegree = 0 判断加入队列；

undirected graph BFS 里靠 degree = 0 判断加入队列；

Minimum Height Trees

论坛里看到的，非常赞的思路。https://discuss.leetcode.com/topic/30572/share-some-thoughts

先说下自己一个 TLE 的初始尝试：根据所有 Edges 建 ArrayList[] 的 Graph，同时存每个点的 Adjacency lists，考虑到是无向图，对于每一个 edge 我们需要在两个 list 中更新才行。然后维护一个 HashMap<> 存着每一个 height 对应的 List<>，然后循环扫描每一个点作为起点进行 BFS，找到最小 height 之后 map.get(height) 就可以了。

然而这种做法的时间复杂度是 O(V * (E + V)) ，每个点都要扫整个 graph ，太高了。

转换一下思路，我们做的事情其实非常近似于Find Leaves of Binary Tree, 对于一个形状和链表一样的图，我们知道最优解一定是中点；对于一个 inorder traversal array，我们知道 height balanced tree 也一定以中点为 root;

在这个 graph 里，我们要找的，其实也是一层一层剥开最外围 nodes 之后，最里面的点。

因此，即使是 undirected graph，degree 也是非常重要的信息，只不过对于 undirected graph 来讲:

degree = "in"-degree + "out"-degree 而已.

AC代码，速度击败了 95.98 % ~

O(E + V)

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int[] degrees = new int[n];
        ArrayList[] graph = new ArrayList[n];

        for(int i = 0; i < n; i++){
            graph[i] = new ArrayList<>();
        }

        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < n; i++){
            if(degrees[i] <= 1) queue.offer(i);
        }

        List<Integer> list = new ArrayList<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                int node = queue.poll();
                list.add(node);
                for(int j = 0; j < graph[node].size(); j++){
                    int next = (int)graph[node].get(j);
                    degrees[next] --;
                    if(degrees[next] == 1) queue.offer(next);
                }
            }
        }

        return list;
    }

Graph Valid Tree

这题我之前写 union-find 的时候做过了，确实是更快更高效的写法。不过这题也完全可以用 Graph 上的常规 BFS / DFS 求解.

一个非常精炼的 BFS, DFS, Union-Find 做法总结帖子

这个题DFS和BFS检查两个事情

是否有环通过visited set
connected components是否是1, 或者一次遍历后count数目是否等于graph节点数量

Union Find 检查两个事情

是否有环; 对边进行union的时候check是否有两个节点的root一样
connected components==1

这题用 BFS 解需要解决这么几个问题：

如何正确 detect cycle?
- 常规 indegree 的话，如果有 cycle 会有一些点因为 indegree 无法进一步缩小的问题永远不被访问，可以记录 visited count;
- 另一种方法是，用 int[] 表示每个点的状态，其中
  - 0 代表“未访问”；
  - 1 代表“访问中”；
  - 2 代表“已访问”；
- 如果在循环的任何时刻，我们试图访问一个状态为 “1” 的节点，都可以说明图中有环。
如何正确识别图中 connected components 的数量?
- 添加任意点，探索所有能到达的点，探索完毕数量 +1；
- 如此往复，直到已探索点的数量 = # of V in graph 为止。

BFS 做法，时间复杂度 O(E + V);

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] states = new int[n];
        ArrayList[] graph = new ArrayList[n];

        for(int i = 0; i < n; i++){
            graph[i] = new ArrayList();
        }

        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(0); 
        states[0] = 1;
        int count = 0;

        while(!queue.isEmpty()){
            int node = queue.poll();
            count ++;
            for(int i = 0; i < graph[node].size(); i++){
                int next = (int) graph[node].get(i);

                if(states[next] == 1) return false ;
                else if(states[next] == 0){
                    states[next] = 1;
                    queue.offer(next);
                }
            }
            states[node] = 2;
        }

        return count == n;
    }
}

Clone Graph

DFS, 一次AC

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return node;
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        return dfs(node, map);
    }

    public UndirectedGraphNode dfs(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map){
        if(map.containsKey(node)) return map.get(node);
        map.put(node, new UndirectedGraphNode(node.label));
        UndirectedGraphNode copy = map.get(node);
        for(UndirectedGraphNode neighbor : node.neighbors){
            copy.neighbors.add(dfs(neighbor, map));
        }
        return copy;
    }

一次 AC ~ 由于不用考虑环和拓扑顺序，BFS 的方式就很简单，记录下看过哪些点就可以了。

参考了下论坛讨论之后，不太同意大多数解法，因为假设所有点的 label 唯一不是很适合 generalize 这个算法。用 HashMap<> 实现 Node - Node mapping 比较靠谱。

BFS分三步

对root节点建立copy, 加入queue
bfs过程中, 每次从queue中取出元素cur, 为cur建立neighbors关系
- neighbor copy已经存在, map.get()直接用
- neighbor copy不存在, 建立copy
对不存在新加入的neighbor, 加入queue. (存在copy的neighbor, 根据code, 我们一定已经建立过这个copy neighbor的关系了, 不用再考虑)

熟能生巧, 一次AC

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return node;
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();

        queue.offer(node); 
        UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 
        map.put(node, copy);

        while(!queue.isEmpty()){
            UndirectedGraphNode cur = queue.poll();
            copy = map.get(cur);

            for(UndirectedGraphNode neighbor : cur.neighbors){
                UndirectedGraphNode copyNeighbor = new UndirectedGraphNode(neighbor.label);
                if(map.containsKey(neighbor)) copyNeighbor = map.get(neighbor);
                copy.neighbors.add(copyNeighbor);
                if(!map.containsKey(neighbor)){
                    map.put(neighbor, copyNeighbor);
                    queue.add(neighbor);
                }
            }
        }

        return map.get(node);
    }

Copy List with Random Pointer

链表也是图啊，就是这么简单，轻松，愉快~~

这题还有一个比较妖孽的 follow-up，不让用 HashMap. 做法就是在每个节点后面插入新节点，最后再拆出来就行了，复杂度依然 O(n).

    public RandomListNode copyRandomList(RandomListNode head){
        if(head==null) return null;
        RandomListNode mover = head;
        //1st round
        while(mover!=null){
            RandomListNode copy = new RandomListNode(mover.label);
            copy.next = mover.next;
            mover.next = copy;
            mover = mover.next.next;
        }
        //2nd round
        mover = head;
        while(mover!=null){
            if(mover.random!=null){
                mover.next.random = mover.random.next;
            }
            mover = mover.next.next;
        }
        //3nd round extract
        RandomListNode copyHead = new RandomListNode(0);
        RandomListNode movercopy = copyHead;
        mover = head;
        while(mover!=null){
            RandomListNode next = mover.next.next;
            movercopy.next = mover.next;
            mover.next = next;
            movercopy = movercopy.next;
            mover = mover.next;
        }
        return copyHead.next;
    }

Undirected Graph, BFS

Undirected Graph, BFS

directed graph BFS 里靠 indegree = 0 判断加入队列；