图算法 (Graph Algorithms)

研究图结构数据的算法，解决最短路径、最小生成树、网络流等经典问题

图的基础知识

图 (Graph) 是由顶点 (Vertex) 和边 (Edge) 组成的数据结构，用于表示对象之间的关系。

图的分类

↔️

无向图

边没有方向，关系是双向的

➡️

有向图

边有方向，关系是单向的

🔢

加权图

边带有权重/代价数值

🔄

有环图

存在从某点回到自身的路径

图的存储方式

存储方式	空间复杂度	查询边	遍历邻居	适用场景
邻接矩阵	O(V²)	O(1)	O(V)	稠密图
邻接表	O(V+E)	O(degree)	O(degree)	稀疏图
边列表	O(E)	O(E)	O(E)	Kruskal 等算法

graph TD A[图算法] --> B[遍历算法] A --> C[最短路径] A --> D[最小生成树] A --> E[网络流] A --> F[拓扑排序] B --> B1[DFS 深度优先] B --> B2[BFS 广度优先] C --> C1[Dijkstra] C --> C2[Bellman-Ford] C --> C3[Floyd-Warshall] C --> C4[A*搜索] D --> D1[Prim] D --> D2[Kruskal] E --> E1[Ford-Fulkerson] E --> E2[Edmonds-Karp] E --> E3[Dinic] style A fill:#2c5282,color:#fff style B fill:#4299e1,color:#fff style C fill:#48bb78,color:#fff style D fill:#ed8936,color:#fff style E fill:#f56565,color:#fff style F fill:#9f7aea,color:#fff

Dijkstra 算法 - 单源最短路径

Dijkstra 算法用于在带权图中找到从起点到所有其他节点的最短路径，适用于权值为非负数的情况。

💡 核心思想

贪心策略 —— 每次选择距离起点最近且未访问的节点，更新其邻居的距离。

Dijkstra 算法可视化

准备开始 Dijkstra 算法演示

时间复杂度

O((V+E) log V)

空间复杂度

O(V)

适用条件

非负权边

🎯 Dijkstra

单源最短路径，贪心策略

时间: O((V+E) log V)

空间: O(V)

适用于非负权图，使用优先队列优化

🔄 Bellman-Ford

单源最短路径，可处理负权

时间: O(VE)

空间: O(V)

可检测负权环，适用于有负权边的图

📊 Floyd-Warshall

多源最短路径，动态规划

时间: O(V³)

空间: O(V²)

计算所有点对之间的最短路径

// Dijkstra 算法实现
function dijkstra(graph, start) {
    const n = graph.length;
    const dist = Array(n).fill(Infinity);
    const visited = Array(n).fill(false);
    const prev = Array(n).fill(-1);
    
    dist[start] = 0;
    
    for (let i = 0; i < n; i++) {
        // 找到未访问的最小距离节点
        let u = -1;
        for (let v = 0; v < n; v++) {
            if (!visited[v] && (u === -1 || dist[v] < dist[u])) {
                u = v;
            }
        }
        
        if (dist[u] === Infinity) break;
        visited[u] = true;
        
        // 更新邻居节点
        for (const [v, weight] of graph[u]) {
            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
            }
        }
    }
    
    return { dist, prev };
}

// 使用优先队列优化的版本
function dijkstraPQ(graph, start) {
    const n = graph.length;
    const dist = Array(n).fill(Infinity);
    const prev = Array(n).fill(-1);
    const pq = new PriorityQueue();
    
    dist[start] = 0;
    pq.push(start, 0);
    
    while (!pq.isEmpty()) {
        const u = pq.pop();
        
        for (const [v, weight] of graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
                pq.push(v, dist[v]);
            }
        }
    }
    
    return { dist, prev };
}

// 简单优先队列实现
class PriorityQueue {
    constructor() {
        this.items = [];
    }
    
    push(element, priority) {
        this.items.push({ element, priority });
        this.items.sort((a, b) => a.priority - b.priority);
    }
    
    pop() {
        return this.items.shift().element;
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
}

// 测试
const graph = [
    [[1, 4], [2, 2]],      // 节点 0
    [[0, 4], [2, 5], [3, 10]],  // 节点 1
    [[0, 2], [1, 5], [3, 3]],   // 节点 2
    [[1, 10], [2, 3]]      // 节点 3
];
console.log(dijkstra(graph, 0));
// dist: [0, 4, 2, 5]

import heapq

def dijkstra(graph, start):
    """
    Dijkstra 算法 - 优先队列优化版本
    graph: 邻接表，graph[u] = [(v, weight), ...]
    """
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[start] = 0
    
    # 优先队列：(distance, node)
    pq = [(0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return dist, prev

# 测试
graph = [
    [(1, 4), (2, 2)],           # 节点 0
    [(0, 4), (2, 5), (3, 10)],  # 节点 1
    [(0, 2), (1, 5), (3, 3)],   # 节点 2
    [(1, 10), (2, 3)]           # 节点 3
]

dist, prev = dijkstra(graph, 0)
print(f"最短距离：{dist}")  # [0, 4, 2, 5]
print(f"前驱节点：{prev}")  # [-1, 0, 0, 2]

package main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    node     int
    distance int
    index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].distance < pq[j].distance
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    item.index = len(*pq)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func dijkstra(graph [][][2]int, start int) []int {
    n := len(graph)
    dist := make([]int, n)
    for i := range dist {
        dist[i] = 1e9
    }
    dist[start] = 0

    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, &Item{node: start, distance: 0})

    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        u := item.node
        d := item.distance

        if d > dist[u] {
            continue
        }

        for _, edge := range graph[u] {
            v, weight := edge[0], edge[1]
            if dist[u]+weight < dist[v] {
                dist[v] = dist[u] + weight
                heap.Push(pq, &Item{node: v, distance: dist[v]})
            }
        }
    }

    return dist
}

func main() {
    graph := [][][2]int{
        {{1, 4}, {2, 2}},
        {{0, 4}, {2, 5}, {3, 10}},
        {{0, 2}, {1, 5}, {3, 3}},
        {{1, 10}, {2, 3}},
    }
    fmt.Println(dijkstra(graph, 0)) // [0 4 2 5]
}

Floyd-Warshall 算法 - 多源最短路径

Floyd-Warshall 算法用于计算图中所有节点对之间的最短路径，采用动态规划思想。

状态转移方程

dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

空间优化后：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

function floydWarshall(graph) {
    const n = graph.length;
    const dist = Array(n).fill(null).map(() => Array(n).fill(Infinity));

    // 初始化
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
    }

    // 填充直接边权重
    for (let u = 0; u < n; u++) {
        for (const [v, w] of graph[u]) {
            dist[u][v] = w;
        }
    }

    // Floyd-Warshall 核心
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let 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;
}

// 测试
const graph = [
    [[1, 3], [3, 7]],
    [[2, 2]],
    [[3, 1]],
    [[0, 2]]
];
console.log(floydWarshall(graph));

def floyd_warshall(graph):
    """
    Floyd-Warshall 算法
    graph: 邻接矩阵，graph[i][j] 表示 i 到 j 的距离
    """
    n = len(graph)
    dist = [row[:] for row in graph]  # 深拷贝

    # 对角线为 0
    for i in range(n):
        dist[i][i] = 0

    # 核心算法
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 测试
INF = float('inf')
graph = [
    [0, 3, INF, 7],
    [INF, 0, 2, INF],
    [INF, INF, 0, 1],
    [2, INF, INF, 0]
]

result = floyd_warshall(graph)
for row in result:
    print(row)

package main

import (
    "fmt"
    "math"
)

const INF = math.MaxInt32

func floydWarshall(graph [][]int) [][]int {
    n := len(graph)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        copy(dist[i], graph[i])
    }

    // Floyd-Warshall 核心
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k]+dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
    }

    return dist
}

func main() {
    graph := [][]int{
        {0, 3, INF, 7},
        {INF, 0, 2, INF},
        {INF, INF, 0, 1},
        {2, INF, INF, 0},
    }

    result := floydWarshall(graph)
    for _, row := range result {
        for _, val := range row {
            if val == INF {
                fmt.Print("INF ")
            } else {
                fmt.Printf("%d ", val)
            }
        }
        fmt.Println()
    }
}

最小生成树 (Minimum Spanning Tree)

在带权连通图中找到一棵包含所有顶点的树，使得树中所有边的权重之和最小。

🌲 Prim 算法

从任意节点开始，每次添加最小权边

时间: O((V+E) log V)

空间: O(V)

适合稠密图，类似 Dijkstra

🔗 Kruskal 算法

按权重排序边，使用并查集避免环

时间: O(E log E)

空间: O(V)

适合稀疏图，实现简单

// 并查集实现
class UnionFind {
    constructor(n) {
        this.parent = Array(n).fill(0).map((_, i) => i);
        this.rank = Array(n).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX === rootY) return false;

        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        return true;
    }
}

// Kruskal 算法
function kruskal(n, edges) {
    // 按权重排序
    edges.sort((a, b) => a[2] - b[2]);

    const uf = new UnionFind(n);
    const mst = [];
    let totalWeight = 0;

    for (const [u, v, w] of edges) {
        if (uf.union(u, v)) {
            mst.push([u, v, w]);
            totalWeight += w;
            if (mst.length === n - 1) break;
        }
    }

    return { mst, totalWeight };
}

// 测试
const edges = [
    [0, 1, 4], [0, 2, 2],
    [1, 2, 5], [1, 3, 10],
    [2, 3, 3], [3, 4, 7],
    [2, 4, 6]
];
console.log(kruskal(5, edges));

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

def kruskal(n, edges):
    """
    Kruskal 算法求最小生成树
    edges: [(u, v, w), ...]
    """
    # 按权重排序
    edges.sort(key=lambda x: x[2])

    uf = UnionFind(n)
    mst = []
    total_weight = 0

    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total_weight += w
            if len(mst) == n - 1:
                break

    return mst, total_weight

# 测试
edges = [
    (0, 1, 4), (0, 2, 2),
    (1, 2, 5), (1, 3, 10),
    (2, 3, 3), (3, 4, 7),
    (2, 4, 6)
]
mst, weight = kruskal(5, edges)
print(f"MST: {mst}")
print(f"总权重：{weight}")

拓扑排序 (Topological Sort)

对有向无环图 (DAG) 的顶点进行线性排序，使得对于每一条有向边 (u, v)，u 在排序中都出现在 v 之前。

⚠️ 注意

只有有向无环图 (DAG) 才能进行拓扑排序。如果图中存在环，则无法完成拓扑排序。

sequenceDiagram participant Init as 初始化入度 participant Queue as 入队 participant BFSProc as BFS participant Result as 结果 Init->>Queue: 计算所有节点入度 Queue->>BFSProc: 入度为 0 的节点入队 BFSProc->>BFSProc: 取出节点，减少邻居入度 BFSProc->>Queue: 新入度为 0 的节点入队 BFSProc->>Result: 所有节点出队即为拓扑序 Note over Init,Result: Kahn 算法流程

// Kahn 算法 - BFS 实现
function topologicalSort(graph) {
    const n = graph.length;
    const inDegree = Array(n).fill(0);
    const result = [];

    // 计算入度
    for (let u = 0; u < n; u++) {
        for (const v of graph[u]) {
            inDegree[v]++;
        }
    }

    // 入度为 0 的节点入队
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }

    // BFS 处理
    while (queue.length > 0) {
        const u = queue.shift();
        result.push(u);

        for (const v of graph[u]) {
            inDegree[v]--;
            if (inDegree[v] === 0) {
                queue.push(v);
            }
        }
    }

    // 检查是否有环
    return result.length === n ? result : [];
}

// 测试 - 课程表问题
const courseGraph = [
    [2],    // 课程 0 完成后才能学课程 2
    [2, 3], // 课程 1 完成后才能学课程 2 和 3
    [4],    // 课程 2 完成后才能学课程 4
    [4],    // 课程 3 完成后才能学课程 4
    []      // 课程 4 没有后续
];
console.log(topologicalSort(courseGraph));
// 可能的输出：[0, 1, 2, 3, 4] 或 [1, 0, 3, 2, 4]

from collections import deque

def topological_sort(graph):
    """
    Kahn 算法 - 拓扑排序
    graph: 邻接表，graph[u] = [v1, v2, ...]
    """
    n = len(graph)
    in_degree = [0] * n
    result = []

    # 计算入度
    for u in range(n):
        for v in graph[u]:
            in_degree[v] += 1

    # 入度为 0 的节点入队
    queue = deque([i for i in range(n) if in_degree[i] == 0])

    # BFS 处理
    while queue:
        u = queue.popleft()
        result.append(u)

        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # 检查是否有环
    return result if len(result) == n else []

# 测试 - 课程表问题
course_graph = [
    [2],        # 课程 0 -> 课程 2
    [2, 3],     # 课程 1 -> 课程 2, 3
    [4],        # 课程 2 -> 课程 4
    [4],        # 课程 3 -> 课程 4
    []          # 课程 4 无后续
]
print(topological_sort(course_graph))
# 可能的输出：[0, 1, 2, 3, 4] 或 [1, 0, 3, 2, 4]

实际应用场景

应用场景	说明	示例
任务调度	确定任务执行顺序	构建系统、CI/CD 流水线
课程安排	确定课程学习顺序	大学课程先修关系
依赖解析	解析包依赖关系	npm、pip、maven
电子表格	单元格计算顺序	Excel 公式计算

最大流问题 (Maximum Flow)

在网络流图中，找到从源点 (source) 到汇点 (sink) 的最大流量。每条边有容量限制，且流入等于流出。

最大流约束条件

1. 容量限制：f(u, v) ≤ c(u, v)
2. 流量守恒：∑f(u, v) = ∑f(v, u) (除源点和汇点外)
3. 反对称性：f(u, v) = -f(v, u)

🔄 Ford-Fulkerson

寻找增广路径，更新残留网络

时间: O(E·max_flow)

⚡ Edmonds-Karp

使用 BFS 找增广路径

时间: O(VE²)

🚀 Dinic

分层图 + 阻塞流

时间: O(V²E)

// Edmonds-Karp 算法 (Ford-Fulkerson + BFS)
class MaxFlow {
    constructor(n) {
        this.n = n;
        this.capacity = Array(n).fill(null).map(() => Array(n).fill(0));
    }

    addEdge(u, v, cap) {
        this.capacity[u][v] += cap;
    }

    bfs(s, t, parent) {
        const visited = Array(this.n).fill(false);
        const queue = [s];
        visited[s] = true;
        parent[s] = -1;

        while (queue.length > 0) {
            const u = queue.shift();

            for (let v = 0; v < this.n; v++) {
                if (!visited[v] && this.capacity[u][v] > 0) {
                    visited[v] = true;
                    parent[v] = u;
                    queue.push(v);
                    if (v === t) return true;
                }
            }
        }
        return false;
    }

    edmondsKarp(s, t) {
        let maxFlow = 0;
        const parent = Array(this.n).fill(-1);

        while (this.bfs(s, t, parent)) {
            // 找到路径上的最小容量
            let pathFlow = Infinity;
            let v = t;
            while (v !== s) {
                const u = parent[v];
                pathFlow = Math.min(pathFlow, this.capacity[u][v]);
                v = u;
            }

            // 更新残留网络
            v = t;
            while (v !== s) {
                const u = parent[v];
                this.capacity[u][v] -= pathFlow;
                this.capacity[v][u] += pathFlow;
                v = u;
            }

            maxFlow += pathFlow;
        }

        return maxFlow;
    }
}

// 测试
const mf = new MaxFlow(6);
mf.addEdge(0, 1, 16);
mf.addEdge(0, 2, 13);
mf.addEdge(1, 2, 10);
mf.addEdge(1, 3, 12);
mf.addEdge(2, 1, 4);
mf.addEdge(2, 4, 14);
mf.addEdge(3, 2, 9);
mf.addEdge(3, 5, 20);
mf.addEdge(4, 3, 7);
mf.addEdge(4, 5, 4);

console.log(mf.edmondsKarp(0, 5)); // 23

from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.capacity = [[0] * n for _ in range(n)]

    def add_edge(self, u, v, cap):
        self.capacity[u][v] += cap

    def bfs(self, s, t, parent):
        visited = [False] * self.n
        queue = deque([s])
        visited[s] = True
        parent[s] = -1

        while queue:
            u = queue.popleft()
            for v in range(self.n):
                if not visited[v] and self.capacity[u][v] > 0:
                    visited[v] = True
                    parent[v] = u
                    queue.append(v)
                    if v == t:
                        return True
        return False

    def edmonds_karp(self, s, t):
        max_flow = 0
        parent = [-1] * self.n

        while self.bfs(s, t, parent):
            # 找到路径上的最小容量
            path_flow = float('inf')
            v = t
            while v != s:
                u = parent[v]
                path_flow = min(path_flow, self.capacity[u][v])
                v = u

            # 更新残留网络
            v = t
            while v != s:
                u = parent[v]
                self.capacity[u][v] -= path_flow
                self.capacity[v][u] += path_flow
                v = u

            max_flow += path_flow

        return max_flow

# 测试
mf = MaxFlow(6)
mf.add_edge(0, 1, 16)
mf.add_edge(0, 2, 13)
mf.add_edge(1, 2, 10)
mf.add_edge(1, 3, 12)
mf.add_edge(2, 1, 4)
mf.add_edge(2, 4, 14)
mf.add_edge(3, 2, 9)
mf.add_edge(3, 5, 20)
mf.add_edge(4, 3, 7)
mf.add_edge(4, 5, 4)

print(mf.edmonds_karp(0, 5))  # 23

实际应用场景

图算法在现实世界中有广泛的应用：

🗺️ 导航系统

Dijkstra、A*算法用于计算两点间最短路径

Google Maps 路线规划
GPS 导航系统
物流配送路径优化

🌐 网络路由

最短路径算法用于数据包路由

OSPF 路由协议
互联网骨干网路由
CDN 内容分发

📱 社交网络

图算法分析社交关系

好友推荐系统
社区发现算法
影响力分析

📦 任务调度

拓扑排序确定任务执行顺序

构建系统 (Make, Gradle)
工作流引擎
依赖解析

A* 搜索算法 - 启发式最短路径

A*算法是一种启发式搜索算法，通过评估函数 f(n) = g(n) + h(n) 来选择最优路径，广泛用于路径规划和游戏 AI。

💡 核心思想

f(n) = g(n) + h(n) —— g(n) 是起点到当前点的实际代价，h(n) 是当前点到终点的估计代价（启发函数）。

A* 评估函数

f(n) = g(n) + h(n)
常用启发函数：曼哈顿距离、欧几里得距离、切比雪夫距离

// A* 搜索算法
function aStar(grid, start, end) {
    const rows = grid.length;
    const cols = grid[0].length;
    
    // 启发函数：曼哈顿距离
    function heuristic(a, b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
    
    const openSet = [[start[0], start[1], 0 + heuristic(start, end), 0]];
    const closedSet = new Set();
    const cameFrom = new Map();
    const gScore = new Map();
    gScore.set(start.toString(), 0);
    
    while (openSet.length > 0) {
        // 按 f 值排序，取最小
        openSet.sort((a, b) => a[2] - b[2]);
        const current = openSet.shift();
        const [row, col, f, g] = current;
        
        if (row === end[0] && col === end[1]) {
            // 重建路径
            const path = [];
            let key = end.toString();
            while (cameFrom.has(key)) {
                const [r, c] = JSON.parse(key);
                path.unshift([r, c]);
                key = cameFrom.get(key).toString();
            }
            path.unshift(start);
            return path;
        }
        
        closedSet.add(`${row},${col}`);
        
        // 检查四个方向
        const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        for (const [dr, dc] of directions) {
            const nr = row + dr;
            const nc = col + dc;
            
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] === 1) continue; // 障碍物
            if (closedSet.has(`${nr},${nc}`)) continue;
            
            const newG = g + 1;
            const key = `${nr},${nc}`;
            
            if (newG < (gScore.get(key) || Infinity)) {
                cameFrom.set(key, [row, col]);
                gScore.set(key, newG);
                const f = newG + heuristic([nr, nc], end);
                openSet.push([nr, nc, f, newG]);
            }
        }
    }
    
    return []; // 无路径
}

// 测试 - 网格地图 (0=空地，1=障碍)
const grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0]
];
const path = aStar(grid, [0, 0], [4, 4]);
console.log('路径:', path);
// 可能的输出：[[0,0], [1,0], [2,0], [2,1], [2,2], [2,3], [3,3], [4,3], [4,4]]

import heapq

def a_star(grid, start, end):
    """
    A* 搜索算法
    grid: 二维数组，0=空地，1=障碍
    start: 起点 (row, col)
    end: 终点 (row, col)
    """
    rows, cols = len(grid), len(grid[0])
    
    # 启发函数：曼哈顿距离
    def heuristic(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
    
    # 优先队列：(f, g, row, col)
    open_set = [(heuristic(start, end), 0, start[0], start[1])]
    closed_set = set()
    came_from = {}
    g_score = {start: 0}
    
    while open_set:
        f, g, row, col = heapq.heappop(open_set)
        current = (row, col)
        
        if current == end:
            # 重建路径
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        closed_set.add(current)
        
        # 检查四个方向
        for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nr, nc = row + dr, col + dc
            neighbor = (nr, nc)
            
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == 1:
                continue
            if neighbor in closed_set:
                continue
            
            new_g = g + 1
            if new_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = new_g
                f = new_g + heuristic(neighbor, end)
                heapq.heappush(open_set, (f, new_g, nr, nc))
    
    return []  # 无路径

# 测试
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
path = a_star(grid, (0, 0), (4, 4))
print(f'路径：{path}')
# 可能的输出：[(0,0), (1,0), (2,0), (2,1), (2,2), (2,3), (3,3), (4,3), (4,4)]

package main

import (
    "fmt"
    "sort"
)

type Node struct {
    row, col int
    f, g     int
}

func aStar(grid [][]int, start, end [2]int) [][2]int {
    rows, cols := len(grid), len(grid[0])
    
    // 启发函数：曼哈顿距离
    heuristic := func(a, b [2]int) int {
        return abs(a[0]-b[0]) + abs(a[1]-b[1])
    }
    
    openSet := []Node{{start[0], start[1], heuristic(start, end), 0}}
    closedSet := make(map[string]bool)
    cameFrom := make(map[string][2]int)
    gScore := make(map[string]int)
    gScore[key(start)] = 0
    
    for len(openSet) > 0 {
        // 按 f 值排序
        sort.Slice(openSet, func(i, j int) bool {
            return openSet[i].f < openSet[j].f
        })
        
        current := openSet[0]
        openSet = openSet[1:]
        
        if current.row == end[0] && current.col == end[1] {
            // 重建路径
            var path [][2]int
            k := key(end)
            for prev, ok := cameFrom[k]; ok; {
                path = append([][2]int{prev}, path...)
                k = key(prev)
            }
            path = append([][2]int{start}, path...)
            return path
        }
        
        closedSet[key([2]int{current.row, current.col})] = true
        
        // 检查四个方向
        directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
        for _, d := range directions {
            nr, nc := current.row+d[0], current.col+d[1]
            
            if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
                continue
            }
            if grid[nr][nc] == 1 {
                continue
            }
            if closedSet[key([2]int{nr, nc})] {
                continue
            }
            
            newG := current.g + 1
            nkey := key([2]int{nr, nc})
            
            if newG < getOrDefault(gScore, nkey, 999999) {
                cameFrom[nkey] = [2]int{current.row, current.col}
                gScore[nkey] = newG
                f := newG + heuristic([2]int{nr, nc}, end)
                openSet = append(openSet, Node{nr, nc, f, newG})
            }
        }
    }
    
    return nil
}

func key(pos [2]int) string {
    return fmt.Sprintf("%d,%d", pos[0], pos[1])
}

func getOrDefault(m map[string]int, key string, defaultVal int) int {
    if v, ok := m[key]; ok {
        return v
    }
    return defaultVal
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    grid := [][]int{
        {0, 0, 0, 0, 0},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0},
    }
    
    path := aStar(grid, [2]int{0, 0}, [2]int{4, 4})
    fmt.Printf("路径：%v\n", path)
}

Bellman-Ford 算法 - 可处理负权的最短路径

Bellman-Ford 算法可以处理带有负权边的图，并且能够检测负权环。

⚠️ 负权环检测

如果图中存在负权环，从起点可以无限降低到某些节点的距离，算法会检测到这种情况。

// Bellman-Ford 算法
function bellmanFord(n, edges, start) {
    const dist = Array(n).fill(Infinity);
    dist[start] = 0;
    
    // 松弛 n-1 轮
    for (let i = 0; i < n - 1; i++) {
        let updated = false;
        for (const [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break; // 提前收敛
    }
    
    // 检测负权环
    for (const [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
            return { hasNegativeCycle: true };
        }
    }
    
    return { dist, hasNegativeCycle: false };
}

// 测试
const n = 5;
const edges = [
    [0, 1, 4],
    [0, 2, 2],
    [1, 2, -1],
    [1, 3, 5],
    [2, 3, 8],
    [2, 4, 10],
    [3, 4, 2]
];

const result = bellmanFord(n, edges, 0);
if (result.hasNegativeCycle) {
    console.log('存在负权环');
} else {
    console.log('最短距离:', result.dist);
    // [0, 4, 2, 9, 11]
}

def bellman_ford(n, edges, start):
    """
    Bellman-Ford 算法
    n: 节点数
    edges: 边列表 [(u, v, w), ...]
    start: 起点
    """
    dist = [float('inf')] * n
    dist[start] = 0
    
    # 松弛 n-1 轮
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break
    
    # 检测负权环
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return {'has_negative_cycle': True}
    
    return {'dist': dist, 'has_negative_cycle': False}

# 测试
n = 5
edges = [
    (0, 1, 4),
    (0, 2, 2),
    (1, 2, -1),
    (1, 3, 5),
    (2, 3, 8),
    (2, 4, 10),
    (3, 4, 2)
]

result = bellman_ford(n, edges, 0)
if result['has_negative_cycle']:
    print('存在负权环')
else:
    print(f"最短距离：{result['dist']}")
    # [0, 4, 2, 9, 11]

package main

import "fmt"

type Edge struct {
    u, v, w int
}

func bellmanFord(n int, edges []Edge, start int) ([]int, bool) {
    const INF = 1e9
    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.u] != INF && dist[e.u]+e.w < dist[e.v] {
                dist[e.v] = dist[e.u] + e.w
                updated = true
            }
        }
        if !updated {
            break
        }
    }
    
    // 检测负权环
    for _, e := range edges {
        if dist[e.u] != INF && dist[e.u]+e.w < dist[e.v] {
            return nil, true
        }
    }
    
    return dist, false
}

func main() {
    n := 5
    edges := []Edge{
        {0, 1, 4},
        {0, 2, 2},
        {1, 2, -1},
        {1, 3, 5},
        {2, 3, 8},
        {2, 4, 10},
        {3, 4, 2},
    }
    
    dist, hasNegativeCycle := bellmanFord(n, edges, 0)
    if hasNegativeCycle {
        fmt.Println("存在负权环")
    } else {
        fmt.Printf("最短距离：%v\n", dist)
        // [0 4 2 9 11]
    }
}

Prim 算法 - 最小生成树

Prim 算法用于在加权无向图中找到最小生成树，从任意节点开始，逐步添加最小权重的边。

// Prim 算法 - 最小生成树
function prim(n, graph) {
    const visited = Array(n).fill(false);
    const minEdge = Array(n).fill(Infinity);
    const parent = Array(n).fill(-1);
    minEdge[0] = 0;
    
    let mstWeight = 0;
    
    for (let i = 0; i < n; i++) {
        // 找到未访问的最小边节点
        let u = -1;
        for (let v = 0; v < n; v++) {
            if (!visited[v] && (u === -1 || minEdge[v] < minEdge[u])) {
                u = v;
            }
        }
        
        if (minEdge[u] === Infinity) return null; // 不连通
        
        visited[u] = true;
        mstWeight += minEdge[u];
        
        // 更新邻居
        for (const [v, w] of graph[u]) {
            if (!visited[v] && w < minEdge[v]) {
                minEdge[v] = w;
                parent[v] = u;
            }
        }
    }
    
    // 构建 MST 边列表
    const mstEdges = [];
    for (let i = 1; i < n; i++) {
        if (parent[i] !== -1) {
            mstEdges.push([parent[i], i, minEdge[i]]);
        }
    }
    
    return { edges: mstEdges, weight: mstWeight };
}

// 测试 - 邻接表
const n = 5;
const graph = [
    [[1, 2], [3, 6]],
    [[0, 2], [3, 8], [4, 5]],
    [[3, 10]],
    [[0, 6], [1, 8], [2, 10], [4, 15]],
    [[1, 5], [3, 15]]
];

const result = prim(n, graph);
console.log('MST 边:', result.edges);
console.log('MST 总权重:', result.weight);

import heapq

def prim(n, graph):
    """
    Prim 算法 - 最小生成树
    graph: 邻接表，graph[u] = [(v, w), ...]
    """
    visited = [False] * n
    min_heap = [(0, 0, -1)]  # (weight, node, parent)
    mst_weight = 0
    mst_edges = []
    
    while min_heap:
        w, u, p = heapq.heappop(min_heap)
        
        if visited[u]:
            continue
        
        visited[u] = True
        mst_weight += w
        if p != -1:
            mst_edges.append((p, u, w))
        
        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (weight, v, u))
    
    if sum(visited) != n:
        return None  # 不连通
    
    return {'edges': mst_edges, 'weight': mst_weight}

# 测试
n = 5
graph = [
    [(1, 2), (3, 6)],
    [(0, 2), (3, 8), (4, 5)],
    [(3, 10)],
    [(0, 6), (1, 8), (2, 10), (4, 15)],
    [(1, 5), (3, 15)]
]

result = prim(n, graph)
if result:
    print(f"MST 边：{result['edges']}")
    print(f"MST 总权重：{result['weight']}")

package main

import "fmt"

type Edge struct {
    to, weight int
}

func prim(n int, graph [][]Edge) ([][3]int, int) {
    visited := make([]bool, n)
    minEdge := make([]int, n)
    parent := make([]int, n)
    for i := range minEdge {
        minEdge[i] = 1e9
        parent[i] = -1
    }
    minEdge[0] = 0
    
    mstWeight := 0
    
    for i := 0; i < n; i++ {
        // 找到未访问的最小边节点
        u := -1
        for v := 0; v < n; v++ {
            if !visited[v] && (u == -1 || minEdge[v] < minEdge[u]) {
                u = v
            }
        }
        
        if minEdge[u] == 1e9 {
            return nil, 0 // 不连通
        }
        
        visited[u] = true
        mstWeight += minEdge[u]
        
        // 更新邻居
        for _, e := range graph[u] {
            if !visited[e.to] && e.weight < minEdge[e.to] {
                minEdge[e.to] = e.weight
                parent[e.to] = u
            }
        }
    }
    
    // 构建 MST 边列表
    var mstEdges [][3]int
    for i := 1; i < n; i++ {
        if parent[i] != -1 {
            mstEdges = append(mstEdges, [3]int{parent[i], i, minEdge[i]})
        }
    }
    
    return mstEdges, mstWeight
}

func main() {
    n := 5
    graph := make([][]Edge, n)
    graph[0] = []Edge{{1, 2}, {3, 6}}
    graph[1] = []Edge{{0, 2}, {3, 8}, {4, 5}}
    graph[2] = []Edge{{3, 10}}
    graph[3] = []Edge{{0, 6}, {1, 8}, {2, 10}, {4, 15}}
    graph[4] = []Edge{{1, 5}, {3, 15}}
    
    edges, weight := prim(n, graph)
    fmt.Printf("MST 边：%v\n", edges)
    fmt.Printf("MST 总权重：%d\n", weight)
}

Tarjan 算法 - 强连通分量

Tarjan 算法用于在有向图中找到所有强连通分量（SCC），即图中任意两点都互相可达的最大子图。

// Tarjan 强连通分量算法
function tarjanSCC(n, graph) {
    const visited = Array(n).fill(false);
    const stack = [];
    const onStack = Array(n).fill(false);
    const disc = Array(n).fill(-1);
    const low = Array(n).fill(-1);
    
    let time = 0;
    const sccs = [];
    
    function dfs(u) {
        disc[u] = low[u] = time++;
        stack.push(u);
        onStack[u] = true;
        
        for (const v of graph[u]) {
            if (disc[v] === -1) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        
        // 找到 SCC 根节点
        if (low[u] === disc[u]) {
            const scc = [];
            while (true) {
                const v = stack.pop();
                onStack[v] = false;
                scc.push(v);
                if (v === u) break;
            }
            sccs.push(scc);
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (disc[i] === -1) {
            dfs(i);
        }
    }
    
    return sccs;
}

// 测试
const n = 8;
const graph = [
    [1],      // 0
    [2],      // 1
    [0, 3],   // 2
    [4],      // 3
    [5, 7],   // 4
    [6],      // 5
    [4],      // 6
 [6]       // 7
];

const sccs = tarjanSCC(n, graph);
console.log('强连通分量:');
sccs.forEach((scc, i) => {
    console.log(`  SCC ${i + 1}: [${scc.join(', ')}]`);
});
// 输出：
//   SCC 1: [7, 6, 5, 4, 3]
//   SCC 2: [2, 1, 0]

def tarjan_scc(n, graph):
    """
    Tarjan 强连通分量算法
    graph: 邻接表
    """
    visited = [False] * n
    stack = []
    on_stack = [False] * n
    disc = [-1] * n
    low = [-1] * n
    
    time = 0
    sccs = []
    
    def dfs(u):
        nonlocal time
        disc[u] = low[u] = time
        time += 1
        stack.append(u)
        on_stack[u] = True
        
        for v in graph[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])
        
        # 找到 SCC 根节点
        if low[u] == disc[u]:
            scc = []
            while True:
                v = stack.pop()
                on_stack[v] = False
                scc.append(v)
                if v == u:
                    break
            sccs.append(scc)
    
    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    
    return sccs

# 测试
n = 8
graph = [
    [1],      # 0
    [2],      # 1
    [0, 3],   # 2
    [4],      # 3
    [5, 7],   # 4
    [6],      # 5
    [4],      # 6
    [6]       # 7
]

sccs = tarjan_scc(n, graph)
print('强连通分量:')
for i, scc in enumerate(sccs):
    print(f"  SCC {i+1}: {scc}")
# 输出：
#   SCC 1: [7, 6, 5, 4, 3]
#   SCC 2: [2, 1, 0]

package main

import "fmt"

func tarjanSCC(n int, graph [][]int) [][]int {
    disc := make([]int, n)
    low := make([]int, n)
    onStack := make([]bool, n)
    stack := []int{}
    
    for i := range disc {
        disc[i] = -1
        low[i] = -1
    }
    
    time := 0
    var sccs [][]int
    
    var dfs func(int)
    dfs = func(u int) {
        disc[u] = time
        low[u] = time
        time++
        stack = append(stack, u)
        onStack[u] = true
        
        for _, v := range graph[u] {
            if disc[v] == -1 {
                dfs(v)
                if low[v] < low[u] {
                    low[u] = low[v]
                }
            } else if onStack[v] && disc[v] < low[u] {
                low[u] = disc[v]
            }
        }
        
        // 找到 SCC 根节点
        if low[u] == disc[u] {
            var scc []int
            for {
                v := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                onStack[v] = false
                scc = append(scc, v)
                if v == u {
                    break
                }
            }
            sccs = append(sccs, scc)
        }
    }
    
    for i := 0; i < n; i++ {
        if disc[i] == -1 {
            dfs(i)
        }
    }
    
    return sccs
}

func main() {
    n := 8
    graph := [][]int{
        {1},      // 0
        {2},      // 1
        {0, 3},   // 2
        {4},      // 3
        {5, 7},   // 4
        {6},      // 5
        {4},      // 6
        {6},      // 7
    }
    
    sccs := tarjanSCC(n, graph)
    fmt.Println("强连通分量:")
    for i, scc := range sccs {
        fmt.Printf("  SCC %d: %v\n", i+1, scc)
    }
}

Kruskal 算法 - 最小生成树

Kruskal 算法通过贪心策略，每次选择权重最小的边来构建最小生成树，使用并查集来检测环。

💡 核心思想

贪心 + 并查集 —— 将所有边按权重排序，从小到大依次选择，如果边的两个端点不在同一连通分量中，则加入该边。

// 并查集实现
class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const px = this.find(x);
        const py = this.find(y);
        if (px === py) return false;

        if (this.rank[px] < this.rank[py]) {
            this.parent[px] = py;
        } else if (this.rank[px] > this.rank[py]) {
            this.parent[py] = px;
        } else {
            this.parent[py] = px;
            this.rank[px]++;
        }
        return true;
    }
}

// Kruskal 算法
function kruskal(n, edges) {
    // 按权重排序
    edges.sort((a, b) => a[2] - b[2]);

    const uf = new UnionFind(n);
    const mstEdges = [];
    let mstWeight = 0;

    for (const [u, v, w] of edges) {
        if (uf.union(u, v)) {
            mstEdges.push([u, v, w]);
            mstWeight += w;
            if (mstEdges.length === n - 1) break;
        }
    }

    return mstEdges.length === n - 1 ? { edges: mstEdges, weight: mstWeight } : null;
}

// 测试
const n = 5;
const edges = [
    [0, 1, 2], [0, 3, 6],
    [1, 2, 3], [1, 3, 8], [1, 4, 5],
    [2, 4, 7],
    [3, 4, 9]
];

const result = kruskal(n, edges);
if (result) {
    console.log('MST 边:', result.edges);
    console.log('MST 总权重:', result.weight);
}

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False

        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    """
    Kruskal 算法 - 最小生成树
    edges: 边列表 [(u, v, w), ...]
    """
    # 按权重排序
    edges.sort(key=lambda x: x[2])

    uf = UnionFind(n)
    mst_edges = []
    mst_weight = 0

    for u, v, w in edges:
        if uf.union(u, v):
            mst_edges.append((u, v, w))
            mst_weight += w
            if len(mst_edges) == n - 1:
                break

    return {'edges': mst_edges, 'weight': mst_weight} if len(mst_edges) == n - 1 else None

# 测试
n = 5
edges = [
    (0, 1, 2), (0, 3, 6),
    (1, 2, 3), (1, 3, 8), (1, 4, 5),
    (2, 4, 7),
    (3, 4, 9)
]

result = kruskal(n, edges)
if result:
    print(f"MST 边：{result['edges']}")
    print(f"MST 总权重：{result['weight']}")

package main

import (
    "fmt"
    "sort"
)

type Edge struct {
    u, v, w int
}

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

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

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] {
        uf.parent[px] = py
    } else if uf.rank[px] > uf.rank[py] {
        uf.parent[py] = px
    } else {
        uf.parent[py] = px
        uf.rank[px]++
    }
    return true
}

func kruskal(n int, edges []Edge) ([]Edge, int) {
    // 按权重排序
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].w < edges[j].w
    })

    uf := NewUnionFind(n)
    var mstEdges []Edge
    mstWeight := 0

    for _, e := range edges {
        if uf.Union(e.u, e.v) {
            mstEdges = append(mstEdges, e)
            mstWeight += e.w
            if len(mstEdges) == n-1 {
                break
            }
        }
    }

    if len(mstEdges) == n-1 {
        return mstEdges, mstWeight
    }
    return nil, 0
}

func main() {
    n := 5
    edges := []Edge{
        {0, 1, 2}, {0, 3, 6},
        {1, 2, 3}, {1, 3, 8}, {1, 4, 5},
        {2, 4, 7},
        {3, 4, 9},
    }

    mstEdges, mstWeight := kruskal(n, edges)
    if mstEdges != nil {
        fmt.Printf("MST 边：%v\n", mstEdges)
        fmt.Printf("MST 总权重：%d\n", mstWeight)
    }
}

SPFA 算法 - 队列优化的 Bellman-Ford

SPFA (Shortest Path Faster Algorithm) 是 Bellman-Ford 算法的队列优化版本，在稀疏图上表现更好。

⚠️ 注意事项

SPFA 在最坏情况下时间复杂度仍为 O(VE)，但在随机稀疏图上通常表现优异。可以检测负权环。

// SPFA 算法
function spfa(n, graph, start) {
    const dist = Array(n).fill(Infinity);
    const inQueue = Array(n).fill(false);
    const count = Array(n).fill(0); // 记录入队次数，检测负环
    dist[start] = 0;

    const queue = [start];
    inQueue[start] = true;
    count[start] = 1;

    while (queue.length > 0) {
        const u = queue.shift();
        inQueue[u] = false;

        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    queue.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    if (count[v] >= n) {
                        return { hasNegativeCycle: true };
                    }
                }
            }
        }
    }

    return { dist, hasNegativeCycle: false };
}

// 测试
const n = 5;
const graph = [
    [[1, 4], [2, 2]],
    [[2, -1], [3, 5]],
    [[3, 8], [4, 10]],
    [[4, 2]],
    []
];

const result = spfa(n, graph, 0);
if (result.hasNegativeCycle) {
    console.log('存在负权环');
} else {
    console.log('最短距离:', result.dist);
}

from collections import deque

def spfa(n, graph, start):
    """
    SPFA 算法 - 队列优化的 Bellman-Ford
    graph: 邻接表，graph[u] = [(v, w), ...]
    """
    dist = [float('inf')] * n
    in_queue = [False] * n
    count = [0] * n
    dist[start] = 0

    queue = deque([start])
    in_queue[start] = True
    count[start] = 1

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1
                    if count[v] >= n:
                        return {'has_negative_cycle': True}

    return {'dist': dist, 'has_negative_cycle': False}

# 测试
n = 5
graph = [
    [(1, 4), (2, 2)],
    [(2, -1), (3, 5)],
    [(3, 8), (4, 10)],
    [(4, 2)],
    []
]

result = spfa(n, graph, 0)
if result['has_negative_cycle']:
    print('存在负权环')
else:
    print(f"最短距离：{result['dist']}")

package main

import "fmt"

type Edge struct {
    to, weight int
}

func spfa(n int, graph [][]Edge, start int) ([]int, bool) {
    const INF = 1e9
    dist := make([]int, n)
    inQueue := make([]bool, n)
    count := make([]int, n)
    for i := range dist {
        dist[i] = INF
    }
    dist[start] = 0

    queue := []int{start}
    inQueue[start] = true
    count[start] = 1

    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        inQueue[u] = false

        for _, e := range graph[u] {
            if dist[u]+e.weight < dist[e.to] {
                dist[e.to] = dist[u] + e.weight
                if !inQueue[e.to] {
                    queue = append(queue, e.to)
                    inQueue[e.to] = true
                    count[e.to]++
                    if count[e.to] >= n {
                        return nil, true
                    }
                }
            }
        }
    }

    return dist, false
}

func main() {
    n := 5
    graph := make([][]Edge, n)
    graph[0] = []Edge{{1, 4}, {2, 2}}
    graph[1] = []Edge{{2, -1}, {3, 5}}
    graph[2] = []Edge{{3, 8}, {4, 10}}
    graph[3] = []Edge{{4, 2}}

    dist, hasNegativeCycle := spfa(n, graph, 0)
    if hasNegativeCycle {
        fmt.Println("存在负权环")
    } else {
        fmt.Printf("最短距离：%v\n", dist)
    }
}

二分图匹配 - 匈牙利算法

匈牙利算法用于在二分图中找到最大匹配，即选择最多的边使得没有两条边共享顶点。

// 匈牙利算法 - 二分图最大匹配
function maxBipartiteMatching(n, m, graph) {
    const match = Array(m).fill(-1); // 右侧匹配
    const vis = Array(n).fill(false);

    function dfs(u) {
        for (const v of graph[u]) {
            if (vis[v]) continue;
            vis[v] = true;

            if (match[v] === -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
        return false;
    }

    let result = 0;
    for (let i = 0; i < n; i++) {
        vis.fill(false);
        if (dfs(i)) result++;
    }

    return {
        maxMatching: result,
        match: match.map((u, v) => u !== -1 ? [u, v] : null).filter(Boolean)
    };
}

// 测试 - 二分图：左侧 4 个点，右侧 3 个点
const n = 4, m = 3;
const graph = [
    [0, 1],      // 左侧点 0 连接右侧点 0,1
    [0, 2],      // 左侧点 1 连接右侧点 0,2
    [1],         // 左侧点 2 连接右侧点 1
    [2]          // 左侧点 3 连接右侧点 2
];

const result = maxBipartiteMatching(n, m, graph);
console.log('最大匹配数:', result.maxMatching);
console.log('匹配边:', result.match);

def max_bipartite_matching(n, m, graph):
    """
    匈牙利算法 - 二分图最大匹配
    n: 左侧点数
    m: 右侧点数
    graph: 邻接表，graph[u] = [v1, v2, ...]
    """
    match = [-1] * m  # 右侧匹配
    vis = [False] * n

    def dfs(u):
        for v in graph[u]:
            if vis[v]:
                continue
            vis[v] = True

            if match[v] == -1 or dfs(match[v]):
                match[v] = u
                return True
        return False

    result = 0
    for i in range(n):
        vis = [False] * n
        if dfs(i):
            result += 1

    match_edges = [(u, v) for v, u in enumerate(match) if u != -1]
    return {'max_matching': result, 'match': match_edges}

# 测试
n, m = 4, 3
graph = [
    [0, 1],      # 左侧点 0 连接右侧点 0,1
    [0, 2],      # 左侧点 1 连接右侧点 0,2
    [1],         # 左侧点 2 连接右侧点 1
    [2]          # 左侧点 3 连接右侧点 2
]

result = max_bipartite_matching(n, m, graph)
print(f"最大匹配数：{result['max_matching']}")
print(f"匹配边：{result['match']}")

package main

import "fmt"

func maxBipartiteMatching(n, m int, graph [][]int) (int, [][2]int) {
    match := make([]int, m)
    for i := range match {
        match[i] = -1
    }

    var dfs func(int, []bool) bool
    dfs = func(u int, vis []bool) bool {
        for _, v := range graph[u] {
            if vis[v] {
                continue
            }
            vis[v] = true

            if match[v] == -1 || dfs(match[v], vis) {
                match[v] = u
                return true
            }
        }
        return false
    }

    result := 0
    for i := 0; i < n; i++ {
        vis := make([]bool, n)
        if dfs(i, vis) {
            result++
        }
    }

    var matchEdges [][2]int
    for v, u := range match {
        if u != -1 {
            matchEdges = append(matchEdges, [2]int{u, v})
        }
    }

    return result, matchEdges
}

func main() {
    n, m := 4, 3
    graph := [][]int{
        {0, 1},
        {0, 2},
        {1},
        {2},
    }

    maxMatching, matchEdges := maxBipartiteMatching(n, m, graph)
    fmt.Printf("最大匹配数：%d\n", maxMatching)
    fmt.Printf("匹配边：%v\n", matchEdges)
}

PageRank 算法 - 网页排名

PageRank 是 Google 的核心算法之一，用于衡量网页的重要性。基于"被重要网页链接的网页也重要"的思想。

PageRank 公式

PR(A) = (1-d)/N + d × Σ(PR(B)/L(B))
d = 阻尼因子 (通常 0.85), L(B) = B 的出链数

// PageRank 算法
function pageRank(n, graph, d = 0.85, maxIter = 100) {
    let pr = Array(n).fill(1 / n);

    // 计算出度
    const outDegree = Array(n).fill(0);
    for (let u = 0; u < n; u++) {
        outDegree[u] = graph[u].length;
    }

    for (let iter = 0; iter < maxIter; iter++) {
        const newPr = Array(n).fill((1 - d) / n);

        for (let u = 0; u < n; u++) {
            for (const v of graph[u]) {
                newPr[v] += d * pr[u] / outDegree[u];
            }
        }

        pr = newPr;
    }

    return pr.map((score, i) => ({ node: i, score }));
}

// 测试 - 4 个网页的链接关系
const n = 4;
const graph = [
    [1, 2],    // 0 链接到 1,2
    [2],       // 1 链接到 2
    [0, 3],    // 2 链接到 0,3
    [2]        // 3 链接到 2
];

const result = pageRank(n, graph);
result.sort((a, b) => b.score - a.score);
console.log('PageRank 排名:');
result.forEach(({ node, score }) => {
    console.log(`  节点 ${node}: ${score.toFixed(4)}`);
});

def pagerank(n, graph, d=0.85, max_iter=100):
    """
    PageRank 算法
    n: 节点数
    graph: 邻接表，graph[u] = [v1, v2, ...]
    d: 阻尼因子
    """
    pr = [1 / n] * n

    # 计算出度
    out_degree = [len(graph[u]) for u in range(n)]

    for _ in range(max_iter):
        new_pr = [(1 - d) / n] * n

        for u in range(n):
            if out_degree[u] == 0:
                continue
            for v in graph[u]:
                new_pr[v] += d * pr[u] / out_degree[u]

        pr = new_pr

    return [(i, score) for i, score in enumerate(pr)]

# 测试
n = 4
graph = [
    [1, 2],    # 0 链接到 1,2
    [2],       # 1 链接到 2
    [0, 3],    # 2 链接到 0,3
    [2]        # 3 链接到 2
]

result = sorted(pagerank(n, graph), key=lambda x: x[1], reverse=True)
print('PageRank 排名:')
for node, score in result:
    print(f"  节点 {node}: {score:.4f}")

package main

import "fmt"

func pageRank(n int, graph [][]int, d float64, maxIter int) []struct {
    Node  int
    Score float64
} {
    pr := make([]float64, n)
    for i := range pr {
        pr[i] = 1.0 / float64(n)
    }

    outDegree := make([]int, n)
    for i := range graph {
        outDegree[i] = len(graph[i])
    }

    for iter := 0; iter < maxIter; iter++ {
        newPr := make([]float64, n)
        for i := range newPr {
            newPr[i] = (1 - d) / float64(n)
        }

        for u := 0; u < n; u++ {
            if outDegree[u] == 0 {
                continue
            }
            for _, v := range graph[u] {
                newPr[v] += d * pr[u] / float64(outDegree[u])
            }
        }

        pr = newPr
    }

    result := make([]struct {
        Node  int
        Score float64
    }, n)
    for i := range result {
        result[i].Node = i
        result[i].Score = pr[i]
    }
    return result
}

func main() {
    n := 4
    graph := [][]int{
        {1, 2},
        {2},
        {0, 3},
        {2},
    }

    result := pageRank(n, graph, 0.85, 100)
    fmt.Println("PageRank 排名:")
    for _, r := range result {
        fmt.Printf("  节点 %d: %.4f\n", r.Node, r.Score)
    }
}

图算法对比总结

算法	类型	时间复杂度	空间复杂度	特点
Dijkstra	单源最短路径	O((V+E) log V)	O(V)	贪心，不能处理负权
Floyd-Warshall	多源最短路径	O(V³)	O(V²)	动态规划，可处理负权
Bellman-Ford	单源最短路径	O(VE)	O(V)	可处理负权，检测负权环
A*	启发式搜索	取决于启发函数	O(V)	路径规划，游戏 AI
Prim	最小生成树	O((V+E) log V)	O(V)	贪心，适用于稠密图
Kruskal	最小生成树	O(E log E)	O(V)	并查集，适用于稀疏图
Tarjan	强连通分量	O(V+E)	O(V)	DFS，线性时间
拓扑排序	DAG 排序	O(V+E)	O(V)	任务调度，依赖解析
SPFA	单源最短路径	O(kE) 平均	O(V)	队列优化，可处理负权
匈牙利算法	二分图匹配	O(VE)	O(V)	DFS 增广路，最大匹配
PageRank	图中心性	O(k(V+E))	O(V)	网页排名，影响力分析