本章重点

图的定义和基本术语

图的定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图1 图2
上方两张图：

• 它们的数据元素，如：1、2、3…，就称之为顶点(Vertex)。
• 线性表可以没有数据元素，即空表；树可以没有元素，即空树；但是图中不能没有数据元素，就像古时候皇帝让你作画，你总不能啥都没画，就说你画了一幅江山社稷图吧。故在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
• 图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，也可以称为弧。如上图中黑色和橙色的线，边集可以为空。

那么上面两张图的区别是什么呢？

• 如图1这种没有箭头的边(无方向)，则称这条边为无向边。如果图中每条边都是无向边，则称该图为无向图。
• 如图2这种有箭头的边(有方向)，则称这条边为有向边。如果图中每条边都是有向边，则称该图为有向图。

在无向图中，如果任意两个顶点都有一条边相连，则称该图为无向完全图。
在有向图中，如果任意两个顶点之间都存在方向完全相反的两条边，则称该图为有向完全图。

无向完全图 有向完全图
如上图所示

• 在无向完全图中，总共有n个顶点，就一定有n(n-1)/2条边。
• 在有向完全图中，总共有n个顶点，就一定有n(n-1)条边。

因为在无向完全图中，一个顶点必须指向除了它本身其他所有的顶点，所以一个顶点就一定有n-1条边，但是n个顶点就是n(n-1)，但是这可能会出现重复的情况，所以除2，保证每个顶点不会被重复计算两次。
而有向完全图由于有向，所以边肯定不会出现重复的情况，所以直接计算n(n-1)。
稀疏图：有很少边或弧的图。
稠密图：有较多边或弧的图。
这里的稀疏和稠密都是相对而言的。

基本术语

图的顶点与边之间的关系

权与网
图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或者耗费。带权的图称为网。如下图所示：

子图
设有两个图 G = ( V, {E} )、G1 = ( V1, {E1} )，若V1 ⊆ V，E1 ⊆ E，则称 G1 是 G 的子图。

邻接：有边/弧相连的两个顶点之间的关系

• 存在 ( Vi, Vj ) ，则称为 Vi 和 Vj 互为邻接点
• 存在< Vi, Vj >，则称 Vi 邻接到 Vj ，Vj 邻接自 Vi 。
• 其中 “()” 表示无向图，”<>”表示有向图

关联(依附)：边/弧与顶点之间的关系。存在 ( Vi, Vj ) / < Vi, Vj >，则称该边/弧关联与 Vi 和 Vj 。
如上图(A)中，1与2之间就互为邻接点，记作( 1, 2 )，而连接1到2的边，则称该边依附于顶点1和2。而开头部分的图2，1邻接到5，5邻接自1，记作< 1,5 >，依附同理。

顶点的度：与该顶点相关联的边的数目，记作TD(v)
在有向图中：

• 顶点的度等于该顶点的入度和出度之和。
• 顶点v的入度是以v为终点的有向边的条数，记作ID(v)
• 顶点v的出度是以v为始点的有向边的条数，记作OD(v)

通过上图可以发现，无向图的边数其实就是个顶点度数和的一半，多出的一半是因为重复两次的计数；而有向图的就是就是入度和或者出度和，因为任意一条线必然都属于入度或者出度。

问：当有向图中仅有一个顶点的入度为0，其余顶点的入度均为1，此时图是何种形状？
答：我们可以依题画出这样一幅图，可以很明显的发现是树型结构，而且是一棵有向树。

路径：接续的边构成的顶点序列
路径长度：路径上边或弧的数目/权值之和。
回路(环)：第一个顶点和最后一个顶点相同的路径。
简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。
简单回路(简单环)：除路径起点和终点外相同外，其余顶点均不相同的路径。

连通图的相关术语

连通图
在无向图 G = ( V, {E} )中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图。

如上左图中的任一顶点，都有到其余任一顶点的路径，故为连通图；而上右图中显然做不到，V0无法到达V4，故为非连通图。
而在有向图中，如果任意两个顶点之间都有路径的话，则称为强连通图。

如上左图中，任一顶点都能到其余顶点，故为强连通图；而上右图，V0到V1有路径，而V1到V0显然没有路径，故为非强连通图。

连通分量
无向图 G 的极大连通子图称为G的连通分量。
极大连通子图的意思是：该子图是 G 连通子图，将 G 的任何不在该子图中的顶点加入，子图就不再连通。

有向图 G 的极大强连通子图称为G的强连通分量。
极大强连通子图意思是：该子图是 G 的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通。

极小连通子图：该子图是 G 的连通子图，在该子图中删除任何一条边子图都不再连通。
生成树：包含无向图 G 所有顶点的极小连通子图。
生成森林：对非连通图，由各个连通分量的生成树的集合。

图的类型定义

ADT Graph {
    数据对象V:具有相同特性的数据元素的集合，称为顶点集。
  数据关系R:R={VR}
        VR={ <v,w>|<v,w>| v,weV A p(v,w),<v,w>表示从v到w的弧，P(v,w)定义了弧<v,w>的信息 }
  基本操作P:
      Create_Graph() :图的创建操作。
      - 初始条件:无。
      - 操作结果:生成一个没有顶点的空图G。
    GetVex(G, v):求图中的顶点v的值。
        - 初始条件:图G存在，v是图中的一个顶点。
      - 操作结果:生成一个没有顶点的空图G。
    CreateGraph(&G,V,VR)
            - 初始条件:V是图的顶点集，VR是图中弧的集合。
      - 操作结果:按V和VR的定义构造图G。
    DFSTraverse(G)
        - 初始条件:图G存在。
      - 操作结果:对图进行深度优先遍历。
    BFSTraverse(G)。
        初始条件:图G存在。
      操作结果:对图进行广度优先遍历。
}ADT Graph

图的存储结构

图的逻辑结构：多对多
所以图中没有顺序存储结构，但可以借助二维数组来表示元素间的关系。这种就是数组表示法(邻接矩阵)
链式存储结构：之前线性表中我们，我们采用指针域指向其后继或者前驱；在树中采用指针域指向其孩子结点，但是图中一个顶点可能指向其他多个顶点，所以我们采用多重链表的方式。
多重链表：

• 邻接表
• 邻接多重表
• 十字链表

重点介绍：数组表示法(邻接矩阵)和邻接表(链式)表示法

邻接矩阵(数组)

建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间的关系)。

图的邻接矩阵是一个二维数组A.arcs[n][n]，定义为：

无向图的邻接矩阵表示法

观察这个矩阵图，可以发现：

1. 无向图的邻接举证是对称的。应为两个顶点之间是互为连接关系，在表中就会被记录两次。
2. 顶点 i 的度 = 第 i 行(列)中 1 的个数。因为只有和该顶点连接的的顶点才会记录为1。
3. 完全图的邻接矩阵中，对角元素为0，其余元素都为1。因为完全图一个顶点指向了其余全部顶点。

有向图的邻接矩阵表示法

注意：在有向图的邻接矩阵中

• 第 i 行含义：以结点 vi 为尾的弧(即出度边)；
• 第 i 列含义：以结点 vi 为头的弧(即入度边)；

观察这个矩阵图，可以发现：

1. 顶点的出度 = 第 i 行元素之和
2. 顶点的入度 = 第 i 列元素之和
3. 顶点的度 = 第 i 行元素之和 + 第 i 列元素之和

网(即有权图)的邻接矩阵表示法
定义为：

邻接矩阵的存储表示

用两个数组分别存储顶点表和邻接矩阵：

#include <limits.h>
#define MAXVEX INT_MAX    // 表示极大值(无穷大)
#define MVNUM 100        // 最大顶点数
typedef char VerTexType;    // 设顶点的数据类型为字符串
typedef int ArcType;        // 设边的权值类型为整型
typedef struct {
    VerTexType vexs[MVNUM];        // 顶点表
    ArcType arcs[MVNUM][MVNUM];    // 邻接矩阵
    int vernum, arcnum;            // 图的当前顶点数和边数
} AMGraph;

采用邻接矩阵表示法创建无向网
算法思想

1. 输入总顶点数和总边数。
2. 依次输入点的信息存入顶点表中。
3. 初始化邻接矩阵，使每个权值初始化为极大值。
4. 构造邻接矩阵。

实现代码：

void CreateAMGraph(AMGraph* G) {
    int i, j, k, w;
    char v1, v2;
    printf("输入顶点数和边数：");
    scanf("%d %d", &G->vernum, &G->arcnum);    // 输入顶点数和边数
    printf("请输入顶点表内容：");
    getchar();    // 清空输入缓冲区
    // 输入顶点信息，建立顶点表
    for (i = 0; i < G->vernum; i++) {
        scanf("%c", &G->vexs[i]);
    }
    getchar();    // 清空输入缓冲区
    // 邻接矩阵初始化，把所有节点的大小都修改成无穷大
    for (i = 0; i < G->vernum; i++) {
        for (j = 0; j < G->vernum; j++) {
            G->arcs[i][j] = MAXVEX;
        }
    }
    // 输入邻接矩阵的值
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入邻接矩阵(vi,vj)中的vi和vj，并输入它们边的权：");
        scanf("%c %c %d", &v1, &v2, &w);
        getchar();    // 清空输入缓冲区
        i = LocateVex(*G, v1);    // 判断v1元素的位置
        j = LocateVex(*G, v2);    // 判断v2元素的位置
        G->arcs[i][j] = G->arcs[j][i] = w;    // 赋予它们边的权值
    }
}

上方我们用到了LocateVex函数，这个函数可以返回v1在顶点表中的位置，我们可以遍历顶点表，返回返回符合要求的元素索引位置，如果没有查找到，则返回-1：

int LocateVex(AMGraph G, VerTexType u) {
    int i;
    for (i = 0; i < G.vernum; i++) {
        if (u == G.vexs[i]) return i;
    }
    return -1;
}

那么建设好了无向网，有向网应该怎么创建呢？
我们仅需要为G->arcs[i][j]赋值，而不需要为G->arcs[j][i]赋值，就可以达到要求，注意在有向邻接矩阵中，行代表出度，列代表入度。

邻接矩阵的优点和缺点

邻接矩阵的优点

• 直观、简单、好理解
• 方便检查任意一对顶点间是否存在边
• 方便找任一顶点的所有”邻接点”(有变直接相连的顶点)
• 方便计算任一顶点的”度”(从该点发出的边数为”出度”，指向该点的边数为”入度”)
• 无向图：对应行(或列)非0元素的个数
• 有向图：对应行非0元素的个数为”出度”，列非-元素的个数为”入度”

邻接矩阵的缺点

• 不便于增加和删除顶点，假设需要增加顶点，则需要添加一行和一列的数据
• 浪费空间，如果存储稀疏图(点很多而变很少)，有大量无效空间(对稠密图/完全图还是很合算的)
• 浪费时间，假设统计稀疏图一共有多少条边，则时间复杂度为O(N2)

邻接表(链式)

无向图的邻接表

顶点：按编号顺序将顶点数据存储在一维数组中。
关联同一顶点的边(以顶点为尾的弧)：用线性链表存储
这就意味着我们先需要一个一维数组，其中存储每一个顶点，同时作为链表的头节点。

• data：存储顶点信息
• firstarc：指向第一个邻接点

同时数组的每一个元素又是一个链表，每个元素都是头节点的邻接点

• adjvex(邻接点域)：存放与Vi邻接的顶点在表头数组中的位置
• nextarc(链域)：指示下一条边或弧
• info(权)：存放当前边的权值

无向图邻接表的特点：

1. 邻接表不唯一
2. 若无向图中有n个顶点、e条边，则其邻接表需n个头节点和2e个表节点，适合稀疏图。
3. 无向图中顶点Vi的度为第i个单链表中的结点数

有向图的邻接表

有向图的邻接表和无向图的邻接表类似，但是链表中存储的是顶点的出度，所以可以得到以下特点：

1. 顶点Vi的出度为第 i 个单链表中的结点个数。
2. 顶点Vi的入度为整个单链表中邻接点域值是 i-1 的结点个数。

由上面两个特点可以得出结论：找出度易，找入度难。

我们还可以把上面的邻接表的链表存储顶点的入度，这就叫做逆邻接表

也可以看出这个邻接表有以下的特点：

1. 顶点Vi的入度为第 i 个单链表中的结点个数。
2. 顶点Vi的出度为整个单链表中邻接点域值是 i - 1 的结点个数。

可以看到这里的特点和前面的相反，所以可以得出结论：找入度易，找出度难。

图的邻接表存储表示

typedef int OtherInfo;
#define MVNUM 100
// 弧(边)的结点结构
typedef struct ArcNode {
    int adjvex;        // 该边所指向的顶点的位置
    struct ArcNode* nextarc;    // 指向下一条边的指针
    OtherInfo info;                // 和边相关的信息，如权..
} ArcNode;
// 顶点的结点结构
typedef struct VNode {
    VerTexType data; // 顶点信息
    ArcNode* firstarc;    // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNUM];
// 定义 AdjList arr 实际上就等同于 VNode arr[MVNUM]
// 图的结构定义
typedef struct {
    AdjList vertices;    // 存储顶点的数组(vertex的复数)
    int vexnum, arcnum;    // 图的当前顶点数和弧数
} ALGraph;

利用邻接表表示法创建无向网
算法思想：

1. 输入总顶点数和总边数
2. 建立顶点表
   • 依次输入点的信息存入顶点表中。
   • 使每个表头结点的指针域初始化为NULL。
3. 创建邻接表
   • 依次输入每条边依附的两个顶点。
   • 确定两个顶点的序号 i 和 j，建立边结点。
   • 将此边结点分别插入到 Vi 和 Vj 对应的两个边链表的头部。

代码：

Status CreateAdjGraph(ALGraph* G) {
    int i, j, k;
    char v1, v2;
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    getchar();    // 清除输入缓冲区
    printf("请输入各个顶点的值：");
    // 输入图的数据以及将头节点赋为NULL
    for (i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    getchar();    // 清除输入缓冲区
    // 初始化邻接链表
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入邻接矩阵(vi,vj)中的vi和vj：");
        scanf("%c %c", &v1, &v2);
        getchar();    // 清除输入缓冲区
        // 找到vi和vj的位置
        i = LocateVex(*G, v1);
        j = LocateVex(*G, v2);
        // 创建新的结点
        ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode));
        p1->adjvex = j;
        p1->info = 1;
        p1->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p1;
        // 如果是有向邻接表则无需下面这段内容
        ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode));
        p2->adjvex = i;
        p2->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p2;
    }
    return OK;
}

LocateVex函数的实现方式：

int LocateVex(ALGraph G, VerTexType u) {
    int i;
    for (i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == u) {
            return i;
        }
    }
    return -1;
}

邻接表的特点

1. 方便找任一顶点的所有邻接点。
2. 节约稀疏图的空间：需要N个头指针 + 2e个结点(每个结点至少2个域)
3. 计算任一顶点的度：
   • 对于无向图：方便
   • 对于有向图：找出度易，找入度难；需要构造逆邻接表，才方便计算入度。
4. 不方便检查任意一对顶点间是否存在边。

邻接矩阵与邻接表的关系

联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非0元素的个数。
区别：

1. 对于任意确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关，仅和算法有关，如头插法、尾插法…)
2. 邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度为O(n+2e)或O(n+e)。

用途：邻接矩阵多用于稠密图，而邻接表多用于稀疏图。

由于邻接表的各种缺点，这又引出了十字链表和邻接多重表的概念：

十字链表

概述
十字链表是有向图的另一种链式存储结构，我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。
有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。
十字链表存储有向图

• data：存储顶点信息
• firstin：第一个入度边(弧)
• firstout：第一个出度边(弧)

• tailvex：弧尾所在位置
• headvex：弧头所在位置
• hlink：指向下一个弧头相同的弧
• tlink：指向下一个弧尾相同的弧

如图所示：

邻接多重表

邻接表存储无向图

• 优点：容易求得顶点和边的信息。
• 缺点：某些操作不方便(删除一条边需要查找表示此边的两个结点)

造成上面这个缺点的原因就是因为在邻接表中和，任何一条边，都会重复出现两个，除了操作不便，还会造成空间浪费的问题。

• mark：标志域，标记此域是否被搜索过
• ivex：该边依附的两个顶点在表头数组中的位置
• ilink：指向依附于 ivex 的下一条边
• jvex：该边依附的两个顶点在表头数组中的位置
• jlink：指向依附于 jvex 的下一条边
• info：如果是无向网，则存储边的权值

• data：存储顶点有关的信息
• firstedge：指向第一条依附于该顶点的边

如图所示：

图的遍历

遍历定义：从已给的连通图的某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。
我们也可以把一张图比作现实中的图，如景区游览图：

遍历实质：找每个顶点的邻接点的过程。

图的特点：
图中可能存在回路，且图的任一顶点都有可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
如上面的那张图，假设我们从V1顶点开始遍历，那么如果我们想将图的每个结点都遍历一次，则肯定会存在回路。
解决思路：
设置辅助数组 visited[n]，用来标记每个被访问过的顶点。

• 初始状态：visited[i] 为 0
• 顶点 i 被访问，改 visited[i] 为 1，防止被多次访问。

图常用的遍历：深度优先遍历(DFS)和广度优先遍历(BFS)。

深度优先遍历

遍历方法：


一张图可能有多种深度遍历方式，连通图的深度优先遍历类似于二叉树的先根遍历。

邻接矩阵遍历

实现代码：

typedef enum {
    FALSE,
    TRUE
}Boolean;
Boolean visited[MAXVEX];
void DFS(AMGraph G, int i) {
    int j;
    visited[i] = TRUE;    // 将辅助数组的对应未知修改为true
    printf("%d ", G.vexs[i]);    // 输出顶点内容
    for (j = 0; j < G.vernum; j++) {    // 依次遍历顶点
        if (G.arcs[i][j] != 0 && !visited[j]) {    // 如果 该顶点有边不等于0，且在辅助数组中不为true
            DFS(G, j);    // 就递归遍历访问
        }
    }
}

邻接表遍历

实现代码：

void DFS(ALGraph G, int i) {
    int j;
    visited[i] = TRUE;
    printf("%c ", G.vertices[i].data);
    ArcNode* p = G.vertices[i].firstarc;
    while (p && !visited[p->adjvex]) {
        DFS(G, p->adjvex);
        p = p->nextarc;
    }
}

DFS算法效率分析

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度是O(n2)。
用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。
结论：

• 稠密图适于在邻接矩阵上进行深度遍历
• 稀疏图适于在邻接表上进行深度遍历。

广度优先遍历

遍历方法：

实现代码：

void BFS(ALGraph G, int i) {
    int j, u, w;
    SqQueue Q;
    ArcNode* p;
    for (j = 0; j < G.vexnum; j++) {
        visited[j] = FALSE;
    }
    InitQueue(&Q);
    printf("%c ", G.vertices[i].data);
    visited[i] = TRUE;
    EnQueue(&Q, i);
    while (!QueueEmpty(&Q)) {
        DeQueue(&Q, &u);
        p = G.vertices[u].firstarc;
        while (p) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = TRUE;
                printf("%c ", G.vertices[p->adjvex].data);
                EnQueue(&Q, p->adjvex);
            }
            p = p->nextarc;
        }
    }
}

BFS算法效率分析

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行(n个元素)，总的时间复杂度为O(n2)。
如果用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。

DFS和BFS算法的比较

空间复杂度相同，都是O(n)(借用了堆栈或队列)
时间复杂度只与存储结构(邻接矩阵或邻接表)有关，而与搜索路径无关。

图的应用

最小生成树

概念回顾 —— 生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图。

一个图可以由许多可不同的生成树，如上右(2、3、4)图都是上左(1)图的生成树。
所有生成树具有以下共同的特点：

• 生成树的顶点个数与图的顶点个数相同。
• 生成树是图的极小连通子图，去掉一条边则非连通。
• 一共有n个顶点的连通图的生成树有n-1条边。
• 在生成树中再加一条边必然形成回路。
• 生成树中任意两个顶点间的路径是唯一的。

含有n个顶点n-1条边的图不一定是生成树，如上右(5)图则不是上左(1)图的生成树。

无向图的生成树

我们学习过了深度优先遍历和广度优先遍历，那么我们就可以利用这两种遍历方式生成生成树。

设图G = (V, E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分成两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边的集合，B(G)是遍历图时为经过边的集合。显然，G1(V,T)是图G的极小连通子图，即子图G1是连通图G的生成树。

最小生成树概念

最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树成为该网的最小生成树，也叫最小代价生成树。

最小生成树的典型用途
欲在n个城市之间建立通信网，则n个城市应铺n-1条线路。
但因为每条线路都会右对于的经济成本，而n个城市最多有n(n-1)/2条线路，那么如何选择n-1条线路，使总费用最少？
我们可以制作一个数学模型：

• 顶点 —— 表示城市，有n个
• 边 —— 表示线路，有n-1条
• 边的权值 —— 表示线路的经济代价
• 连通网 —— 表示n个城市间通信网

我们只需要依据这个数学模型构造出相应的最小生成树就可以解决我们的问题。

构造最小生成树

构造最小生成树的算法很多，其中多数算法都利用了MST(Minimum Spanning Tree)性质。

MST性质：设 N = (V,E) 是一个连通网，U是顶点集V的一个非空子集，若边(u,v)是一条具有最小权值的边，其中u∈U，v∈V-u，则必存在一棵包含边(u,v)的最小生成树。

在生成树的构造过程中，图中n个顶点分属两个集合：

• 已落在生成树上的顶点集：U
• 尚未落在生成树上的顶点集：V-U

接下来则在应在所有连通U中顶点和V-U中顶点的边中取权值最小的边

普利姆(Prim)算法

算法思想：

• 设N = (V,E)是连通网，TE是N上最小生成树中边的集合。
• 初始令U={u0}，(u0∈V)，TE={}。
• 在所有u∈U，v∈V-U的边(u,v)∈E中，找一条代价最小的边(u0,v0)
• 将(u0,v0)并入集合TE，同时v0并入U。
• 重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树。

如下图：

实现代码：

void MiniSpanTree_Prim(MGraph G) {
    int i, j, k, min;
    // 保存相关顶点间的权值，
    // 之后凡是这个数组中的值设置为0，就表示此下标位置的顶点被纳入最小生成树
    int lowcost[MAXVEX];    
    // 保存顶点间边的权值点的下标
    int adjvex[MAXVEX];        
    lowcost[0] = 0;        // 初始化第一个顶点权值为，即v0加入最小生成树
    adjvex[0] = 0;        // 初始化第一个顶点为v0的下标
    for (i = 1; i < G.vexnum; i++) {
        lowcost[i] = G.arcs[0][i];    // 将v0顶点相关的边的权值加入数组
        adjvex[i] = 0;                // 初始化都为v0的下标
    }
    // 循环一次就确定一条生成树的边，还需要循环n-1次
    for (i = 1; i < G.vexnum; i++) {
        min = INFINITY;        // 初始化最小权值为无穷大，可以是比较大的数字如65535
        j = 1, k = 0;        // j是循环变量，k是最小顶点的下标
        // 循环全部结点
        while (j < G.vexnum) {
            // 如果权值不为0且权值比最小值还小
            // 注意：这里的lowcost[j] != 0是表示已经是生成树的顶点不加入最小权值查找
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("(%d, %d)\n", adjvex[k], k);        // 打印最小权值的边
        lowcost[k] = 0;        // 将选出的下标中的值设置为0，表示此顶点已经加入生成树
        for (j = 1; j < G.vexnum; j++) {
            // 如果权值不为0且下标为k的顶点依附的各个边 小于 其他未被加入生成树的权值
            if (lowcost[j] != 0 && G.arcs[k][j] < lowcost[j]) {
                lowcost[j] = G.arcs[k][j];    // 将较小权值存入lowcost相应位置
                adjvex[j] = k;                // 将下标为k的顶点存入adjvex
            }
        }
    }
}

克鲁斯卡尔(Kruskal)算法

算法思想：

• 设连通网N=(V,E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量。
• 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即：不能形成环)，则将此边加入到T中，否者，舍去此边，选取下一条代价最小的边。
• 依次类推，直至T中所有顶点都在同一连通分量上为止。

如下图：

上面的两种算法，如果我们更改某些边的权值，就会发现构造出的最小生成树变了，所以可以发现，最小生成树可能不唯一。
实现代码：

void swap(Edge* edges, int i, int j)
{
    int temp;
    temp = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = temp;
    temp = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = temp;
    temp = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = temp;
}
void sort(Edge* edges, MGraph* G) {
    int i, j;
    for (i = 0; i < G->arcnum - 1; i++) {
        for (j = 0; j < G->arcnum - i - 1; j++) {
            if (edges[j].weight > edges[j + 1].weight) {
                swap(edges, j, j + 1);
            }
        }
    }
    printf("权排序之后的为:\n");
    for (i = 0; i < G->arcnum; i++)
    {
        printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
    }
}
int find(int* parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}
void MiniSpanTree_Kruskal(MGraph G) {
    int i, j, n, m;
    int k = 0;
    int parent[MAXVEX];
    // 构建边集数组
    Edge edges[MAXVEX];
    for (i = 0; i < G.vexnum - 1; i++) {
        for (j = i + 1; j < G.vexnum; j++) {
            if (G.arcs[i][j] < INFINITY && G.arcs[i][j] != 0) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arcs[i][j];
                k++;
            }
        }
    }
    // 对边集数组进行排序，使权值较小的边在前面
    sort(edges, &G);
    for (i = 0; i < G.vexnum; i++) {
        parent[i] = 0;
    }
    printf("打印最小生成树：\n");
    for (i = 0; i < G.vexnum; i++) {
        n = find(parent, edges[i].begin);
        m = find(parent, edges[i].end);
        if (n != m) {
            parent[n] = m;
            printf("(v%d, v%d)\n", edges[i].begin, edges[i].end);
        }
    }
}

两种算法的比较

最短路径

典型用途：交通网络问题 —— 从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？ 这里的最短不仅仅意味的距离短，还可以抽象为时间短，花费少，换乘少等等情况。

交通网络用有向图来表示：

• 顶点 —— 表示地点
• 弧 —— 表示两个地点有路连通
• 弧上的权值 —— 表示两地点之间的距离、交通费或途中所花费的时间等。

解决类似于这种问题，就是我们的最短路径。

问题抽象：在有向网中A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。

两种常见的最短路径问题：
第一类问题：两点间最短路径

单源最短路径 —— 用Dijkstra(迪杰斯特拉)算法
第二类问题：某源点到其他各点最短路径

所有顶点间的最短路径 —— 用Floyd(弗洛伊德)算法

迪杰斯特拉(Dijistra)算法

• 初始化：先找出从源点v0到各终点vk的直达路径(v0,vk)，即通过一条弧到达的路径。
• 选择：从这些路径中找出一条长度最短的路径(v0,u)。
• 更新：然后对其余各条路径进行适当调整。
• 若在图中存在弧(u,vk)，且(v0,u) + (u,vk) < (v0,vk)，则以路径(v0,u,vk)代替(v0,vk)。
• 在调整后的各条路径中，再找长度最短的路径，依次类推。

迪杰斯特拉(Dihkstra)算法：按路径长度递增次序产生最短路径。

算法思想：

1. 把V分成两组：
   1. S：已求出最短路径的顶点的集合。
   2. T=V-S：尚未确定最短路径的顶点集合。
2. 将T中顶点按最短路径递增的次序加入到S中
   1. 从源点v0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
   2. 每个顶点对应一个距离值：
      1. S中顶点：从v0到此顶点的最短路径长度
      2. T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。

弗洛伊德(Floyd)算法

算法思想：

• 则个顶点试探
• 从vi到vj的所有可能存在的路径中，选出一条长度最短的路径

有向无环图及其应用

有向无环图：无环的有向图，简称 DAG 图。如下图中间的图。

有向无环图常用来描述一个工程或通信系统的进行过程。(通常把计划、施工、生产、程序流程等当成是一个工程)。
一个工程可以分为若干个子工程，只要完成了这些子工程(活动)，就可以导致整个工程的完成。
那我们怎么表示这些子工程(活动)呢？我们有两种表示方式：
AOV网：
用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系。称这种有向图为顶点表示活动的网，简称 AOV 网。

AOE网
用一个有向图表示一个工程的各子工程及其互相制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件。称这种有向图为边表示活动的网，简称 AOE 网。

我们通常用AOV网解决拓扑排序问题，用AOE网解决关键路径问题。

AOV 网的特点
若从 i 到 j 有一条有向路径，则 i 是 j 的前驱，j 是 i 的后继。若 是网中有向边，则 i 是 j 的直接前驱，j 是 i 的直接后继。
AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

拓扑排序

在AOV网中没有回路的前提下，我们将全部活动排列成一个线性序列，使得AOV网中弧存在，则在这个序列中，i 一定排在 j 前面，具有这种性质的线性序列称为拓扑排序。

拓扑排序步骤：

1. 在有向图中选一个没有前驱的顶点输出之。
2. 在图中删除该顶点和所有以它为尾的弧。
3. 重复上述两部，直到全部顶点均已输出，或者当图中不存在无前驱的顶点为止。

按照上图的方式，依据上面三个步骤删除顶点，那么我们应该可以得到如下这么一个序列：

注意：一个AOV网的拓扑排序不是唯一的，有上上方图可以发现，根据我们移除的无前驱顶点的不同，就可以获得不同的拓扑序列。

拓扑排序的一个重要应用
检测AOV网中是否存在环的方法：
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定存在环。如下图中的AOV网则必然存在环，因为依据上面的上面的方法移除顶点后，则必然下面标红线的三个顶点互为前驱。

拓扑排序实现：

要是先拓扑排序，我们首先需要重新定义一下邻接表的存储结构，结构代码如下：

// 边结点域
typedef struct ArcNode {
    int adjvex;                // 存储该顶点对应邻接点的下标
    int weight;                // 用于存储权值
    struct ArcNode* next;    // 链域，指向下一个邻接点
} ArcNode;
// 顶点域
typedef struct VertexNode {
    int in;                    // 顶点入度
    int data;                // 顶点域，存储顶点信息
    ArcNode* firstArc;        // 指向该顶点的第一个邻接点
} VertexNode, AdjList[MAXVEX];    
// 图
typedef struct {
    AdjList adjlist;        // 邻接表
    int vexnum, arcnum;        // 当前图的顶点数和边数
}graphAdjList, * GraphAdjList;

可以发现，和原来相比，就顶点域中多了一个 in 成员变量用于存储顶点入度，当 in = 0 时，就代表该顶点无前驱(无入度)。同时我们还需要辅助的存储结构 —— 栈。用来存储处理过程中的入度为0的顶点。目的是为了避免每次查找都要遍历顶点表找有没有入度为0的顶点。

Status TopologicalSort(GraphAdjList GL) {
    ArcNode* e;
    int i, k, gettop;
    int top = 0;        // 栈顶的下标
    int count = 0;        // 用于统计输出顶点的个数
    int* stack;            // 建议辅助数据结构 —— 栈
    stack = (int*)malloc(sizeof(int) * GL->vexnum);
    if (!stack) exit(OVERFLOW);
    for (i = 0; i < GL->vexnum; i++) {
        if (!GL->adjlist[i].in) {
            stack[++top] = i;        // 将入度为0的顶点入栈
        }
    }
    // 如果栈不为空则继续遍历
    while (top != 0) {
        gettop = stack[top--];        // 取出栈顶元素
        printf("%c -> ", GL->adjlist[gettop].data);    // 输出栈顶元素
        count++;        // 输出元素之后，统计次数+1
        e = GL->adjlist[gettop].firstArc;    // 遍历边集链表
        while (e) {
            // 将栈顶元素的出度(其邻接点的入度)减去
            if (!(--GL->adjlist[e->adjvex].in)) {
                stack[++top] = e->adjvex;    // 如果邻接点的入度为0，加入栈
            }
            e = e->next;    // 指向下一条边
        }
    }
    printf("\n");
    free(stack);    // 释放栈空间
    if (count < GL->vexnum) {    // 如果顶点有未被统计过的，就说明失败
        return ERROR;
    }
    else {
        return OK;
    }
}

关键路径

在学习关键路径之前，我们应该要了解关键路径可以用来做什么。

例如：准备一个小型家庭宴会，晚上6点开始。需要提前准备的事情如下图，那么我们最迟应该几点开始准备？压缩哪项活动的时间可以使总时间减少？

前置任务就是完成这个活动的前提是需要完成哪项活动。
解决方法：

• 把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。
• 事件表示在它之前的活动已经完成，在它之后的活动可以开始。

那么上图就可以表示成这么一张图：

以上图为例：

• 事件 v1 —— 表示整个工程开始 (源点：入度为0的顶点)
• 事件 v7 —— 表示整个工程结束 (汇点：出度为0的顶点)

对于AOE网，我们关心两个问题：

1. 完成整个工程至少需要花费多少时间？
2. 哪些活动是影响工程进度的关键？

那么这些问题都可以转换成关键路径问题：

• 关键路径 —— 路径长度最长的路径。
• 路径长度 —— 路径上各活动持续时间之和。

为了解决关键路径问题，需要定义4个描述量：

• ve(vj) —— 表示事件 vj 的最早发生时间。例：v2最早发生时间为v1结束之后立即开始，ve(v2)=30。
• vl(vj) —— 表示事件 vj 的最迟发生事件。例：假设工程最多需要 180 分钟完成，那么我们求的就是 vj 最迟什么时候就要开始，ve(v4)=180-15=165。
• e(i) —— 表示活动 i 的最早开始时间。例：C最早可以什么什么时候开始，A完成之后即可开始，e(C)=30。
• l(i) —— 表示活动 i 的最迟开始时间。例：还是设工程180分钟完成，那么C最晚什么时候开始，需要先预留出G的时间，再减去C本身需要的时间，l(C)=120。

l(i) - e(i) —— 表示完成活动 i 的时间余量，例：l(C)-e(C)=90。
关键活动 —— 关键路径上的活动，即 l(i)==e(i) ，或者说 l(i)-e(i)==0 的活动。

如何找到 l(i)==e(i) 的关键活动？

设活动 i 用弧 表示，其持续时间记为：Wj, k。
则有：

1. e(i) = ve(j)
2. l(i) = vl(k) - Wj, k

如何求 ve(j) 和 vl(j)？

1. 从 ve(1) = 0 开始向前递推，则 ve(j) = MAX{ve(i) + Wj, k}, ∈T, 2 <= j <= n。其中T是所有以 j 为头的弧的集合。
2. 从 vl(n) = ve(n) 开始往后递推，则 vl(i) = MIN{vl(i) - Wj, k}, ∈S, 1 <= i <= n-1。其中S是所有以 i 为尾的弧的集合。