第 6 章　图

6.1　图的基本概念 高频考点

6.1.1 顶点的度与握手定理

6.1.2 完全图、连通与树图

6.2　图的存储结构

图的存储要同时安放「顶点」和「多对多的关系」，关系不像线性表那样能靠位置隐含，必须显式记录。主角是两种：邻接矩阵（顺序存储思路）与邻接表（链式存储思路），另有两个改进型号（十字链表、邻接多重表）专门修补它们各自的痛点——「每种结构解决了什么问题」正是选择题的出题点。

6.2.1 邻接矩阵与邻接表

// 邻接矩阵存储（严蔚敏教材风格）

#define MAX_VERTEX_NUM 100
typedef char VertexType;                    // 顶点数据类型
typedef int  EdgeType;                      // 带权图：权值类型
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];        // 顶点表
    EdgeType   arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum;                     // 顶点数、边（弧）数
} MGraph;   // 无向图加边要对称写两格：arcs[i][j] = arcs[j][i] = w

// 邻接表存储（边结点 + 顶点结点 + 图）

typedef struct ArcNode {                  // 边（弧）结点
    int adjvex;                           // 该边指向的邻接点下标
    struct ArcNode *nextarc;              // 指向依附于同一顶点的下一条边
    int weight;                           // 权值（带权图才需要）
} ArcNode;
typedef struct VNode {                    // 顶点结点
    VertexType data;                      // 顶点信息
    ArcNode *firstarc;                    // 该顶点边表的头指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertices;                     // 顶点数组
    int vexnum, arcnum;                   // 顶点数、边数
} ALGraph;

6.2.2 十字链表、邻接多重表与对比

6.3　图的遍历 高频考点

图的遍历要解决「每个顶点可能有多条进入路径」的重复访问问题：设辅助数组 visited[]，初始全 false，访问过的顶点置 true。另一件必须刻进本能的事：从某顶点出发的一次遍历，只能访问到它所在的连通分量（无向）或它能到达的部分（有向）——非连通图的完整遍历要对每个未访问顶点再启动一次。

6.3.1 BFS 与 DFS

// BFS：队列 + visited 标记（邻接表版；入口先清空 visited，再对每个未访问顶点调用 BFS——非连通图多次启动）

bool visited[MAX_VERTEX_NUM];              // 全局辅助数组
void BFS(ALGraph G, int v) {
    visit(v);                              // 访问出发顶点
    visited[v] = true;                     // 入队前就标记！
    EnQueue(Q, v);
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);                     // 队头顶点出队
        for (ArcNode *p = G.vertices[v].firstarc; p != NULL; p = p->nextarc)
            if (!visited[p->adjvex]) {     // 只处理未访问的邻接点
                visit(p->adjvex);
                visited[p->adjvex] = true; // 同一顶点绝不二次入队
                EnQueue(Q, p->adjvex);
            }
    }
}

// DFS：递归 + 回溯（邻接表版）

void DFS(ALGraph G, int v) {
    visit(v);                              // 访问
    visited[v] = true;
    for (ArcNode *p = G.vertices[v].firstarc; p != NULL; p = p->nextarc)
        if (!visited[p->adjvex])           // 未访问才递归
            DFS(G, p->adjvex);             // 深入下一层，走完自动回溯
}
void DFSTraverse(ALGraph G) {
    for (int v = 0; v < G.vexnum; v++) visited[v] = false;
    for (int v = 0; v < G.vexnum; v++)
        if (!visited[v]) DFS(G, v);        // 非连通：调用几次就有几个分量
}

6.3.2 遍历的应用与复杂度

void DFS(ALGraph G, int v) {
    visit(v);
    visited[v] = ________;                     // ①
    for (ArcNode *p = G.vertices[v].firstarc; p != NULL; p = p->nextarc)
        if (________)                          // ②
            DFS(G, ________);                  // ③
}

6.4　最小生成树 高频考点

6.4.1 Prim：逐步加顶点

对图 6-2 从 \(v_0\) 出发手工模拟（候选边按「权值最小，权同取两端编号小者」）：

得 MST 边集 \(\{(0,2),(2,1),(1,3),(3,4),(4,5)\}\)，权和 \(1+2+3+2+4=\)12（恰 \(n-1=5\) 条 ✓）。

6.4.2 Kruskal：逐步加边

对图 6-2 手工模拟（排序后依次：(0,2)1、(2,1)2、(3,4)2、(1,3)3、(0,1)4、(4,5)4、(2,4)5、(3,5)6）：

边集与 Prim 完全一致，权和同为 12 ✓——同一图两法殊途同归。

6.5　最短路径 高频考点

6.5.1 Dijkstra：逐步填表

对图 6-2（无向边双向可走）从 \(v_0\) 出发手工填表（格子记「路径长（前驱）」，加粗=本轮确定）：

最终 \(dist=[0,3,1,6,6,10]\)，\(prev=[-,2,0,1,2,4]\)。逐条核对：\(0\to2=1\) ✓；\(0\to2\to1=1+2=3\)（比直连 4 更短）✓；\(0\to2\to1\to3=3+3=6\) ✓；\(0\to2\to4=1+5=6\) ✓；\(0\to2\to4\to5=6+4=10\)（第 4 轮把 12 改成 10）✓。

6.5.2 Floyd 与负权问题

// Floyd 核心：中转点 k 在最外层

for (int k = 0; k < n; k++)              // 依次放开每个中转点
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (A[i][k] + A[k][j] < A[i][j])
                A[i][j] = A[i][k] + A[k][j];   // i→k→j 更短则改道

6.6　拓扑排序与关键路径 高频考点

6.6.1 AOV 网与拓扑排序

6.6.2 AOE 网与关键路径

6.7　章末自测 真题风格

限时 60 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。涉及手工模拟的题，请在草稿纸上把表格完整画出来再对答案。

6.8　本章考点总结