图的邻接表应用实例

什么是图的邻接表表示法？

在计算机科学中，图是一种数据结构，用于表示对象之间的关系。图由节点（顶点）和边组成。邻接表是存储图的一种方式，它通过列表来表示每一对相邻节点的关系。

对于每个节点，我们维护一个指向其所有相邻节点的链表或数组，这种结构简洁且易于实现。

邻接表的基本概念

1. 图数据结构

首先定义一个简单的图数据结构。我们可以使用 Python 实现一个图类 Graph 及其邻接表表示法。

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjacency_list = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        # 添加从节点 u 到节点 v 的边
        self.adjacency_list[u].append(v)

2. 示例图的构建

我们使用上述代码创建一个图，并添加一些边。这里我们构造一个简单例子，表示一个有四个节点的小型图。

# 创建一个具有4个顶点的图并添加边
graph = Graph(4)

# 边之间的关系
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)

print("图的邻接表表示如下：")
for i in range(graph.vertices):
    print(f"节点 {i}: {graph.adjacency_list[i]}")

输出结果将是：

图的邻接表表示如下：
节点 0: [1, 2]
节点 1: [2]
节点 2: [0, 3]
节点 3: [3]

邻接表的应用实例

1. 深度优先搜索 (DFS)

利用邻接列表，我们可以实现图的深度优先遍历（DFS）算法。这里提供一个简单的 DFS 函数：

def dfs(graph, v, visited):
    # 标记当前节点已访问
    visited[v] = True
    print(v, end=' ')

    for i in graph.adjacency_list[v]:
        if not visited[i]:
            dfs(graph, i, visited)

visited = [False] * (graph.vertices)
dfs(graph, 0, visited)

在给定的图中，从节点 0 开始执行 DFS。

2. 广度优先搜索 (BFS)

同样地，利用邻接列表，我们可以实现广度优先遍历（BFS）算法。下面是 BFS 的一个简单实现：

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = [False] * graph.vertices
    visited[start] = True
    
    while queue:
        current_node = queue.popleft()
        print(current_node, end=' ')

        for i in graph.adjacency_list[current_node]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

bfs(graph, 0)

运行上述代码会从节点 0 开始进行 BFS 遍历。

3. 最短路径问题 (单源最短路径 - Dijkstra 算法)

对于具有权重的图，可以使用邻接表来实现 Dijkstra 算法寻找最短路径。这里提供一个简化版的 Dijkstra 算法实现：

import sys

def dijkstra(graph, start):
    n = graph.vertices
    distance = [sys.maxsize] * n
    distance[start] = 0
    visited = [False] * n

    for _ in range(n - 1):
        min_distance = sys.maxsize
        u = None
        # 选择未访问的且距离最小的节点
        for v in range(n):
            if not visited[v] and distance[v] < min_distance:
                min_distance = distance[v]
                u = v

        visited[u] = True

        # 更新邻接节点的距离值
        for v in graph.adjacency_list[u]:
            if not visited[v] and (distance[u] + 1) < distance[v]:
                distance[v] = distance[u] + 1
    
    return distance

distances = dijkstra(graph, 0)
print("从节点 0 出发的最短路径为:", distances)

通过上述代码，我们可以计算出从节点 0 开始到其他所有节点的距离。

结语

通过上述实例可以看出，邻接表表示法在图算法中有着广泛的应用。它可以有效地支持各种图操作和算法实现，如深度优先搜索、广度优先搜索及最短路径问题等。