图之邻接表（存储结构、图的遍历、最小生成树、关键路径、最短路径）

阅读量：566 次

发布时间：2019-03-09

本文共 3445 字，大约阅读时间需要 11 分钟。

邻接表的存储结构

邻接表是一种有效地表示图的数据结构，常用于存储无向图或有向图的边和顶点信息。每个顶点通过一个链表头指针（Adjacency List）来连接到它的相邻顶点。这种结构允许在常数时间内访问任意顶点的相邻顶点，以支持各种图的遍历和算法操作。

邻接表的构造

邻接表的构造可以分为顶点初始化和边插入两个主要步骤：

顶点初始化：

为每个顶点分配一个数据存储单元，记录顶点自身信息（如顶点标识ID、邻接边的头指针和入度数）。

使用数组存储所有顶点的邻接表头指针，方便后续操作。

边插入：

为每条边的两个顶点找到它们在邻接表中的位置。

为每个顶点创建新的弧节点，记录该弧指向的目标顶点和相关信息。

将新的弧节点添加到目标顶点的邻接表头结点位置，并更新目标顶点的入度。

图的遍历

遍历图是根据特定条件（如深度优先或广度优先）访问所有顶点的操作。以下是两种常见遍历方式的实现：

深度优先遍历（Depth-First Search, DFS）

算法思想：

从图中选取任意一个未访问的顶点作为起点。

访问该顶点，并记录其访问状态。

递归访问起点的所有未被访问的邻接顶点。

重复上述过程，直到所有与起点连通的顶点都被访问。

代码示例（伪代码）：

void DFS(ALGraph G, int v, int visited[]) {
    if visited[v] is 0:
        visited[v] = 1
        for each neighbor w of v:
            if not visited[w]:
                DFS(G, w, visited)
}
void DFSTravel(ALGraph G) {
    // 初始化所有顶点为未访问状态
    visited[0...N] = 0
    for i from 0到N-1:
        如果顶点i未被访问：
            printf("访问顶点")[i]
            DFS(G, i, visited)
}

广度优先遍历（Breadth-First Search, BFS）

算法思想：

使用队列来管理当前需要访问的顶点。

依次从队列中取出顶点，访问其所有未被访问的邻接顶点，并将邻接顶点加入队列。

重复上述过程，直到队列空尽。

代码示例（伪代码）：

void BFSTravel(ALGraph G) {
    // 初始化队列
    queue = []
    for all vertices v:
        if v未被访问:
            将v加入队列
    while 队列不为空:
        从队列尾部取出顶点v
        访问v
        for all neighbors w of v:
            如果w未被访问：
                将w加入队列
                标记w为已访问
    }
}

图的常见算法

以下是用于图操作的几种常见算法：

最小生成树

普利姆算法（Prim）

算法思想：

初始化所有顶点的闭环边数组，记录从已加入树的顶点到其他顶点的最小边。

在闭环边中选择权值最小的边，将其相关顶点加入树，并更新其闭环边。

重复上述步骤，直到所有顶点都被加入树。

代码示例（伪代码）：

void MiniTree_Prim(ALGraph G, int v) {
    // 初始化
    int visited[N] = 0
    for i from 0到N-1:
        closedge[i] = {lowcost: MAX, vex: v_i}
    // 总数顶点或边数
    while 队列中有未访问顶点：
        选择closedge[i].lowcost最小的顶点k
        将k加入树
        对所有顶点k的邻接边进行更新
}

拓扑排序

算法思想：

计算每个顶点的入度。

使用栈记录所有入度为零的顶点。

依次从栈中取出顶点，处理其所连接的边，递减目标顶点的入度。如果目标顶点的入度变为零，则将其加入栈。

如果所有顶点都被处理，则图无环；否则存在环。

代码示例（伪代码）：

void TopologicalSort(ALGraph G) {
    int indegree[N] = 0
    for i从0到N-1:
        for all edges (u, v) 包含顶点i:
            indegree[v] += 1
    int stack[N]
    for i从0到N-1：
        如果indegree[i] == 0:
            将i加入栈
    int count = 0
    while栈不为空：
        v = 栈顶
        将v加入输出序列
        for all neighbors u of v:
            indegree[u] -= 1
            如果indegree[u] == 0:
                将u加入栈
        v = pop

关键路径问题（AOE-网）

算法思想：

计算每个顶点的最早开始时间（earliest start time, EST）和最晚开始时间（latest start time, LST）。

根据最早开始和最晚开始时间确定关键路径。

代码示例（伪代码）：

void TopologicalOrder(ALGraph G) {
    // 和拓扑排序相同
}
void CriticalPath(ALGraph G) {
    // 计算关键路径
}

最短路径问题

迪杰斯特拉算法（Dijkstra）

算法思想：

从源点开始，计算到各顶点的最短路径。

使用优先队列来选择下一次最短路径的扩展。

代码示例（伪代码）：

void ShortestPath_DIJ(ALGraph G, int v0) {
    // 初始化最短距离数组
    D[0...N] = {INF, INF, ..., INF}
    D[v0] = 0
    // 初始化优先队列
    for i from 0到N-1:
        if i == v0:
            D[i] = 0
        else:
            D[i] = INF
    while队列不为空:
        u 取出优先队列
        for all neighbors v of u:
            if D[v] > D[u] + 边权：
                D[v] = D[u] + 边权
                将v加入优先队列
}

弗洛伊德算法（Floyd）

算法思想：

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

初始化距离矩阵为无穷大，源点到自身距离为0。

通过交换顶点顺序，更新距离矩阵中的最短路径。

代码示例（伪代码）：

void ShortestPath_FLOYD(ALGraph G) {
    // 初始化距离矩阵
    D[0...N][0...N] = {INF, INF, ..., INF}
    for i从0到N-1:
        D[i][i] = 0
    // 求所有顶点对之间的最短路径
    for k从0到N-1:
        for i从0到N-1:
            for j从0到N-1:
                如果 D[i][k] + 边权 < D[i][j]:
                    D[i][j] = D[i][k] + 边权
}