研究生 → 定制化 → 组合优化 ↓

图算法

图是用于模拟对象之间配对关系的数学结构。在此上下文中，图由通过边（也称为链接或线）连接的顶点（也称为节点或点）组成。图算法是旨在解决涉及图问题的数学程序。

图算法的重要性

图在包括计算机科学、生物学和社会科学在内的许多领域中具有根本的重要性。它们有助于解决诸如网络流、寻找最短路径、创建生成树等问题。让我们来探讨一些基本和高级的图算法。

基本定义

在进入算法之前，了解与图相关的一些基本术语是必不可少的。

顶点（或节点）：图中边相交的点。
边（或链接）：两个顶点之间的连接。
相邻性：如果两个顶点直接通过一条边连接，则它们是相邻的。
路径：连接一系列顶点的一系列边。
环：起始和终止于同一顶点的路径。
连通图：在连通图中，每对顶点之间都有路径。

图的类型

有向图（digraph）：图中的边具有方向。每条边是一对有序顶点。
无向图：图中的边没有方向。每条边是一对无序顶点。
加权图：图中的每条边都有一个数值（权重）与之关联。
无权图：图中的边没有权重。
完全图：在完全图中，每对顶点之间恰好有一条边。

图的表示

图可以用两种主要方式表示：

邻接矩阵

邻接矩阵是一个二维数组，其中每个元素指示顶点对之间是否存在边。

a = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [0, 1, 1, 0]
]

此矩阵显示具有4个顶点和顶点对之间边（0,1）、（1,2）、（1,3）和（2,3）的图。

邻接表

邻接表将图表示为顶点列表，其中每个顶点有自己的相邻顶点列表。

{
    0: [1],
    1: [0, 2, 3],
    2: [1, 3],
    3: [1, 2]
}

在此列表中，顶点0连接到顶点1，顶点1连接到顶点0、2、3，依此类推。

图遍历算法

图遍历意味着访问图的每个顶点的过程。遍历图有两种主要方法：

广度优先搜索（BFS）

BFS是一种迭代遍历图的方法，它通过探索位于当前深度的相邻节点，然后再移动到位于下一深度级别的节点。

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

    while queue:
        vertex = queue.pop(0)

        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)

    return visited

在上面的代码中，图从顶点start开始遍历。BFS方法使用队列来跟踪下一个要访问的顶点。

BFS操作示例

上述SVG展示了一个简单的图，其中顶点编号为0至3。从顶点0开始，BFS将按以下顺序访问节点：0，1，3，2。

深度优先搜索（DFS）

DFS是一种遍历方法，优先考虑深度，并尽可能沿分支移动，然后再回溯。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    for next in graph[start]:
        if next not in visited:
            dfs(graph, next, visited)

    return visited

在DFS代码中，方法是通过函数调用递归调用的，并且使用堆栈来跟踪路径。

DFS操作示例

对于相同的图，DFS将按以下顺序访问节点：0，1，2，3。

最短路径算法

图算法的目标通常是找到节点之间的最短路径。以下是两个著名的最短路径算法：

Dijkstra算法

Dijkstra算法找到从初始顶点到加权图中所有其他顶点的最短路径。

import heapq

def dijkstra(graph, start):
    queue = []
    heapq.heappush(queue, (0, start))
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        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(queue, (distance, neighbor))

    return distances

该算法使用队列首先找到具有最小累积权重的边。它使用优先队列（最小堆）来有效地获取最小距离的边。

Bellman–Ford算法

Bellman-Ford算法从单个源顶点计算到图中所有其他顶点的最短路径。它可以处理具有负权重的图。

def bellman_ford(graph, start):
    distance = {i: float('inf') for i in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distance[vertex] + weight < distance[neighbor]:
                raise ValueError("The graph contains a negative weight cycle")

    return distance

与Dijkstra算法不同，Bellman-Ford算法适用于包含负权重边的图。它重复检查每条边以确保找到最优路径。

最小生成树（MST）算法

连通无向图的最小生成树是连接所有顶点的边的子集，没有任何环，并且具有最小可能总边权重。

Kruskal算法

Kruskal算法通过逐一添加边来构建MST，从最短边开始，且仅添加那些不形成环的边。

def kruskal(graph):
    parent = {}
    
    def find(n):
        while parent[n] != n:
            n = parent[n]
        return n

    def union(n1, n2):
        root1 = find(n1)
        root2 = find(n2)
        parent[root2] = root1

    graph.sort(key=lambda x: x[2])
    for n1, n2, _ in graph:
        parent[n1] = n1
        parent[n2] = n2

    mst = []
    for n1, n2, weight in graph:
        if find(n1) != find(n2):
            union(n1, n2)
            mst.append((n1, n2, weight))
    return mst

该算法首先按权重对所有边进行排序。它使用联合查找数据结构来跟踪连接的组件，并确保不形成环。

Prim算法

Prim算法通过从任意顶点开始，并依次添加从已选择顶点到未选择顶点的最低权重边来构建MST。

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_edges = [(0, start, None)]

    while min_edges:
        weight, vertex, frm = heapq.heappop(min_edges)
        if vertex in visited:
            continue

        visited.add(vertex)
        if frm is not None:
            mst.append((frm, vertex, weight))

        for next_vertex, next_weight in graph[vertex].items():
            if next_vertex not in visited:
                heapq.heappush(min_edges, (next_weight, next_vertex, vertex))
    return mst

Prim算法使用优先队列来始终扩展当前边缘上具有最低成本的节点。

结论

图算法提供了解决节点和边网络相关问题的广泛解决方案。无论是寻找最短路径、最优连接还是遍历节点，这些算法在高效解决复杂问题中起着至关重要的作用。了解基本定义、表示和主要算法，如BFS、DFS、Dijkstra、Bellman-Ford、Kruskal和Prim，对于在实际应用中利用图算法至关重要。

标记为已读

研究生 → 9.3.1

username

完成于研究生

图算法