5.2.3\*邻接多重表

强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 5.2.3\*邻接多重表


无向图G2


## 邻接多重表结构：

<!-- verified-by-hand -->
> [!success] 已结合原文第 195 页及 Markdown 上下文人工校对
> VexBox 和 AMLGraph 的左花括号丢失，int 与 numVertices 粘连。
#define MAXV 100
typedef struct EBox
{
    bool mark;
    int ivex, jvex;
    struct EBox *ilink, *jlink;
    int weight;
} EBox;
typedef struct VexBox
{
    char data;
    EBox *first;
} VexBox;
typedef struct
{
    VexBox VerticesList[MAXV];
    int numVertices, numEdges;
} AMLGraph;


## 邻接多重表的遍历：

<!-- verified-by-hand -->
> [!success] 已结合原文第 195 页及 Markdown 上下文人工校对
> for 循环缺少复合语句花括号，EBox 大小写错误，函数末尾多出一个花括号。
void TraverseEdges_AMLGraph(AMLGraph G)
{
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        EBox *p = G.VerticesList[i].first;
        while (p != NULL)
        {
            if (!p-&gt;mark)
            {
                visit(p);
                p-&gt;mark = true;
            }
            p = (i == p-&gt;ivex) ? p-&gt;ilink : p-&gt;jlink;
        }
    }
}


<!-- page 197 -->

## 5.2.4\*十字链表


(a) 有向图


(b)十字链表

## 十字链表结构：

<!-- verified-by-hand -->
> [!success] 已结合原文第 197 页及 Markdown 上下文人工校对
> ArcBox、VexNode 和 OLGraph 三个结构体的左花括号全部丢失。
#define MAXV 100
typedef struct ArcBox
{
    int tailvex, headvex;
    struct ArcBox *hlink, *tlink;
    int weight;
} ArcBox;
typedef struct VexNode
{
    char data;
    ArcBox *firstin, *firstout;
} VexNode;
typedef struct
{
    VexNode VerticesList[MAXV];
    int numVertices, numEdges;
} OLGraph;


## 十字链表的遍历：

<!-- verified-by-hand -->
> [!success] 已结合原文第 197 页及 Markdown 上下文人工校对
> OL 被识别成数字 0L，中文注释混入语句；while 缺花括号使指针更新落在循环外并造成无限循环。
void TraverseEdges_OLGraph(OLGraph G)
{
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        ArcBox *p = G.VerticesList[i].firstout;
        while (p != NULL)
        {
            visit(p);
            p = p-&gt;tlink;
        }
    }
}


<!-- page 199 -->

## 5.3 图的经典算法

图可以有多种定义，因此对于图算法，核心应该是理清：

功能是什么？适用于什么题目？

步骤有哪些？

## 5.3.1 深度优先遍历

基本思想：沿着图的某一路径尽可能“深入”，直到不能继续为止，再回溯到上一个结点，尝试探索其他路径。其核心是“一条路走到黑，走不通再退回换条路”。这非常类似于树的先序遍历，也像在走迷宫时，沿着一条路走到死胡同，然后原路返回到上一个岔路口，选择另一条路继续探索。

实现原理：DFS的“后进先出”特性天然与栈这种数据结构相匹配。假设未访问的结点用蓝色，表示平静；已加入递归栈中的用橙黄色，表示正在处理中；已处理完的用绿色，表示已经探索完毕。

## 算法步骤 (递归版)

1. 选择一个起始顶点 v，访问它，并标记为已访问（visited [v] = true)。

2. 查找 v 的所有邻接点 w。

3. 如果邻接点 w 未被访问，则从 w 开始进行深度优先遍历（递归调用 DFS(G，w））。

4. 如果v的所有邻接点都已被访问，则函数返回，实现回溯。

## 邻接表的 DFS 代码如下：

<!-- verified-by-hand -->
> [!success] 已结合原文第 199 页及 Markdown 上下文人工校对
> 递归前缺少 visited 判断，遇到无向边会相互递归直至栈溢出；while 花括号和指针更新位置也错误。
bool visited[MAXV] = {false};
void DFS_ALGraph(ALGraph G, int v)
{
    visit(v);
    visited[v] = true;
    for (ArcNode *p = G.VerticesList[v].first; p != NULL; p = p-&gt;next)
        if (!visited[p-&gt;adjvex])
            DFS_ALGraph(G, p-&gt;adjvex);
}
void ans(ALGraph G)
{
    for (int i = 0; i &lt; G.numVertices; i++)
        if (!visited[i]) DFS_ALGraph(G, i);
}


复杂度分析 假设图有n 个顶点和 e 条边。

<!-- page 200 -->

时间复杂度：

邻接表：每个顶点和每条边都只会被访问一次，所以时间复杂度为O(n+e)。

邻接矩阵：需要遍历矩阵来查找每个顶点的邻接点，所以时间复杂度为 O(n²)。

空间复杂度：主要取决于递归深度或栈的大小，最坏情况下需要存储所有顶点，所以空间复杂度为 O(n)。

## 应用场景

寻找连通分量：在一个非连通图中，可以确定有多少个独立的子图。

检测环路：在遍历过程中，如果遇到一个已经访问过且不在当前路径上的祖先结点的顶点，则说明存在环。

拓扑排序：用于有向无环图(DAG)，可以得到一个线性的任务序列。

寻找路径：寻找从一个点到另一个点的路径。

<!-- page 201 -->

## 5.3.2 广度优先遍历

基本思想：相当于树与二叉树的层次遍历。从一个起始顶点开始，首先访问其所有直接相邻的邻接点，然后按距离逐层向外扩展，访问更远的顶点。其核心是“逐层扩散，齐头并进”。这非常类似于树的层次遍历，也像是往平静的水面扔一块石头，水波从中心一圈一圈向外扩散。

实现原理：BFS的“先进先出”特性需要用队列来实现。假设未扫描的结点用蓝色，表示平静；已加入队列的用橙色，表示跃跃欲试待处理；已处理完的用绿色，表示已经探索完毕。


## 算法步骤

1. 选择一个起始（蓝色）顶点v，将其加入队列，标记为已入队（蓝→橙）。

2. 当队列不为空时，循环执行以下操作：

a. 从队头取出一个顶点u，访问该结点。

b. 遍历 u的所有邻接点w：如果 w未入队，则访问w，并将其加入队列，标记为已入队(蓝→橙)。遍历完后u由橙→绿。

邻接表的 BFS 遍历：

bool visited[MAXV] = {false}; // 表示顶点是否已入队
void BFS_ALGraph(ALGraph G, int v)
{
    int queue[MAXV],front = 0, rear = 0;
    //1.将入队，标记
    queue[rear++] = v;
    visited[v] = true;
    //2.如果队列不为空则循环
    while (front &lt; rear)
    {
        // 2-a.选择队头元素 u 访问
        int u = queue[front++];
        visit(u);
        // 2-b.将u 出发可到达的所有未访问顶点加入队列
        ArcNode *p = G.VerticesList[u].first;
        while (p != NULL)
        {
            if (visited[p-&gt;adjvex] != true)
            {
                queue[rear++] = p-&gt;adjvex;
                visited[p-&gt;adjvex] = true;
            }
            p = p-&gt;next;
        }
    }
} void ans(ALGraph G)
{
    //无向图调用BFS 次数等于连通分量数
    for (i=0; i &lt; G.numVertices; i++)
    if (visited[i] != true) BFS_ALGraph(G, i);
}


<!-- page 202 -->

复杂度分析：假设图有Ⅴ个顶点和E条边。

## 时间复杂度：

邻接表：每个顶点和每条边都只会被访问一次，所以时间复杂度为O(n+e)。

邻接矩阵：同样需要查找每个顶点的所有邻接点，时间复杂度为 O(n²)。

空间复杂度：主要取决于队列的大小，最坏情况下需要存储所有顶点，所以空间复杂度为O(n)。

## 应用场景

寻找无权图的最短路径：BFS保证了最先找到目标顶点的路径就是最短的(边数最少)。

检测二分图：一个图是二分图，当且仅当它不包含奇数长度的环。我们可以使用BFS 对图用两种颜色进行着色。 道

<table><tr><td rowspan=1 colspan=1>特性</td><td rowspan=1 colspan=1>深度优先遍历 (DFS)</td><td rowspan=1 colspan=1>广度优先遍历 (BFS)</td></tr><tr><td rowspan=1 colspan=1>数据结构</td><td rowspan=1 colspan=1>栈</td><td rowspan=1 colspan=1>队列</td></tr><tr><td rowspan=1 colspan=1>搜索方式</td><td rowspan=1 colspan=1>莽夫，无路可走再回溯</td><td rowspan=1 colspan=1>谨慎，一层层前进</td></tr><tr><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>O(n)</td></tr><tr><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>邻接表 O(n+e)，邻接矩阵O(n^2)</td><td rowspan=1 colspan=1>邻接表O(n+e)，邻接矩阵O(n^2)</td></tr><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>拓扑排序、找环、找连通分量</td><td rowspan=1 colspan=1>无权图最短路径，二分图</td></tr><tr><td rowspan=1 colspan=1>访问顺序</td><td rowspan=1 colspan=1>不唯一，取决于邻接点的顺序和起始点</td><td rowspan=1 colspan=1>不唯一，取决于邻接点的顺序，但层级固定</td></tr></table>

<!-- page 203 -->

## 5.3.3 最短路径

## 无权图

对于无权图(其实也可以用于权值相同的图），最短路径是指从一个顶点到另一个顶点经过的边数最少的路径。由于每条边的“权重”可以视为1，我们可以使用广度优先搜索（BFS）来寻找最短路径。BFS按层级遍历图，天然地保证了最先到达某个顶点的路径就是最短路径。

思路：使用广度优先搜索(BFS)。从源点开始，逐层向外扩展，第一次访问到某个顶点时，所经过的路径就是从源点到该顶点的最短路径。

## 步骤：

1. 初始化距离数组dist，dist[start]=0，所有其他顶点的距离为无穷大∞。同时，初始化路径数组 path用于记录前驱结点。

2. 创建一个队列，并将源点 start 入队。

3. 队列不为空则循环执行：

a. 从队头取出一个顶点 u。

b. 遍历 u的所有邻接点v。如果ν尚未入队则将ν入队并更新距离。

邻接矩阵代码如下，时间复杂度为 O(n²):

<!-- verified-by-hand -->
> [!success] 已结合原文第 203 页及 Markdown 上下文人工校对
> 源点入队和 BFS 主循环被错误嵌入初始化循环，while 缺花括号；发现邻点后原代码没有将其入队，无法扩展到第二层。
void BFS_ShortestPath(MGraph G, int start)
{
    int queue[MAXV], dist[MAXV], path[MAXV];
    bool visited[MAXV] = {false};
    int front = 0, rear = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    dist[start] = 0;
    queue[rear++] = start;
    visited[start] = true;
    while (front &lt; rear)
    {
        int u = queue[front++];
        for (int v = 0; v &lt; G.numVertices; v++)
        {
            if (!visited[v] &amp;&amp; G.Edge[u][v] != 0)
            {
                dist[v] = dist[u] + 1;
                path[v] = u;
                visited[v] = true;
                queue[rear++] = v;
            }
        }
    }
}


<!-- page 204 -->

如果 dist[v] 为无穷大，就说明未访问过，因此它可以实现 visited 数组的功能，后者是冗余的。所以其实可以基于上面的代码进一步改写。

邻接表代码如下，时间复杂度为O(n+e):

//使用BFS计算无权图的单源最短路径
void BFS_ShortestPath_AL(ALGraph G, int start)
{
    int queue[MAXV];
    int dist[MAXV], path[MAXV];
    int front = 0, rear = 0;
    //1.初始化
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    //2.将源点入队
    dist[start] = 0;
    queue[rear++] = start; //源点入队
    //3.当队列不为空时，循环执行
    while (front &lt; rear) //队列不为空
    {
        // 3-a 队头元素 u 出队
        int u = queue[front++]; //队头元素出队
        p = G.VerticesList[u].first;
        while (p != NULL)
        {
            int v = p-&gt;adjvex;
            // 如果v尚未被访问过
            if (dist[v] == INT_MAX)
            {
                dist[v] = dist[u] + 1; // v的距离是u的距离+1
                path[v] = u; // v的前驱是u
                queue[rear++] = v; //将新访问的顶点v入队
            }
            p = p-&gt;next;
        }
    }
}


<!-- page 205 -->

根据 dist 数组输出长度，根据 path 数组输出路径

<!-- page 206 -->

## 有权图-Dijsktra算法

在一个有权图中，我们要求从一个点出发到达其他所有点需要花费的时间。把这个过程想象成在一张地图上找从你家（起点）到所有其他地方的最短花费时间。

## 1. 初始化

在你家旁边标注”用时0分钟”。

在其他所有地点旁边标注”用时无限长”。

准备一个空集合”已确定最短时间的地点”。

2. 循环：重复以下三步，直到所有地点都已确定。

第一步选择从所有尚未确定的地点中，挑出当前记录用时最短的那个。第一次选的必然是你家（用时0)。

第二步确定 将选出的地点（记为A）加入”已确定”集合，之后不再考察。

第三步 更新对于 A 能直接到达的、尚未确定的每个邻近地点B：计算”从你家到 A的时间”+“从A到B的时间”。若这个总时间比清单上B当前记录的用时更短，则更新。

3. 结束当地图上所有能到达的地点都加入了”已确定”集合，算法结束。此时清单上的记录就是从你家到每个地点的最短时间。

这个算法的精髓（贪心策略）在于：每次都选择当前看起来最近的那个点，并认定它的最短路径已经找到，然后用它来更新其他邻居点的路径。

从已知世界S扩展到未知世界，每次都选择距离源点最近的：