第8章 图

目录

• 一、图的基本概念
• 二、图的基本运算
• 三、图的基本存储结构
  • 3.1 邻接矩阵及其实现
    • 3.1.1 邻接矩阵存储结构
    • 3.1.2 建立网络的邻接矩阵算法（算法）
  • 3.2 邻接表及其实现
    • 3.2.1 邻接表存储结构
    • 3.2.2 建立无向图的邻接表算法（算法）
  • 3.3 邻接多重表
• 四、图的遍历
  • 4.1 深度优先遍历（DFS）
  • 4.2 广度优先遍历 （BFS）
• 五、生成树与最小生成树 （无向网）
  • 5.1 最小生成树的定义
  • 5.2 最小生成树的普里姆(Prim)算法
  • 5.3 最小生成树的克鲁斯卡尔(Kruskal)算法
• 六、最短路径 （有向网）
  • 6.1 单源最短路径（Dijkstra算法）
  • 6.2 所有顶点对的最短路径 （Floyd算法）
• 七、拓扑排序 （AOV网）
• 八、关键路径 （AOE网）
• 九、算法设计题
  • 9.1 求一个顶点的度（真题）（算法）
  • 9.2 往图中插入一个顶点（算法）
  • 9.3 往图中插入一条边（算法）
• 十、错题集

一、图的基本概念

1. 图 \(G\) 的顶点集：记作 \(V(G)\)
2. 图 \(G\) 的边集：记作 \(E(G)\)
3. 无向图的边：顶点 \(v\) 到 顶点 \(u\) 的边记作 \((u,v)\)
4. 有向图的边：顶点 \(v\) 到 顶点 \(u\) 的边记作 \(<u,v>\)
5. 邻接点：若 \((v,u)\) 是一条无向边，则称 \(u\) 和 \(v\) 互为邻接点
6. 顶点和边数的关系：
   1. \(n\) 个顶点的无向图，其边数 \(e\) 小于等于 \(n(n-1)/2\)。边数恰好为 \(n(n-1)/2\) 的无向图称为无向完全图
   2. \(n\) 个顶点的有向图，其边数 \(e\) 小于等于 \(n(n-1)\)。边数恰好为 \(n(n-1\) 的有向图称为有向完全图
7. 无向图顶点的度：顶点相关联的边的数目，顶点 \(v\) 的度记为 \(D(v)\)
8. 有向图顶点的度：
   1. 入度：以顶点 \(v\) 作为终点的边的数目，记为 \(ID(v)\)
   2. 出度：以顶点 \(v\) 作为始点的边的数目，记为 \(OD(v)\)
   3. 注：有向图顶点的度等于顶点的入度和出度之和
9. 顶点数 \(n\)、边数 \(e\) 和度数的关系：\(e=\frac{1}{2}\sum_{i=1}^n{D(v_i)}\)
10. 有向图路径：存在一个顶点序列 \(v,v_1,v_2,\cdots,v_m,u\)，且 \((v,v_1),(v_1,v_2),\cdots,(v_m,u)\) 都属于 \(E(G)\)，则该顶点序列为 \(v\) 到 \(u\) 的一条路径
11. 无向图路径：有向图路径：存在一个顶点序列 \(v,v_1,v_2,\cdots,v_m,u\)，且 \(<v,v_1>,<v_1,v_2>,\cdots,<v_m,u>\) 都属于 \(E(G)\)，则该顶点序列为 \(v\) 到 \(u\) 的一条路径
12. 简单路径：一条路径除了起点 \(v\) 和终点 \(u\) 之外，其余顶点均不相同，该路径称之为一条简单路径
13. 简单回路（简单环）：起点和终点相同（\(v=u\)）的简单路径
14. 无向图连通的概念：
    1. 无向图的连通：顶点 \(v\) 到 \(u\) 之间有路径，则称 \(v\) 和 \(u\) 是连通的
    2. 连通图（无向图）：\(V(G)\) 中任意两个不同的顶点 \(v\) 和 \(u\) 都连通（即有路径），则 \(G\) 为连通图
    3. 连通分量：无向图 \(G\) 的极大连通子图（任何连通图的连通分量都是其本身，非连通的无向图有多个连通分量）
15. 有向图连通的概念：
    1. 强连通图：\(V(G)\) 中任意两个不同的顶点 \(v\) 和 \(u\)，都存在从 \(v\) 到 \(u\) 和从 \(u\) 到 \(v\) 的路径
    2. 强连通分量：有向图的极大强连通子图（任何强连通图的唯一强连通分量是其自身，非强连通的有向图有多个强连通分量）
16. 连通分量和强连通分量注意事项：单个顶点可以属于一个单独的连通分量或强连通分量
17. 权：图的每条边上附上相关的数值
18. 网络（带权图）：图的每条边都赋上一个权

二、图的基本运算

1. 略

三、图的基本存储结构

1. 注：对于以下图的存储结构，都假定顶点序号从 \(0\) 开始，图 \(G\) 的顶点集一般形式为 \(V(G)=\{v_0,\cdots,v_i,\cdots,v_{n-1}\}\)

3.1 邻接矩阵及其实现

1. 图的邻接矩阵表示法：用两个表格分别存储数据元素（顶点）的信息和数据之间的关联（边）信息
   1. 一维数组（顺序表）：存储数据元素的信息
   2. 二维数组（邻接矩阵）：存储数据元素之间的关系
2. 邻接矩阵的性质：若 \((v_i,v_j)或<v_i,v_j>\in{E(G)}\)，\(A[i,j]=1\)；若 \((v_i,v_j)or<v_i,v_j>\notin{E(G)}\)，\(A[i,j]=0\)
3. 无向图的邻接矩阵：该邻接矩阵一定是对称的，可以采用上（下）三角矩阵进行压缩存储，存储空间为 \(n(n+1)/2\)
4. 有向图的邻接矩阵：该邻接矩阵不一定是对称的，存储空间为 \(n^2\)
5. 无向图顶点 \(v_i\) 的度数：\(D(v_i) = \sum_{j=0}^{n-1}A[i,j]=\sum_{j=0}^{n-1}A[j,i]\) （对称矩阵\(A=A^T\)）
6. 有向图顶点 \(v_i\) 的度数：
   1. 出度：\(OD(v_i)=\sum_{j=0}^{n-1}A[i,j]\)
   2. 入度：\(ID(v_i) = \sum_{j=0}^{n-1}A[j,i]\)
7. 图邻接矩阵图：
8. 网络的邻接矩阵性质：

\[A[i,j]=

\begin{cases}

W_{ij} &\qquad \text{当$(v_i,v_j)$或$<v_i,v_j>$$\in$E(G)} \\

0 &\qquad \text{当$(v_i,v_j)$或$<v_i,v_j>$$\notin$E(G)且i=j} \\

\infin &\qquad \text{当$(v_i,v_j)$或$<v_i,v_j>$$\notin$E(G)且i$\neq$j}

\end{cases}

\]

1. 图网络邻接矩阵图：

3.1.1 邻接矩阵存储结构

#define FINITY 5000 // 用5000表示无穷大
#define M 20 // 最大顶点数
typedef char vertextype; // 顶点值类型
typedef int edgetype; // 权值类型
typedef struct {
    vertextype vexs[M]; // 顶点信息域
    edgetype edges[M][M]; // 邻接矩阵
    int n, e; // 图中顶点总数和边数
} Mgraph;
           

3.1.2 建立网络的邻接矩阵算法（算法）

1. 算法步骤：
   1. 打开文件
   2. 读入图中的顶点数和边数
   3. 读入图中的顶点值
   4. 初始化邻接矩阵
   5. 读入网络中的边
   6. 建立无向图邻接矩阵
   7. 关闭文件

3.2 邻接表及其实现

1. 邻接表与邻接矩阵的区别：
   1. 顶点个数为 \(n\) 的图，邻接矩阵的存储空间为 \(n^2\) ，而使用邻接表则可节省很多空间
   2. 邻接矩阵表示法唯一，而邻接表的表示法不唯一
2. 邻接表中的两个结点：
   1. 表头结点：存储顶点的数据域（\(vertex\)）和头指针域（\(firstedge\)）
   2. 边表结点：邻接点域（\(adjvex\)）和链域（\(next\)）
3. 邻接表的随机访问任意顶点的构造：让所有头结点顺序存储在一个向量中
4. 图无向图邻接表：
5. 有向图
   1. 出边表（邻接表）：表结点存储以顶点 \(v\) 为始点射出的一条边
   2. 入边表（逆邻接表）：表结点存储以顶点 \(v\) 为终点射出的一条边
6. 图有向图的邻接表：
7. 邻接表存储空间：无向图（\(n\) 个顶点和 \(e\) 条边）用邻接表存储需要 \(n\) 个头结点和 \(2e\) 个边结点
8. 注：当 \(e\) 远小于 \(n(n-1)/2\) 时，邻接表存储图比邻接矩阵存储图节省空间
9. 无向图的度（邻接表）：顶点 \(v_i\) 的度为第 \(i\) 个链表中结点的个数
10. 有向图的度（邻接表-出边表）：
    1. 出度：第 \(i\) 个链表中的结点的个数
    2. 入度：所有链表中其邻接点域的值为 \(i\) 的结点的个数

3.2.1 邻接表存储结构

#define M 20 // 预定义图的最大顶点数
typedef char datatype; // 定点信息数据域
// 边表结点类型
typedef struct node {
    int adjvex; // 邻接点
    struct node *next;
} edgenode;
// 头结点类型
typedef struct vnode {
    datatype vertex; // 顶点信息
    edgenode *firstedge; // 邻接链表头指针
} vertexnode;
// 邻接表类型
typedef struct {
    vertexnode adjlist[M]; // 存放头结点的顺序表
    int n, e; // 图的顶点数与边数
} linkedgraph;
           

3.2.2 建立无向图的邻接表算法（算法）

1. 算法步骤：
   1. 打开文件
   2. 读入顶点数和边数
   3. 读入顶点信息
   4. 边表置为空
   5. 循环 e（边数） 次建立边表
      1. 输入无序对 \((i,j)\)
      2. 邻接点序号为 \(j\)
      3. 将新结点 \(*s\) 插入顶点 \(v_i\) 的边表头部
   6. 关闭文件

3.3 邻接多重表

1. 邻接多重表由两个表组成：
   1. 表头结点：\(vertex\) 域存储顶点的相关信息；\(firstedge\) 存储第一条关联于 \(vertex\) 顶点的边
   2. 边表结点：\(mark\) 域标志图的遍历算法中是否被搜索过；\(vex_i\) 和 \(vex_j\) 表示边的两个顶点在图中的位序；\(link_i\) 和 \(link_j\) 表示两个边表结点指针。
      1. \(link_i\) 指向关联于顶点 \(vex_i\)的下一条边；\(link_j\) 指向关联于顶点 \(vex_j\) 的下一条边
   3. 边表结点的顺序如下表所示：

      1. \(mark\)	\(vex_i\)	\(link_i\)	\(vex_j\)	\(link_j\)

四、图的遍历

4.1 深度优先遍历（DFS）

1. 深度优先遍历步骤：
   1. 选取一个源点 \(v\in{V}\)，把 \(v\) 标记为已被访问
   2. 使用深度优先搜索方法依次搜索 \(v\) 的所有邻接点 \(w\)
   3. 如果 \(w\) 未被访问，以 \(w\) 为新的出发点继续进行深度优先遍历
   4. 如果从 \(v\) 出发，有路的顶点都被访问过，则从 \(v\) 的搜索过程结束
   5. 如果图中还有未被访问过的顶点（该图有多个连通分量或者强连通分量），则再任选一个未被访问的顶点开始新的搜索
2. 注：深度优先遍历的顺序是不一定的，但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的
3. 图深度优先遍历：

4.2 广度优先遍历 （BFS）

1. 广度优先遍历步骤：
   1. 从图中某个源点 \(v\) 出发
   2. 访问顶点 \(v\) 后，尽可能先横向搜索 \(v\) 的所有邻接点
   3. 在访问 \(v\) 的各个邻接点 \(w_k,\cdots,w_k\) 后，从这些邻接点出发依次访问与 \(w_1,\cdots,w_k\) 邻接的所有未曾访问过的顶点
   4. 如果 \(G\) 是连通图，访问完成；否则另选一个尚未访问的顶点作为新源点继续上述搜索过程，知道图 \(G\) 的所有顶点均被访问
2. 注：广度优先遍历无向图的过程中，调用 \(bfs（函数：从顶点\,i\,出发广度优先遍历图\,g\,的连通分量）\) 的次数就是该图连通分量的个数
3. 图广度优先遍历：

五、生成树与最小生成树 （无向网）

1. 生成树：对于一个无向的连通图 \(G\)，设 \(G'\) 是它的一个子图，如果 \(G'\) 中包含了 \(G\) 中所有的顶点，且 \(G'\) 是无回路的连通图，则称 \(G'\) 为 \(G\) 的一颗生成树
2. 图生成树：
3. 生成森林：如果 \(G\) 是非连通的无向图，需要若干次从外部调用 \(DFS（或BFS）\) 算法才能完成对 \(G\) 的遍历。每一次外部调用，只能访问 \(G\) 的一个连通分量，经过该连通分量的顶点和边构造出一颗生成树，则 \(G\) 的各个连通分量的生成树组成了 \(G\) 的生成森林
4. 图生成森林：

5.1 最小生成树的定义

1. 生成树的权：生成树 \(T\) 的各边的权值总和，记作 \(W(T)=\sum_{(u,v)\in{E}}w_{uv}\)，其中 \(E\) 表示 \(T\) 的边集，\(w_{uv}\) 表示边 \((u,v)\) 的权
2. 最小生成树的权：总权值 \(W(T)\) 最小的生成树称为最小生成树
3. 构造最小生成树的准则：
   1. 必须只使用该网络中的边来构造最小生成树
   2. 必须使用且仅使用 \(n-1\) 条边来连接网络中的 \(n\) 个顶点
   3. 不能使用产生回路的边

5.2 最小生成树的普里姆(Prim)算法

1. 两栖边：假设 \(G=(V,E)\) 是一个连通图，\(U\) 是顶点集 \(V\) 的一个非空真子集，若 \((u,v)\) 是满足 \(u\in{U},v\in{V-U}\) 的边（称这个边为两栖边），且 \((u,v)\) 在所有的两栖边中具有最小的权值（此时，称 \((u,v)\) 为最小两栖边）
2. Prim算法步骤：
   1. 初始化 \(U=\{u_0\}，TREE=\{\}\)
   2. 如果 \(U=V（G）\)，则输出最小生成树 \(T\)，并结束算法
   3. 在所有两栖边中找一条权最小的边 \((u,v)\)（若候选两栖边中的最小边不止一条，可任选其中的一条），将边 \((u,v)\) 加入到边集 \(TREE\) 中，并将顶点 \(v\) 并入集合 \(U\) 中
   4. 由于新顶点的加入，\(U\) 的状态发生变化，需要对 \(U\) 与 \(V-U\) 之间的两栖边进行调整
   5. 转步骤 \(2\)
3. 下图步骤顺序（\(V=\{A,B,C,D,E,F\}\)）：
   1. \(U = \{A\}\)，\(V-U=\{B,C,D,E,F\}\)，\(TREE=\{\}\)，两栖边 \((A,B),(A,C),(A,D),(A,E),(A,F)\)，最小两栖边 \((A,B)\)
   2. \(U = \{A,B\}\)，\(V-U=\{C,D,E,F\}\)，\(TREE=\{(A,B)\}\)，两栖边 \((B,C),(B,D),(B,F),(A,E)\)（\((B,C)\) 比 (\(A,C)\) 小，因此做一个替换），最小两栖边 \((B,D)\)
   3. \(U = \{A,B,D\}\)，\(V-U=\{C,E,F\}\)，\(TREE=\{(A,B),(B,D)\}\)，两栖边 \((B,C),(B,F),(A,E)\)，最小两栖边 \((B,F)\)
   4. \(U = \{A,B,D,F\}\)，\(V-U=\{C,E\}\)，\(TREE=\{(A,B),(B,D),(B,F)\}\)，两栖边 \((B,C),((F,E)\)，最小两栖边 \((B,C)\)
   5. \(U = \{A,B,D,F,C\}\)，\(V-U=\{E\}\)，\(TREE=\{(A,B),(B,D),(B,F),(B,C)\}\)，两栖边 \((F,E)\)，最小两栖边 \((F,E)\)
   6. \(U = \{A,B,D,F,C,E\}\)，\(V-U=\{\}\)，\(TREE=\{(A,B),(B,D),(B,F),(B,C),(F,E)\}\)，两栖边 \(\{\}\)，最小两栖边 \(\{\}\)
4. 图prim算法：

5.3 最小生成树的克鲁斯卡尔(Kruskal)算法

1. 算法步骤：
   1. 将图 \(G\) 看做一个森林，每个顶点为一棵独立的树
   2. 将所有的边加入集合 \(S\)，即一开始 \(S = E\)
   3. 从 \(S\) 中拿出一条最短的边 \((u,v)\)，如果 \((u,v)\) 不在同一棵树内，则连接 \(u,v\) 合并这两棵树，同时将 \((u,v)\) 加入生成树的边集 \(E'\)
   4. 重复步骤 \(3\) 直到所有点属于同一棵树，边集 \(E'\) 就是一棵最小生成树
2. 图kruskal算法：

六、最短路径 （有向网）

6.1 单源最短路径（Dijkstra算法）

1. 距离向量 \(d\)：表示源点可以途径 \(S\) 中的顶点到达 \(V-S\) 中顶点的距离
2. 路径向量 \(p\)：保存路径上第 \(i\) 个顶点的前驱顶点序号（没有的话，默认为 \(-1\)）
3. 算法步骤：
   1. 找到与源点 \(v\) 最近的顶点，并将该顶点并入最终集合 \(S\)
   2. 根据找到的最近的顶点更新从源点 \(v\) 出发到集合 \(V-S\) 上可达顶点的最短路径
   3. 重复以上操作
4. 图Dijkstra算法：
5. 上图求单源最短路径步骤：
   1. 初始化：从源点 \(v1\) 出发得到矩阵，到达个点的最小路径是 \(D_{12}=10\)，\(D_{0}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &\infty &30 &100\\ \end{array}\right ]\)
   2. 第一次：从 \(v2\) 点出发，\(v1\) 和 \(v2\) 保持不变，迭代剩下点 \((v3,v4,v5)\) 的距离后，剩余点的最短路径是 \(v4\)，\(D_{1}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &60（10+50） &30 &100\\ \end{array}\right ]\)
   3. 第二次：从 \(v4\) 点 出发，\(v1,v2,v4\) 保持不变，优化剩余点 \((v3，v5)\) 的最短距离。剩余点的最短路径是 \(v3\)，\(D_{2}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &50（20+30） &30 &90（30+60）\\ \end{array}\right ]\)
   4. 第三次：从 \(v3\) 点出发，\(v1,v2,v4,v3\) 保持不变。优化剩余点 $v5 \(的最短路径，\)D_{3}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\ 0 &10 &50 &30 &60（20+30+10）\ \end{array}\right ]$
6. 源点 \(v1\) 的 \(Dijkstra算法\) 的最短路径（如下表）：

   1. 中间顶点	终点	路径长度
      2	10
      4	3	50
      4	30
      4；3	5	60

7. 距离向量 \(d\) 和路径向量 \(p\)：
8. 图Dijkstra算法的辅助数组：

6.2 所有顶点对的最短路径 （Floyd算法）

1. 算法步骤：略

七、拓扑排序 （AOV网）

1. \(AOV网\) 边的作用：表示活动间（一个顶点表示一个活动）的优先关系
2. 注：（真题）拓扑排序可以判断图中有没有回路（深度遍历优先算法也可以）
3. 算法步骤
   1. 在有向图中找一个没有前驱（入度为 \(0\)）的顶点并输出
   2. 在图中删除该顶点以及所有从该顶点发出的有向边
   3. 反复执行步骤 \(1\) 和 \(2\)，知道所有顶点均被输出，或者 \(AOV\) 网中再也没有入度为 \(0\) 的顶点存在为止
4. 图拓扑排序：

八、关键路径 （AOE网）

1. \(AOE网\) 边的作用：表示活动（一个顶点表示一个活动）持续的时间
2. 事件可能的最早开始时间 \(v_e(i)\)：对于某一事件 \(v_i\)，它可能的最早发生时间 \(v_e(i)\) 是从源点到顶点 \(v_i\) 的最大路径长度

   1. \[\begin{cases}v_e(0) = 0\\v_e(i) = max\{v_e(j)+活动<v_j,v_i>持续的时间\}(1\leq{i}\leq{n-1)}\end{cases}

      \]

3. 事件允许的最晚发生时间 \(v_l(i)\)：对于某一事件 \(v_i\)，它允许的最晚发生时间是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间

   1. \[\begin{cases}v_l(n-1)=v_e(n-1)\\v_l=min\{v_l(j)-len(<v_i,v_j>)\}(0\leq{i}\leq{n-2})\end{cases}

      \]

4. 最早可能开始时间 \(e(i)\) 和 允许的最晚发生时间 \(l(i)\)：

   1. \[\begin{cases}e(k)=v_e(i)\\l(k)=v_l(j)-len(<v_i,v_j>)\end{cases}

      \]

   2. 注：\(k\) 为某条边，即 \(<v_i,v_j>\) 为 \(a_k\)
5. 关键活动：\(e(i) = l(i)\) 的顶点为关键活动
6. 算法步骤：
   1. 求出各个事件的 \(v_e\) 和 \(v_l\) 值后
      1. 计算原则：\(v_e\) 的值越大越好；\(v_l\) 的值越小越好
   2. 求出活动的最早可能开始时间 \(e(i)\) 和 允许的最晚发生时间 \(l(i)\)
   3. 其中满足 \(e(i)=l(i)\) 的活动就是 \(AOE网\) 中的关键活动
7. 图关键路径图：

拓扑序列（v0、v1、v2、v4、v3、v6、v7、v5、v8、v9）每个事件的最早开始时间：
ve（0）=0
ve（1）= 8，ve（2）=6，ve（4）=7；
ve（3）=max{ve（1）+len（a3），ve（2）+len（a4）}=16；
ve（6）=max{ve（2）+len（a5），ve（4）+len（a6）}=16；
ve（7）=max{ve（6）+len（a11），ve（4）+len（a7）}=20；
ve（5）= ve（3）+len（a8）=20；
ve（8）=max{ve（3）+len（a9），ve（6）+len（a10），ve（7）+len（a12）}=35；
ve（9）=max{ve（5）+len（a13），ve（8）+len（a14）}=45；

每个事件允许的最晚发生时间如下：
vl（9）=ve（9）=45
vl（8）=vl（9）-len（<v8，v9>）=45-10=35
vl（5）=vl（9）-len（<v5，v9>）=45-14=31
vl（7）=vl（8）-len（<v7，v8>）=35-6=29
vl（6）=min{vl（7）-len（<v6，v7>），vl（8）-len（<v6，v8>）}=min{27，27}=27
vl（3）=min{vl（5）-len（<v3，v5>），vl（8）-len（<v3，v8>）}=min{27，16}=16
vl（4）=min{vl（6）-len（<v4，v6>），vl（7）-len（<v4，v7>）}=min{18，16}=16
vl（2）=min{vl（3）-len（<v2，v3>），vl（6）-len（<v2，v6>）}=min{6，18}=6
vl（1）=vl（3）-len（<v1，v3>）=13
vl（0）=min{vl（1）-8，vl（2）-6，vl（4）-7}=min{5，0，9}=0
           

1. 图关键路径
2. 图AOE网计算：

九、算法设计题

9.1 求一个顶点的度（真题）（算法）

无向图采用邻接表作为存储结构，求一个顶点的度

1. 算法步骤：
   1. 获取顶点的第一个结点 \(firstedge\)
   2. 如果第一个结点存在，循环获取后续结点

#define M 20 // 预定义图的最大顶点数
typedef char datatype; // 顶点信息数据域
// 边表结点类型
typedef struct node {
    int adjvex; // 邻接点
    struct node *next;
} edgenode;
// 头结点类型
typedef struct vnode {
    datatype vertex; // 顶点信息
    edgenode *firstedge; // 邻接链表头指针
} vertexnode;
// 邻接表类型
typedef struct {
    vertexnode adjlist[M]; // 存放头结点的顺序表
    int n, e; // 图的顶点数与边数
} adjgraph;

int d(adjgraph g, int i) {
    int k = 0;
    edgenode *p;
    p = g.adjlist[i].firstedge;

    while (p) {
        k++;
        p = p->next;
    }
    return k;
}
           

9.2 往图中插入一个顶点（算法）

无向图采用邻接表作为存储结构，往图中插入一个顶点

1. 算法步骤:
   1. 查找并判断待插入的结点是否存在
   2. 判断邻接表是否已满
   3. 上述判断都通过，则插入新顶点

#define M 20 // 预定义图的最大顶点数
typedef char datatype; // 顶点信息数据域
// 边表结点类型
typedef struct node {
    int adjvex; // 邻接点
    struct node *next;
} edgenode;
// 头结点类型
typedef struct vnode {
    datatype vertex; // 顶点信息
    edgenode *firstedge; // 邻接链表头指针
} vertexnode;
// 邻接表类型
typedef struct {
    vertexnode adjlist[M]; // 存放头结点的顺序表
    int n, e; // 图的顶点数与边数
} adjgraph;

void insertvex(adjgraph *g, datatype x) {
    int i = 0, flag = 0;
    // 查找待插入的结点是否存在
    while (!flag && i < g->n) {
        if (g->adjlist[i].vertex == x) flag = 1;
        i++;
    }
    // 判断结点是否存在
    if (flag) {
        printf("结点已存在！");
        getch();
        exit(0);
    }
    // 判断邻接表是否已满
    if (g->n > M) {
        printf("邻接表已满！");
        exit(0);
    }
    // 插入结点
    g->adjlist[g->n].vertex = x;
    g->adjlist[g->n].firstedge = NULL;
    g->n++;
}
           

9.3 往图中插入一条边（算法）

无向图采用邻接表作为存储结构，往图中插入一条边（本题采用前插法）

1. 算法步骤：
   1. 判断边是否已经存在
   2. 在顶点 \(i\) 的链表中插入邻接点 \(j\)；在顶点 \(j\) 的链表中插入邻接点 \(i\)（使用前插法）

#define M 20 // 预定义图的最大顶点数
typedef char datatype; // 顶点信息数据域
// 边表结点类型
typedef struct node {
    int adjvex; // 邻接点
    struct node *next;
} edgenode;
// 头结点类型
typedef struct vnode {
    datatype vertex; // 顶点信息
    edgenode *firstedge; // 邻接链表头指针
} vertexnode;
// 邻接表类型
typedef struct {
    vertexnode adjlist[M]; // 存放头结点的顺序表
    int n, e; // 图的顶点数与边数
} adjgraph;

void insertedge(adjgraph *g, int i, int j) {
    edgenode *p, *s;
    int flag = 0;

    // 判断边是否存在
    if (i < g->n && j < g->n) {
        p = g->adjlist[i].firstedge;
        while (!flag && p) {
            if (p->adjvex == j) flag = 1;
            p = p->next;
        }
        if (flag) {
            printf("边已存在!");
            getch();
            exit(0);
        }
        // 插入无向边(i,j)
        s = (edgenode *) malloc(sizeof(edgenode));
        s->adjvex = j; // 邻接点序号为 j
        s->next = g->adjlist[i].firstedge;
        g->adjlist[i].firstedge = s; // 将新结点*s 插入顶点 vi 的边表头部
        s = (edgenode *) malloc(sizeof(edgenode));
        s->adjvex = i; // 邻接点序号为 i
        s->next = g->adjlist[j].firstedge;
        g->adjlist[j].firstedge = s; // 将新结点*s 插入顶点 vj 的边表头部
    } else
        printf("插入边不合法!");
}
           

十、错题集

1. （真题）判断一个有向图是否存在回路可以利用拓扑排序法和深度优先遍历算法
2. 在一个带权连通图 \(G\) 中，权值最小的边一定包含在 \(G\) 的最小生成树中