图与搜索算法

图是数据结构中最通用、也最贴近现实世界的结构——社交网络、地图导航、依赖关系、网络拓扑都可以用图表示。图的算法体系庞大：遍历、最短路径、最小生成树、拓扑排序、并查集，每一类都是工程中的常用工具。本篇将从图的表示讲起，覆盖 DFS/BFS、Dijkstra/Floyd/Bellman-Ford 三大最短路算法、Kruskal/Prim 最小生成树、拓扑排序、并查集，最后用 LeetCode 真题收尾。这一篇内容较多，建议分块消化。

一、图的表示

图由顶点（Vertex）和边（Edge）组成。根据边是否有方向，分为有向图和无向图；根据边是否有权重，分为有权图和无权图。

1. 邻接矩阵

用 N×N 的二维数组表示，matrix[i][j] 表示从 i 到 j 的边（无权图用 0/1，有权图用权重）。

优点：查询边是否存在 O(1)。
缺点：空间 O(V²)，稀疏图浪费严重。

2. 邻接表

每个顶点维护一个列表，存所有相邻顶点。空间 O(V+E)，适合稀疏图。Go 中通常用 [][]int 或 map[int][]int。

package main

import "fmt"

// 邻接表表示无向图
type Graph struct {
	vertices int
	adj      [][]int
}

func NewGraph(v int) *Graph {
	return &Graph{
		vertices: v,
		adj:      make([][]int, v),
	}
}

func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u) // 无向图
}

func (g *Graph) Print() {
	for i := 0; i < g.vertices; i++ {
		fmt.Printf("%d: %v\n", i, g.adj[i])
	}
}

func main() {
	g := NewGraph(5)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.Print()
}

二、图的遍历

1. DFS（深度优先搜索）

DFS 用递归或显式栈，一路走到底再回溯。常用于连通分量、环检测、路径搜索。

package main

import "fmt"

type Graph struct {
	vertices int
	adj      [][]int
}

func NewGraph(v int) *Graph {
	return &Graph{vertices: v, adj: make([][]int, v)}
}

func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) DFS(start int) []int {
	visited := make(map[int]bool)
	var result []int
	var dfs func(int)
	dfs = func(u int) {
		visited[u] = true
		result = append(result, u)
		for _, v := range g.adj[u] {
			if !visited[v] {
				dfs(v)
			}
		}
	}
	dfs(start)
	return result
}

func main() {
	g := NewGraph(6)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 5)
	fmt.Println("DFS from 0:", g.DFS(0))
}

2. BFS（广度优先搜索）

BFS 用队列，逐层扩展。常用于无权图最短路径、层序遍历。

package main

import "fmt"

type Graph struct {
	vertices int
	adj      [][]int
}

func NewGraph(v int) *Graph {
	return &Graph{vertices: v, adj: make([][]int, v)}
}

func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) BFS(start int) []int {
	visited := make(map[int]bool)
	var result []int
	queue := []int{start}
	visited[start] = true
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		result = append(result, u)
		for _, v := range g.adj[u] {
			if !visited[v] {
				visited[v] = true
				queue = append(queue, v)
			}
		}
	}
	return result
}

func main() {
	g := NewGraph(6)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 5)
	fmt.Println("BFS from 0:", g.BFS(0))
}

DFS 适合「找所有解 / 检测环 / 连通性」，BFS 适合「最短步数 / 层序」。BFS 的 visited 必须在入队时标记，而非出队时，否则会重复入队。

三、最短路径算法

1. Dijkstra 算法

求单源最短路径，要求边权非负。用贪心 + 优先队列：每次取距离最小的未确定顶点，松弛其邻边。O((V+E) log V) 用堆优化。

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	to     int
	weight int
}

type Graph struct {
	vertices int
	adj      [][]Edge
}

func NewGraph(v int) *Graph {
	return &Graph{vertices: v, adj: make([][]Edge, v)}
}

func (g *Graph) AddEdge(from, to, w int) {
	g.adj[from] = append(g.adj[from], Edge{to, w})
}

type Item struct {
	node int
	dist int
}

type MinHeap []Item

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func (g *Graph) Dijkstra(start int) []int {
	dist := make([]int, g.vertices)
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[start] = 0
	h := &MinHeap{}
	heap.Init(h)
	heap.Push(h, Item{start, 0})
	for h.Len() > 0 {
		cur := heap.Pop(h).(Item)
		if cur.dist > dist[cur.node] {
			continue // 已有更优解
		}
		for _, e := range g.adj[cur.node] {
			newDist := dist[cur.node] + e.weight
			if newDist < dist[e.to] {
				dist[e.to] = newDist
				heap.Push(h, Item{e.to, newDist})
			}
		}
	}
	return dist
}

func main() {
	g := NewGraph(5)
	g.AddEdge(0, 1, 4)
	g.AddEdge(0, 2, 1)
	g.AddEdge(2, 1, 2)
	g.AddEdge(1, 3, 1)
	g.AddEdge(2, 3, 5)
	g.AddEdge(3, 4, 3)
	dist := g.Dijkstra(0)
	fmt.Println("从 0 出发最短路:", dist)
}

2. Floyd-Warshall 算法

求所有点对最短路径，支持负权边（不能有负环）。动态规划思想：dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])，三重循环 O(V³)。

package main

import "fmt"

func floyd(dist [][]int) [][]int {
	n := len(dist)
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] = dist[i][k] + dist[k][j]
				}
			}
		}
	}
	return dist
}

func main() {
	const INF = 1 << 30
	dist := [][]int{
		{0, 4, 1, INF},
		{INF, 0, INF, 1},
		{INF, 2, 0, 5},
		{INF, INF, INF, 0},
	}
	result := floyd(dist)
	for _, row := range result {
		fmt.Println(row)
	}
}

3. Bellman-Ford 算法

求单源最短路径，支持负权边，能检测负环。对所有边松弛 V-1 轮，若第 V 轮仍能松弛则存在负环。O(VE)。

package main

import "fmt"

type Edge struct {
	from, to, weight int
}

func bellmanFord(n int, edges []Edge, start int) ([]int, bool) {
	const INF = 1 << 30
	dist := make([]int, n)
	for i := range dist {
		dist[i] = INF
	}
	dist[start] = 0
	// 松弛 n-1 轮
	for i := 0; i < n-1; i++ {
		updated := false
		for _, e := range edges {
			if dist[e.from] != INF && dist[e.from]+e.weight < dist[e.to] {
				dist[e.to] = dist[e.from] + e.weight
				updated = true
			}
		}
		if !updated {
			break
		}
	}
	// 检测负环
	for _, e := range edges {
		if dist[e.from] != INF && dist[e.from]+e.weight < dist[e.to] {
			return nil, false // 存在负环
		}
	}
	return dist, true
}

func main() {
	edges := []Edge{
		{0, 1, 4}, {0, 2, 1}, {2, 1, 2},
		{1, 3, 1}, {2, 3, 5},
	}
	dist, ok := bellmanFord(4, edges, 0)
	if ok {
		fmt.Println("Bellman-Ford 结果:", dist)
	} else {
		fmt.Println("存在负环")
	}
}

四、最小生成树

最小生成树（MST）是连通无向图中边权之和最小的生成树。两种经典算法：

1. Kruskal 算法

按边权排序，从小到大加入不构成环的边，用并查集判环。O(E log E)。

package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	u, v, weight int
}

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUF(n int) *UnionFind {
	uf := &UnionFind{parent: make([]int, n), rank: make([]int, n)}
	for i := range uf.parent {
		uf.parent[i] = i
	}
	return uf
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
	px, py := uf.Find(x), uf.Find(y)
	if px == py {
		return false
	}
	if uf.rank[px] < uf.rank[py] {
		px, py = py, px
	}
	uf.parent[py] = px
	if uf.rank[px] == uf.rank[py] {
		uf.rank[px]++
	}
	return true
}

func kruskal(n int, edges []Edge) (int, []Edge) {
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})
	uf := NewUF(n)
	totalWeight := 0
	var mst []Edge
	for _, e := range edges {
		if uf.Union(e.u, e.v) {
			mst = append(mst, e)
			totalWeight += e.weight
		}
	}
	return totalWeight, mst
}

func main() {
	edges := []Edge{
		{0, 1, 4}, {0, 2, 1}, {0, 3, 3},
		{1, 2, 2}, {2, 3, 5}, {1, 3, 6},
	}
	w, mst := kruskal(4, edges)
	fmt.Println("MST 权重:", w)
	fmt.Println("MST 边:", mst)
}

2. Prim 算法

从一个点出发，每次选「连接已选集合和未选集合」的最小边，用优先队列优化 O(E log V)。

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	to, weight int
}

type Item struct {
	to, weight int
}

type MinHeap []Item

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].weight < h[j].weight }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func prim(adj [][]Edge, n int) int {
	visited := make([]bool, n)
	totalWeight := 0
	h := &MinHeap{}
	heap.Init(h)
	heap.Push(h, Item{0, 0})
	for h.Len() > 0 {
		cur := heap.Pop(h).(Item)
		if visited[cur.to] {
			continue
		}
		visited[cur.to] = true
		totalWeight += cur.weight
		for _, e := range adj[cur.to] {
			if !visited[e.to] {
				heap.Push(h, Item{e.to, e.weight})
			}
		}
	}
	return totalWeight
}

func main() {
	n := 4
	adj := make([][]Edge, n)
	add := func(u, v, w int) {
		adj[u] = append(adj[u], Edge{v, w})
		adj[v] = append(adj[v], Edge{u, w})
	}
	add(0, 1, 4)
	add(0, 2, 1)
	add(0, 3, 3)
	add(1, 2, 2)
	add(2, 3, 5)
	fmt.Println("Prim MST 权重:", prim(adj, n))
	_ = math.MaxInt
}

五、拓扑排序

拓扑排序针对有向无环图（DAG），把所有顶点排成线性序列，使得所有边的方向一致。常用于任务依赖、编译顺序。

1. Kahn 算法（BFS）

维护入度，每次取入度为 0 的顶点，相邻顶点入度减 1。若结果序列长度小于顶点数，说明有环。

package main

import "fmt"

func kahnSort(n int, edges [][]int) []int {
	adj := make([][]int, n)
	inDegree := make([]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		inDegree[e[1]]++
	}
	var queue []int
	for i := 0; i < n; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}
	var result []int
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		result = append(result, u)
		for _, v := range adj[u] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(result) != n {
		return nil // 有环
	}
	return result
}

func main() {
	edges := [][]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}}
	fmt.Println("拓扑排序:", kahnSort(5, edges))
}

2. DFS 实现

DFS 后序逆序即为拓扑序列。访问到「正在访问」状态的节点说明有环。

package main

import "fmt"

func dfsTopSort(n int, edges [][]int) []int {
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
	}
	// 0:未访问 1:访问中 2:已完成
	state := make([]int, n)
	var result []int
	var hasCycle bool
	var dfs func(u int)
	dfs = func(u int) {
		if hasCycle {
			return
		}
		state[u] = 1
		for _, v := range adj[u] {
			if state[v] == 1 {
				hasCycle = true
				return
			}
			if state[v] == 0 {
				dfs(v)
			}
		}
		state[u] = 2
		result = append(result, u) // 后序
	}
	for i := 0; i < n; i++ {
		if state[i] == 0 {
			dfs(i)
		}
	}
	if hasCycle {
		return nil
	}
	// 逆序
	for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
		result[i], result[j] = result[j], result[i]
	}
	return result
}

func main() {
	edges := [][]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}}
	fmt.Println("DFS 拓扑:", dfsTopSort(5, edges))
}

六、并查集（Union-Find）

并查集用于「动态连通性」问题：合并两个集合、查询两个元素是否同属一个集合。配合路径压缩 + 按秩合并，单次操作接近 O(1)。

package main

import "fmt"

type UnionFind struct {
	parent []int
	rank   []int
	count  int // 连通分量数
}

func NewUF(n int) *UnionFind {
	uf := &UnionFind{
		parent: make([]int, n),
		rank:   make([]int, n),
		count:  n,
	}
	for i := range uf.parent {
		uf.parent[i] = i
	}
	return uf
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
	px, py := uf.Find(x), uf.Find(y)
	if px == py {
		return false
	}
	// 按秩合并
	if uf.rank[px] < uf.rank[py] {
		px, py = py, px
	}
	uf.parent[py] = px
	if uf.rank[px] == uf.rank[py] {
		uf.rank[px]++
	}
	uf.count--
	return true
}

func (uf *UnionFind) Connected(x, y int) bool {
	return uf.Find(x) == uf.Find(y)
}

func (uf *UnionFind) Count() int { return uf.count }

func main() {
	uf := NewUF(6)
	uf.Union(0, 1)
	uf.Union(2, 3)
	uf.Union(1, 2)
	fmt.Println("0 和 3 连通?", uf.Connected(0, 3)) // true
	fmt.Println("0 和 4 连通?", uf.Connected(0, 4)) // false
	fmt.Println("连通分量数:", uf.Count())          // 3
}

并查集应用：连通分量、Kruskal 最小生成树、判断无向图是否有环、朋友圈/省份数量。

七、LeetCode 经典题解析

1. 岛屿数量（LC 200）

题目：二维网格中 '1' 是陆地，'0' 是水，求岛屿数量。

思路：遍历每个格子，遇到 '1' 就 DFS/BFS 把整个连通块标为已访问，计数加一。

package main

import "fmt"

func numIslands(grid [][]byte) int {
	if len(grid) == 0 {
		return 0
	}
	rows, cols := len(grid), len(grid[0])
	count := 0
	var dfs func(int, int)
	dfs = func(r, c int) {
		if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
			return
		}
		grid[r][c] = '2' // 标记已访问
		dfs(r-1, c)
		dfs(r+1, c)
		dfs(r, c-1)
		dfs(r, c+1)
	}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == '1' {
				count++
				dfs(r, c)
			}
		}
	}
	return count
}

func main() {
	grid := [][]byte{
		{'1', '1', '0', '0', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '1', '0', '0'},
		{'0', '0', '0', '1', '1'},
	}
	fmt.Println("岛屿数量:", numIslands(grid)) // 3
}

2. 课程表（LC 207）

题目：共有 numCourses 门课，prerequisites 给出依赖关系，判断能否完成所有课程。

思路：本质是判断有向图是否有环，用拓扑排序（Kahn 或 DFS）。

package main

import "fmt"

func canFinish(numCourses int, prerequisites [][]int) bool {
	adj := make([][]int, numCourses)
	inDegree := make([]int, numCourses)
	for _, p := range prerequisites {
		adj[p[1]] = append(adj[p[1]], p[0])
		inDegree[p[0]]++
	}
	var queue []int
	for i := 0; i < numCourses; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}
	count := 0
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		count++
		for _, v := range adj[u] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	return count == numCourses
}

func main() {
	fmt.Println("能完成 2 门:", canFinish(2, [][]int{{1, 0}}))        // true
	fmt.Println("能完成 2 门:", canFinish(2, [][]int{{1, 0}, {0, 1}})) // false
}

3. 网络延迟时间（LC 743）

题目：从节点 k 发送信号到所有节点，求全部收到的时间（即最远的最短路径）。

思路：单源最短路径，Dijkstra，答案是最短路径中的最大值。

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	to, weight int
}

type Item struct {
	node, dist int
}

type MinHeap []Item

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func networkDelayTime(times [][]int, n int, k int) int {
	adj := make([][]Edge, n+1)
	for _, t := range times {
		adj[t[0]] = append(adj[t[0]], Edge{t[1], t[2]})
	}
	dist := make([]int, n+1)
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[k] = 0
	h := &MinHeap{}
	heap.Init(h)
	heap.Push(h, Item{k, 0})
	for h.Len() > 0 {
		cur := heap.Pop(h).(Item)
		if cur.dist > dist[cur.node] {
			continue
		}
		for _, e := range adj[cur.node] {
			if dist[cur.node]+e.weight < dist[e.to] {
				dist[e.to] = dist[cur.node] + e.weight
				heap.Push(h, Item{e.to, dist[e.to]})
			}
		}
	}
	maxDist := 0
	for i := 1; i <= n; i++ {
		if dist[i] == math.MaxInt {
			return -1
		}
		if dist[i] > maxDist {
			maxDist = dist[i]
		}
	}
	return maxDist
}

func main() {
	times := [][]int{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}
	fmt.Println("网络延迟:", networkDelayTime(times, 4, 2)) // 2
}

八、复杂度分析

算法	时间复杂度	空间复杂度	适用场景
DFS/BFS	O(V+E)	O(V)	遍历、连通性
Dijkstra	O((V+E) log V)	O(V)	非负权单源最短路
Bellman-Ford	O(VE)	O(V)	含负权单源最短路
Floyd-Warshall	O(V³)	O(V²)	所有点对最短路
Kruskal	O(E log E)	O(V)	最小生成树
Prim	O(E log V)	O(V)	最小生成树
拓扑排序	O(V+E)	O(V)	DAG 排序
并查集	近 O(1) 单次	O(V)	动态连通性

九、小结

图是数据结构中应用最广的章节，本篇要点：

图的表示：邻接矩阵 O(V²) 空间适合稠密图；邻接表 O(V+E) 适合稀疏图，工程中更常用。
DFS 用递归/栈，适合连通性、环检测、所有路径；BFS 用队列，适合无权最短路、层序。BFS 的 visited 必须入队时标记。
Dijkstra 用堆 + 贪心，要求非负权；Bellman-Ford 松弛 V-1 轮，支持负权并能检测负环；Floyd 三重循环求所有点对，支持负权。
Kruskal 按边排序 + 并查集，Prim 从一点扩展 + 优先队列，都求最小生成树。
拓扑排序只对 DAG 有效：Kahn 用入度 + BFS，DFS 用后序逆序。结果长度小于顶点数即有环。
并查集配合路径压缩 + 按秩合并，单次操作接近 O(1)，是连通性问题的首选。

图的代码量大、边界多，建议把岛屿数量、课程表、网络延迟时间三题作为模板题反复练习。下一篇我们回到相对简单的排序算法，把各种排序的思路、复杂度、稳定性一次性梳理清楚。

入门篇

进阶篇

资深篇

图与搜索算法

一、图的表示

1. 邻接矩阵

2. 邻接表

二、图的遍历

1. DFS（深度优先搜索）

2. BFS（广度优先搜索）

三、最短路径算法

1. Dijkstra 算法

2. Floyd-Warshall 算法

3. Bellman-Ford 算法

四、最小生成树

1. Kruskal 算法

2. Prim 算法

五、拓扑排序

1. Kahn 算法（BFS）

2. DFS 实现

六、并查集（Union-Find）

七、LeetCode 经典题解析

1. 岛屿数量（LC 200）

2. 课程表（LC 207）

3. 网络延迟时间（LC 743）

八、复杂度分析

九、小结

图与搜索算法 ​

一、图的表示 ​

1. 邻接矩阵 ​

2. 邻接表 ​

二、图的遍历 ​

1. DFS（深度优先搜索） ​

2. BFS（广度优先搜索） ​

三、最短路径算法 ​

1. Dijkstra 算法 ​

2. Floyd-Warshall 算法 ​

3. Bellman-Ford 算法 ​

四、最小生成树 ​

1. Kruskal 算法 ​

2. Prim 算法 ​

五、拓扑排序 ​

1. Kahn 算法（BFS） ​

2. DFS 实现 ​

六、并查集（Union-Find） ​

七、LeetCode 经典题解析 ​

1. 岛屿数量（LC 200） ​

2. 课程表（LC 207） ​

3. 网络延迟时间（LC 743） ​

八、复杂度分析 ​

九、小结 ​

图与搜索算法

一、图的表示

1. 邻接矩阵

2. 邻接表

二、图的遍历

1. DFS（深度优先搜索）

2. BFS（广度优先搜索）

三、最短路径算法

1. Dijkstra 算法

2. Floyd-Warshall 算法

3. Bellman-Ford 算法

四、最小生成树

1. Kruskal 算法

2. Prim 算法

五、拓扑排序

1. Kahn 算法（BFS）

2. DFS 实现

六、并查集（Union-Find）

七、LeetCode 经典题解析

1. 岛屿数量（LC 200）

2. 课程表（LC 207）

3. 网络延迟时间（LC 743）

八、复杂度分析

九、小结