# Undirected Graph, BFS

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

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

## [Minimum Height Trees](https://leetcode.com/problems/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 ](https://leetcode.com/problems/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)

```java
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](https://leetcode.com/problems/graph-valid-tree/)

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

#### [一个非常精炼的 BFS, DFS, Union-Find 做法总结帖子](https://discuss.leetcode.com/topic/35515/share-my-25-line-dfs-20-line-bfs-and-clean-union-find-java-solutions)

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

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

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

```java
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](https://leetcode.com/problems/clone-graph/)

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

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

下面的代码简化了一下，参考了九章的写法，先用一个 getNodes 函数返回所有的节点(因为函数就给了一个)，在返回的时候直接 new ArrayList<>(set) 调用 Collection constructor.

这样算法逻辑就分成两步：

* 过一遍所有节点，建新节点放到 HashMap 中；
* 再过一遍所有节点，这次更新每个对应节点的 neighbors.

```java
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return node;

        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

        List<UndirectedGraphNode> nodeList = getNodes(node);

        for(UndirectedGraphNode cur : nodeList){
            map.put(cur, new UndirectedGraphNode(cur.label));
        }

        for(UndirectedGraphNode cur : nodeList){
            UndirectedGraphNode copy = map.get(cur);

            for(UndirectedGraphNode neighbor : cur.neighbors){
                copy.neighbors.add(map.get(neighbor));
            }
        }

        return map.get(node);
    }

    private List<UndirectedGraphNode> getNodes(UndirectedGraphNode node){
        Set<UndirectedGraphNode> visited = new HashSet<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();

        queue.offer(node);
        visited.add(node);

        while(!queue.isEmpty()){
            UndirectedGraphNode cur = queue.poll();
            for(UndirectedGraphNode next : cur.neighbors){
                if(!visited.contains(next)){
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }

        return new ArrayList<>(visited);
    }
}
```

## [Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)

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

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

```java
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();

        RandomListNode cur;

        for(cur = head; cur != null; cur = cur.next){
            map.put(cur, new RandomListNode(cur.label));
        }

        for(cur = head; cur != null; cur = cur.next){
            RandomListNode copy = map.get(cur);

            copy.random = map.get(cur.random);
            copy.next = map.get(cur.next);
        }

        return map.get(head);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/topological_sortff0c_tuo_pu_pai_xu/undirected_graph-_bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.