LeetCode-图论基础及算法技巧总结

VocabVictor2024-09-022024-09-04

引言

图是一种复杂而强大的数据结构，在计算机科学和现实世界中有着广泛的应用。本文将介绍图的基本概念、表示方法、常见算法以及解决图相关问题的技巧。

1. 图的基本概念

图由顶点（节点）和边组成。根据边的性质，图可以分为：

无向图：边没有方向
有向图：边有特定方向
加权图：边有权重

2. 图的表示方法

2.1 邻接矩阵

使用二维数组表示图中节点之间的连接关系。

# 邻接矩阵表示
graph = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
]

2.2 邻接表

使用字典或列表数组表示每个节点的邻接节点。

# 邻接表表示
graph = {
    0: [1],
    1: [0, 2],
    2: [1]
}

3. 图的遍历

3.1 深度优先搜索（DFS）

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

3.2 广度优先搜索（BFS）

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

4. 常见图算法

4.1 最短路径算法

Dijkstra算法

用于找到图中一个顶点到其他所有顶点的最短路径。

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

Floyd-Warshall算法

用于找到图中所有顶点对之间的最短路径。

def floyd_warshall(graph):
    dist = {node: {node: float('inf') for node in graph} for node in graph}
    
    for node in graph:
        dist[node][node] = 0
        for neighbor, weight in graph[node].items():
            dist[node][neighbor] = weight
    
    for k in graph:
        for i in graph:
            for j in graph:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

4.2 最小生成树算法

Kruskal算法

def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])

def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

def kruskal(graph):
    result = []
    i, e = 0, 0
    graph = sorted(graph, key=lambda item: item[2])
    parent = []
    rank = []
    for node in range(len(graph)):
        parent.append(node)
        rank.append(0)
    while e < len(graph) - 1:
        u, v, w = graph[i]
        i = i + 1
        x = find(parent, u)
        y = find(parent, v)
        if x != y:
            e = e + 1
            result.append([u, v, w])
            union(parent, rank, x, y)
    return result

4.3 拓扑排序

from collections import defaultdict

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    queue = deque([u for u in in_degree if in_degree[u] == 0])
    result = []
    
    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)
    
    if len(result) != len(graph):
        return None  # Graph has a cycle
    return result