图论基础#

图论是计算机科学中重要的研究领域，广泛应用于网络、社交媒体、交通等领域。
图由顶点（节点）和边（连接顶点的线段）组成。
图可以是有向图（边有方向）或无向图（边无方向）。
图的表示方法包括邻接矩阵、邻接表等。
图的基本操作包括遍历（深度优先搜索 DFS、广度优先搜索 BFS）、最短路径计算、最小生成树等。

深度优先搜索理论#

深度优先搜索（DFS）是一种遍历图的算法，从起始节点开始，尽可能深地搜索每个分支。
DFS 可以使用递归或栈实现。
时间复杂度为 $O(V + E)$ ，其中 $V$ 是顶点数， $E$ 是边数。
DFS 的应用包括拓扑排序、连通分量检测等。

1
def dfs(graph, start, visited=None):
2
    if visited is None:
3
        visited = set()
4
    visited.add(start)
5
    for neighbor in graph[start]:
6
        if neighbor not in visited:
7
            dfs(graph, neighbor, visited)
8
    return visited

广度优先搜索理论#

广度优先搜索（BFS）是一种遍历图的算法，从起始节点开始，先访问所有邻接节点，再逐层向外扩展。
BFS 使用队列实现。
时间复杂度同样为 $O(V + E)$。
BFS 的应用包括最短路径计算、连通分量检测等。

1
from collections import deque
2

3
def bfs(graph, start):
4
    visited = set()
5
    queue = deque([start])
6
    while queue:
7
        node = queue.popleft()
8
        if node not in visited:
9
            print("Visiting:", node)
10
            visited.add(node)
11
            for neighbor in graph.get(node, []):
12
                if neighbor not in visited:
13
                    queue.append(neighbor)
14
    return visited

卡码网：98. 所有可达路径#

题目链接

1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().split()
6
    n, m = int(data[0]), int(data[1])
7
    graph = [[] for _ in range(n + 1)]
8
    index = 2
9
    for _ in range(m):
10
        u = int(data[index])
11
        v = int(data[index + 1])
12
        graph[u].append(v)
13
        index += 2
14

15
    res = []
16
    path = []
17

18
    def dfs(node):
19
        path.append(node)
20
        if node == n:
21
            res.append(path[:])
22
        else:
23
            for neighbor in graph[node]:
24
                dfs(neighbor)
25
        path.pop()
26

27
    dfs(1)
28

29
    if not res:
30
        print(-1)
31
    else:
32
        for p in res:
33
            print(' '.join(map(str, p)))
34

35
if __name__ == "__main__":
36
    main()