> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/08_bfs.md).

# 广度优先BFS

常见的BFS用来解决什么问题？

* 简单树/图（有向无向皆可）的最短路径长度，注意是长度而不是具体的路径
* 拓扑排序
  * 一般用于解决有方向的图，non-directed graph不能用， 需要用union find或者普通的DFS/BFS
* 遍历一个图（或者树）
* use BFS for unweighted graphs and use Dijkstra's algorithm for weighted graphs. Dijkstra is similar to BFS, the difference is using priority queue instead of queue. The priority will pop the element with higher priority
* 复杂度
  * The time complexity will be O(V+E), each vertex will become a source only once and each edge will be accessed and removed once.
  * The space complexity will be O(V+E), since we are storing all of the edges for each vertex in an adjacency list

**基础**

* BFS基本模板（需要记录层数或者不需要记录层数）
* BFS和DFS都是一种N叉树的遍历，图有必要的时间记录是否被visited。**加入队列的时候**，立刻标记为被访问过
* 多数情况下时间复杂度空间复杂度都是O（N+M），N为节点个数，M为边的个数
* 有些题目既可以DFS也可以BFS，此时"用BFS更好还是DFS更好取决于树的形状是又高又窄还是又矮又宽"

## 一些trick

* 通过去掉leave nodes来实现图的bfs

## 基于树的BFS

不需要专门一个set来记录访问过的节点

```python
bfs = [target.val]
visited = set([target.val])
for k in range(K):
    bfs = [y for x in bfs for y in conn[x] if y not in visited]
    visited |= set(bfs)
```

## 基于图的bfs

* [207 Course Schedule](https://github.com/LongxingTan/mle-interview/blob/main/01_leetcode/08_bfs/207%20Course%20Schedule.md)
* [210. Course Schedule II](/mle-interview/01_leetcode/08_bfs/210.-course-schedule-ii.md)

```python
import collections

collections.defaultdict(list)
collections.defaultdict(set)
collections.defaultdict(dict)
collections.deque()
```

[1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/description/)

```python
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if not edges:
            return True

        graph = collections.defaultdict(list)
        visited = set()
        for (i, j) in edges:
            graph[i].append(j)  # 无向图两个方向都加入
            graph[j].append(i)

        nodes = collections.deque([source])
        visited.add(source)

        while nodes:
            i = nodes.popleft()
            i_next = graph[i]
            for node in i_next:
                if node == destination:
                    return True
                if node not in visited:
                    nodes.append(node)
                    visited.add(node)
        return False
```

[Find Longest Path in DAG](https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/)

```python
def topological_sort(V, adj):
    in_degree = [0] * V
    for u in range(V):
        for neighbor, _ in adj[u]:
            in_degree[neighbor] += 1

    queue = deque([i for i in range(V) if in_degree[i] == 0])
    top_order = []

    while queue:
        u = queue.popleft()
        top_order.append(u)
        for neighbor, _ in adj[u]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return top_order

def longest_path(V, adj, s):
    top_order = topological_sort(V, adj)  # Get topological order iteratively
    dist = [float('-inf')] * V
    dist[s] = 0

    for u in top_order:
        if dist[u] != float('-inf'):
            for neighbor, weight in adj[u]:
                dist[neighbor] = max(dist[neighbor], dist[u] + weight)

    print(" ".join(str(d) if d != float('-inf') else "INF" for d in dist))
```

## follow up

* graph类的BFS如何scale
* [BFS｜宽度优先搜索 题型技巧分类总结](https://www.1point3acres.com/bbs/forum.php?mod=viewthread\&tid=909366\&ctid=9)
* [How to trace the path in a Breadth-First Search?](https://stackoverflow.com/questions/8922060/how-to-trace-the-path-in-a-breadth-first-search)
* 如何打印最短路径/步数
  * python中，直接把path也传到queue里面，每次更新path


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://longxingtan.gitbook.io/mle-interview/01_leetcode/08_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.