← 返回算法分类

图算法

什么是图算法？

图算法用于处理图结构数据，解决最短路径、最小生成树、拓扑排序等经典问题。

Dijkstra

O((V+E)logV)

Floyd-Warshall

O(V³)

Kruskal/Prim

O(ElogV)

Dijkstra 最短路径算法

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

function dijkstra(graph, start) {
    const distances = {};
    const visited = new Set();
    const pq = new PriorityQueue();
    
    // 初始化
    for (const node in graph) {
        distances[node] = Infinity;
    }
    distances[start] = 0;
    pq.enqueue(start, 0);
    
    while (!pq.isEmpty()) {
        const { element: current } = pq.dequeue();
        
        if (visited.has(current)) continue;
        visited.add(current);
        
        for (const neighbor in graph[current]) {
            const distance = distances[current] + graph[current][neighbor];
            
            if (distance < distances[neighbor]) {
                distances[neighbor] = distance;
                pq.enqueue(neighbor, distance);
            }
        }
    }
    
    return distances;
}

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

// 测试
const graph = {
    A: { B: 4, C: 2 },
    B: { A: 4, C: 5, D: 10 },
    C: { A: 2, B: 5, D: 3 },
    D: { B: 10, C: 3 }
};
console.log(dijkstra(graph, 'A'));
// { A: 0, B: 4, C: 2, D: 5 }
                            
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, current = heapq.heapp        
        if currentop(pq)
_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# 测试
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 5, 'D': 10},
    'C': {'A': 2, 'B': 5, 'D': 3},
    'D': {'B': 10, 'C': 3}
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 4, 'C': 2, 'D': 5}
                            
package main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    node     string
    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]
    old[n-1] = nil
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

func (pq *PriorityQueue) update(item *Item, node string, distance int) {
    item.node = node
    item.distance = distance
    heap.Fix(pq, item.index)
}

func dijkstra(graph map[string]map[string]int, start string) map[string]int {
    distances := make(map[string]int)
    visited := make(map[string]bool)
    
    for node := range graph {
        distances[node] = 1 << 30
    }
    distances[start] = 0
    
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, &Item{node: start, distance: 0})
    
    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        current := item.node
        currentDist := item.distance
        
        if visited[current] {
            continue
        }
        visited[current] = true
        
        for neighbor, weight := range graph[current] {
            if visited[neighbor] {
                continue
            }
            newDist := currentDist + weight
            if newDist < distances[neighbor] {
                distances[neighbor] = newDist
                heap.Push(pq, &Item{node: neighbor, distance: newDist})
            }
        }
    }
    
    return distances
}

func main() {
    graph := map[string]map[string]int{
        "A": {"B": 4, "C": 2},
        "B": {"A": 4, "C": 5, "D": 10},
        "C": {"A": 2, "B": 5, "D": 3},
        "D": {"B": 10, "C": 3},
    }
    fmt.Println(dijkstra(graph, "A"))  // map[A:0 B:4 C:2 D:5]
}

Floyd-Warshall 算法

计算图中所有节点对之间的最短路径，适合解决多源最短路径问题。

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 (const [u, v, w] of graph) {
        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;
}

// 测试 (节点0,1,2,3)
const graph = [
    [0, 3, Infinity, 7],
    [8, 0, 2, Infinity],
    [5, Infinity, 0, 1],
    [2, Infinity, Infinity, 0]
];
console.log(floydWarshall(graph));
                            
def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    
    for u, v, w in graph:
        dist[u][v] = w
    
    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

# 测试 (节点0,1,2,3)
graph = [
    [0, 3, float('inf'), 7],
    [8, 0, 2, float('inf')],
    [5, float('inf'), 0, 1],
    [2, float('inf'), float('inf'), 0]
]
print(floyd_warshall(graph))
                            
package main

import (
    "fmt"
    "math"
)

func floydWarshall(graph [][]int) [][]int {
    n := len(graph)
    dist := make([][]int, n)
    const INF = 1 << 30
    
    for i := 0; i < n; i++ {
        dist[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if i == j {
                dist[i][j] = 0
            } else {
                dist[i][j] = INF
            }
        }
    }
    
    for _, edge := range graph {
        u, v, w := edge[0], edge[1], edge[2]
        dist[u][v] = w
    }
    
    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() {
    graph := [][]int{
        {0, 3, 0, 7},
        {8, 0, 2, 0},
        {5, 0, 0, 1},
        {2, 0, 0, 0},
    }
    result := floydWarshall(graph)
    fmt.Println(result)
}

最小生成树 (Prim算法)

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

function prim(graph) {
    const n = graph.length;
    const key = Array(n).fill(Infinity);
    const parent = Array(n).fill(-1);
    const mst = new Set();
    
    key[0] = 0;
    
    for (let i = 0; i < n - 1; i++) {
        // 找到key值最小的顶点
        let u = -1;
        for (let v = 0; v < n; v++) {
            if (!mst.has(v) && (u === -1 || key[v] < key[u])) {
                u = v;
            }
        }
        
        mst.add(u);
        
        // 更新相邻顶点的key值
        for (let v = 0; v < n; v++) {
            if (graph[u][v] && !mst.has(v) && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    
    return parent;
}

// 测试
const graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
];
const mst = prim(graph);
console.log("最小生成树的边：");
for (let i = 1; i < mst.length; i++) {
    console.log(`${mst[i]} - ${i}`);
}
                            
def prim(graph):
    n = len(graph)
    key = [float('inf')] * n
    parent = [-1] * n
    mst = set()
    
    key[0] = 0
    
    for _ in range(n - 1):
        u = -1
        for v in range(n):
            if v not in mst and (u == -1 or key[v] < key[u]):
                u = v
        
        mst.add(u)
        
        for v in range(n):
            if graph[u][v] and v not in mst and graph[u][v] < key[v]:
                parent[v] = u
                key[v] = graph[u][v]
    
    return parent

# 测试
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
mst = prim(graph)
print("最小生成树的边：")
for i in range(1, len(mst)):
    print(f"{mst[i]} - {i}")
                            
package main

import (
    "fmt"
    "math"
)

func prim(graph [][]int) []int {
    n := len(graph)
    key := make([]int, n)
    parent := make([]int, n)
    mst := make([]bool, n)
    const INF = 1 << 30
    
    for i := 0; i < n; i++ {
        key[i] = INF
        parent[i] = -1
    }
    
    key[0] = 0
    
    for i := 0; i < n-1; i++ {
        u := -1
        for v := 0; v < n; v++ {
            if !mst[v] && (u == -1 || key[v] < key[u]) {
                u = v
            }
        }
        
        mst[u] = true
        
        for v := 0; v < n; v++ {
            if graph[u][v] != 0 && !mst[v] && graph[u][v] < key[v] {
                parent[v] = u
                key[v] = graph[u][v]
            }
        }
    }
    
    return parent
}

func main() {
    graph := [][]int{
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0},
    }
    mst := prim(graph)
    fmt.Println("最小生成树的边：")
    for i := 1; i < len(mst); i++ {
        fmt.Printf("%d - %d\n", mst[i], i)
    }
}

拓扑排序

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

function topologicalSort(graph) {
    const inDegree = {};
    const queue = [];
    const result = [];
    
    // 初始化入度
    for (const node in graph) {
        inDegree[node] = 0;
    }
    for (const node in graph) {
        for (const neighbor of graph[node]) {
            inDegree[neighbor]++;
        }
    }
    
    // 将入度为0的节点加入队列
    for (const node in inDegree) {
        if (inDegree[node] === 0) {
            queue.push(node);
        }
    }
    
    // BFS处理
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        
        for (const neighbor of graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return result.length === Object.keys(graph).length ? result : [];
}

// 测试
const courseGraph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
};
console.log(topologicalSort(courseGraph)); // ['B', 'A', 'D', 'C', 'E', 'F']
                            
from collections import deque

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == len(graph) else []

# 测试
course_graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}
print(topological_sort(course_graph))  # ['B', 'A', 'D', 'C', 'E', 'F']
                            
package main

import (
    "fmt"
)

func topologicalSort(graph map[string][]string) []string {
    inDegree := make(map[string]int)
    
    for node := range graph {
        inDegree[node] = 0
    }
    
    for node, neighbors := range graph {
        for _, neighbor := range neighbors {
            inDegree[neighbor]++
        }
    }
    
    var queue []string
    for node, degree := range inDegree {
        if degree == 0 {
            queue = append(queue, node)
        }
    }
    
    var result []string
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    
    if len(result) == len(graph) {
        return result
    }
    return nil
}

func main() {
    courseGraph := map[string][]string{
        "A": {"C"},
        "B": {"C", "D"},
        "C": {"E"},
        "D": {"F"},
        "E": {"F"},
        "F": {},
    }
    fmt.Println(topologicalSort(courseGraph))  // [B A D C E F]
}

学习建议

  • 掌握图的基本表示方法：邻接矩阵和邻接表
  • 理解不同算法的适用场景
  • 多练习经典问题：最短路径、最小生成树
  • 学习BFS和DFS在图中的应用