🔑数据结构_第六章：图

第六章、图

（一）图的基本概念

1、定义：

线性表是一对一，树是一对多，图就是多对多。
图由顶点和边组成，顶点即数据节点，边即顶点间的联系，每条边都一定连接着两个顶点，但每个顶点不一定有几条边相连。
图G由顶点集V和边集E组成，记为G = (V, E)；V(G)表示图G中所有顶点的集合，为有限非空集；E(G)表示图G中所有边的集合，可以是空集。
**|V|表示图G中顶点的总个数，也称图G的阶；|E|**表示图G中边的条数。
线性表可以是空表，树可以是空树，但是图不能是空图！

2、无向图和有向图

无向图
- 边为无向边的图称为无向图，无向边也称为边。
- 边是顶点的无序对，记为(v,w)或(w,v)，其中v、w为顶点/互为邻接点，(v,w)=(w,v)。
- 可以说边(v,w)依附于顶点w和v，或者说边(v,w)与顶点w、v相关联。
对于上图中图G可表示为：
$\begin{aligned} (1) & G_{1} & = (V_{1}, E_{1}) V_{1} & = A, B, C, D, E E_{1} & = (A, B), (B, D), (B, E), (C, D), (C, E), (D, E) \end{aligned}$
有向图
- 边为有向边的图称为有向图，有向边也称为弧：从左指向右，从弧尾指向弧头。
- 弧是顶点的有序对，记为<v,w>，其中v、w为顶点，v称为弧尾，w称为弧头，<v,w>≠<w,v>。
- <v,w>称为从顶点v到顶点w的弧，表示v邻接到w，或w邻接自v。
对于上图中图G可表示为：

$\begin{aligned} (2) & G_{2} & = (V_{2}, E_{2}) V_{2} & = A, B, C, D, E E_{2} & = < A, B >, < A, C >, < A, D >, < A, E >, < B, A >, < B, C >, < B, E >, < C, D > \end{aligned}$

3、简单图与多重图

考研不探讨多重图。

4、顶点的度、入度、出度

对于无向图
- 顶点v的度是指依附于该顶点的边的条数，记为**TD(v)**。
- 无向图中全部顶点（v）的度的和等于边数的2倍，即在具有n个顶点e条边的无向图中：
  $\sum_{i = 1}^{n} T D (v_{i}) = 2 e$
对于有向图
- 入度是以顶点v为终点的有向边的数目，记为ID(v)；
- 出度是以顶点v为起点的有向边的数目，记为OD(v)；
- **顶点v的度TD(v)等于其入度和出度之和：TD(v) = ID(v) + OD(V)**，即在具有n个顶点、e条边的有向图中：
  $\sum_{i = 1}^{n} T D (v_{i}) = \sum_{i = 1}^{n} I D (v_{i}) + \sum_{i = 1}^{n} O D (v_{i})$
- 在具有n个顶点、e条边的有向图中，入度数目=出度数目=边数：
  $\sum_{i + 1}^{n} I D (v_{i}) = \sum_{i + 1}^{n} O D (v_{i}) = e$

5、顶点 - 顶点关系描述

路径：顶点v_p到顶点v_q逐渐的一条路径是指顶点序列：v_p, v_i1, v_i2, v_i3, …… v_q。
回路：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度：路径上边的数目。
点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
无向图——顶点的连通：无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
有向图——顶点的强连通：有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。

6、连通图与强连通图

无向图的连通图

任意两个顶点都是连通的，否则为非连通图。

常见考点——对于n个顶点的无向图G：
- 若G是连通图，则最少有n-1条边；
- 若G是非连通图，则最多可能有C²_n-1条边。
有向图的强连通图

任意一对顶点都是强连通的。

常见考点：
- 对于n个顶点的有向图G，若G是强连通图，则最少应有n条边（形成回路）。

7、子图

对于无向图和有向图来说：设有两个图G=(V, E)和G^‘=(V^‘, E^‘)，若V^‘是V的子集，E^‘是E的子集，则称G^‘是G的子图。

若G^‘和G的顶点完全一样，只是边不同，那么我们称G^‘为G的生成子图。

*注：并非从图G中任意选取一些顶点和边组成的集合就是子图，必须满足这些选出来的顶点和边能组合成正确的图才行！

8、连通分量和强连通分量

极大连通子图：包含尽可能多的顶点和边的连通子图。

极大强连通子图：包含尽可能多的顶点和边的强连通子图。

无向图的连通分量

无向图中的极大连通子图称为无向图的连通分量。
有向图的强连通分量

有向图中的极大强连通子图称为有向图的强连通分量。

9、生成树与生成森林

极小连通子图：边尽可能的少，但要保持联通。

生成树

连通图的生成树是指包含图中全部顶点的一个极小连通子图。

若图G的顶点数为n，则它的生成树含有n-1条边。

对于生成树而言，若砍去它的一条边则会变成非连通图，若加上一条边则会出现一个回路。
生成森林

在非连通图中，连通分量的生成树构成了这个非连通图的生成森林。

10、边的权、带权图/网

边的权：

在一个图中（无论有向或无向），每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网：

边上带有权值的图（无论有向或无向）称为带权图，也称网。
带权路径长度：

当图（无论有向或无向）是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

11、几种特殊的图

（1）完全图

无向完全图：任意两个顶点之间都有边的图。

n个顶点的无向完全图的总边数为**C²_n**个。
有向完全图：任意两个顶点之间都有两条互指的弧的图。

n个顶点的有向完全图的总边数为**2C²_n**个。

（2）稀疏图和稠密图

稀疏图和稠密图是相对而言的，并没有单独的判断标准！

（3）树和森林

树：

不存在回路，且连通的无向图。

n个顶点的树，必有n-1条边。

常见考点：n个顶点的图，若边数|E|>n-1，则一定有回路！
森林：

多个树的集合。
有向树：

一个顶点的入度为0，其余所有顶点的入度均为1的有向图，称为有向树。

入度为0的那个顶点可看作树的根结点。

注：有向树并不是强连通图！

总结：

（二）图的存储与实现

1、邻接矩阵法

（1）普通图

顶点数有n个，那么对应的邻接矩阵大小是n*n。
若将图G的顶点编号为v₁，v₂，…v_n，则：
$$
A[i][j]=
\left{
$\begin{aligned} (3) & 1, & 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 是 E (G) 的边 0, & 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 不是 E (G) 的边 \end{aligned}$
\right.
$$
无向图的邻接矩阵是个对称矩阵，而有向图的不是。
有向图中：A指向B，那么在矩阵中的A行B列的值为1（横的指向竖的）。
无向图的度等于结点自身所在行或列的非0元素个数。
有向图的入度等于节点所在列的非0元素个数，而出度等于节点所在行的非0元素个数，度等于二者之和。
两种图的的邻接矩阵法求顶点的度/入度/出度的时间复杂度均为O(|V|)。

（2）带权图

在普通图的基础上稍加改造即可，可将原先矩阵中表示有连接的数字1用权值替代，没有边的位置用自定义的数字表示。（根据实际业务需求决定）。

（3）性能分析

空间复杂度通常很高，只适合存储稠密图。

（4）邻接矩阵的特殊性质

设图G的邻接矩阵为A(矩阵元素为0和1)，则Aⁿ的元素Aⁿ[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

2、邻接表法

//定义“顶点”
typedef struct VNode{
    int data;		            //顶点信息
    ArcNode *first;			    //第一条边/弧
}VNode, AdjList[100];           //将该顶点结构变换为一个顶点数组

//定义“边/弧”
typedef struct ArcNode{
        int adjvex;				//边/弧指向哪个顶点
        struct ArcNode *next;	//指向下一条弧的指针
        //InfoType info;		//边的权值
};

//定义图
typedef struct{
    //声明图里面的顶点数组
    AdjList vertices;
    //定义顶点和边/弧的数量
    int vexnum, arcnum;
}ALGraph;

注：图的邻接表表示结果并不唯一！而用邻接矩阵法表示时，只要确定了顶点编号，那么矩阵就是唯一的！

邻接表与邻接矩阵对比：

	邻接表	邻接矩阵
空间复杂度	无向图O(\|V\|+\|2E\|)，有向图O(\|v\|+\|E\|)	O(\|V\|²)
适合用于	存储稀疏图，稠密图也可	稠密图
表示方式/表示结果	不唯一	唯一
计算度/出度/入度	计算有向图的度、入度不方便，其余很方便	须遍历对应行或列，较为方便
找相邻的边	找有向图的入边不方便，其余都方便	须遍历对应行或列，较为方便

3、十字链表、邻接多重表（工大不考）

十字链表用于存储有向图，邻接多重表由于存储无向图。

（1）十字链表法

空间复杂度：O(|E|+|V| )。
如何找到指定顶点的所有出边？——顺着绿色线路找。
如何找到指定顶点的所有入边？——顺着橙色线路找。

注：十字链表法只适合存储有向图！

（2）邻接多重表法

空间复杂度：O(|V|+|E|)。
删除边、结点等操作很方便。

注：邻接多重表只适用于存储无向图！

（三）图的基本操作

1、`Adjacent(G,x,y)`：

判断图G是否存在边(x,y)或<x,y>：

对于无向图：

邻接矩阵法：

只需判断两个目标结点在邻接矩阵中的对应位置的矩阵元素值是否为1即可，为1则存在，为0不存在。

时间复杂度为O(1)。

邻接表法：

遍历其中一个结点的所有边结点。

时间复杂度：O(1)~O(|V|)。
对于有向图：

原理同上。

2、`Neighbors(G, x)`：

列出图G中与结点x相邻的边：

无向图：

邻接矩阵法：

遍历目标节点在矩阵中的所在行/列，把值为1的元素全找出来即可。

时间复杂度为O(|V|)。

邻接表：

遍历目标结点对应的链表即可

时间复杂度：O(1)~O(|V|)。
有向图

邻接矩阵法：

找出边遍历对应的行，找入边遍历对应的列。

时间复杂度为O(|V|)。

邻接表：

找出边同上，而要找入边的话就必须遍历所有的边才行！

时间复杂度：出边为O(1)~O(|V|)，而入边为O(|E|)。

3、`InsertVertex(G, x)`：

在图G中插入顶点x：

无向图和有向图都是如此：

直接在矩阵或邻接表末尾插入即可。

4、`DeleteVertex(G, x)`：

从图G中删除顶点x：

无向图：

邻接矩阵法：

在矩阵中将目标结点所在的行和列的所有元素值都改为0，再将用于存储结点的一维数组中的结点删去；

给结点结构体中添加一个bool类型的判空标识，这样删除结点时只需改动此标识即可。

只需修改矩阵中一行和一列的元素，时间复杂度为O(|V|)。

邻接表：

除了要删除结点和结点指向链表中所有数据，还要遍历整个链表找到所有相关的边进行删除。

时间复杂度O(|1|)~O(|E|)。
有向图：

邻接矩阵：同上。

邻接链表：

删除出边只需删除结点指向的链表即可，时间复杂度为O(1)~O(|V|)；

但删除入边就需要遍历找入边了，时间复杂度为O(|E|)。

5、`AddEdge(G, x, y)`：

若边(x,y)、<x,y>不存在，则向图G中添加该边。

无向图和有向图相同：

邻接矩阵：只需更改矩阵里的对应元素值为1即可，时间复杂度为O(1)。

邻接链表：在对应结点的对应链表中，采用尾插法或头插法都可，时间复杂度为O(1)~O(|V|)。

6、`FirstNeighbor(G,x)`：

求图G中顶点x的第一个邻接点，若有则返回顶点号，若x无邻接顶点或图中不存在x，则返回-1：

无向图

邻接矩阵：

只需扫描对应的行或列，遇到的第一个值为1的数据返回即可。

时间复杂度为O(1)~O(|V|)。

邻接链表：

只需扫描结点对应的链表，返回该链表中第一个元素即可。

时间复杂度为O(1)。
有向图：

邻接矩阵：

原理同上，找出边横向遍历，找入边纵向遍历。

时间复杂度为O(1)~O(|V|)。

邻接链表：

同样，找出边一步到位，找入边就得遍历了。

时间复杂度为O(1)~O(|E|)。

7、`NextNeighbor(G, x, y)`：

x为y的邻接点，找出x的除y之外的下一个邻接点，若有则返回顶点号，若无（y是x的最后一个邻接点）则返回-1：

算法在FirstNeighbor(G,x)的基础上，找到第y个，再往下扫描一个即可。

8、`Get_edge_value(G, x, y)`和`Set_edge_value(G, x, y, v)`：

获取和设置某条边的权值：

与Adjacent(G,x,y)雷同，在其基础上增加一条获取或修改权值的指令即可。

时间复杂度：O(1)~O(|V|)。

（四）图的遍历

1、广度优先遍历BFS

有向图和无向图都完美适配！

（1）算法逻辑

与树的广度优先遍历之间存在联系，而树的广度优先遍历即层序遍历。

图与树的不同即有回路，在树的层序遍历基础上解决这个回路问题即是图的广度优先遍历算法。

解决方式：给每个节点增加一个“访问标识”（如bool的0和1），用于记录在遍历过程中是否已访问过该结点。

算法思路：

1.找到与一个顶点相邻的所有顶点；
标记哪些顶点被访问过；
需要一个辅助队列。

FirstNeighbor(G,x): 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
NextNeighbor(G,x,y): 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

（2）代码实现

//广度优先遍历
void BFSTaverse(Graph G1){
    //一、生成并初始化“访问标记数组”（用于标记所有顶点是否已被访问）
	bool visited[MAX_VERTEX_NUM];
    for(int i=0; i<G.vexnum; ++i)
        visited[i] = false;
    //二、初始化辅助队列Q
    InitQueue(Q);
    //三、从0号顶点开始遍历
    for(int i=0; i<G.vexnum; ++i){
        //对每个连通分量调用一次BFS
        if(!visited[i])
            //v_i未访问过，从v_i开始BFS
            BFS(G, i);
    }
}

//对单个连通图的遍历算法
void BFS(Graph G1, int v){			//从顶点v出发遍历图G1
    //从第一个结点出发
    visit(v);						//访问初始顶点v
    visited(v) = true;				//对v做已访问标记
    Enqueue(Q, v);					//顶点v入队列Q
    //对其余结点的处理
    while(!isEmpty(Q)){				//若队列Q不为空则执行循环体，为空说明遍历结束
        Dequeue(Q, v);				//顶点v出队
        //w初始情况下等于v的第一个邻接顶点，若顶点存在其值不可能小于0，若顶点不存在则其值被赋为-1，结束循环：
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){	//循环找到所有邻接点，并在循环体内访问和入队
            if(!visited[w]){		//w为v的尚未访问的邻接顶点
                visit(w);			//访问顶点w
                visited[w] = true;	//对w做已访问标记
                Enqueue(Q, w);		//顶点w入队
            }
        }
    }
}

注：

FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号，若x无邻接顶点或图中不存在x，则返回-1。
NextNeighbor(G, x, y)：x为y的邻接点，找出x的除y之外的下一个邻接点，若有则返回顶点号，若无（y是x的最后一个邻接点）则返回-1。
若图采用邻接矩阵法存储，那么遍历序列是唯一的，如果采用邻接表法存储，那么遍历结果不唯一！

（3）性能分析

时间复杂度
- 邻接矩阵： $O (| V |^{2})$ 。
- 邻接链表： $O (| V | + | E |)$ 。
空间复杂度

（4）广度优先生成树与森林

图由广度优先遍历过程得到的序列，可生成“广度优先生成树”：

同理：

注：若用邻接矩阵存储图，则以上二者的生成结果是唯一的，若用邻接链表存储图，则以上二者的生成结果不唯一。

最后：

2、深度优先遍历DFS

（1）算法逻辑

树的深度优先遍历分为先根遍历和后根遍历，二图的深度优先遍历类似于树的先根遍历。

树的先根遍历：

（2）代码实现

//声明“访问标记数组”
bool visited[MAX_VERTEX_NUM];

//对图G进行深度优先遍历
void DFSTraverse(Graph G){
    //初始化“访问标记数组”
    for(v=0; v<G.vexnum; ++v)
        visited[v] = false;
    /*
    此处从v=0处调用DFS方法去遍历它在图G中所在的连通分量；
    完成后在整个图中寻找还未被访问的顶点，找到后再遍历它所在的连通分量，
    如此循环执行就可以完整无误地遍历完整个图：
    */
    for(v=0; v<G.vexnum; ++v){
        if(!visited[v])
            DFS(G, v);
    }
}

//从顶点v出发，深度优先遍历它所在的连通分量
void DFS(Graph G, int v){
    //访问目标定点v
    visit(v);
    //更改“访问标识”
    visited[v] = true;
    //依次遍历寻找“下一个”邻接顶点
    for(w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w)){
        //递归调用自己进行遍历
        if(!visited[w])
            DFS(G, w);
    }
}

（3）性能分析

空间复杂度：

来自函数调用栈，最坏情况为 $O (| V |)$ 。
时间复杂度：

邻接矩阵存储的图： $O (| V |^{2})$ ；

邻接链表存储的图： $O (| V | + | E |)$ 。

（4）深度优先生成树/森林

与广度优先生成树/森林原理一样。

3、图的遍历和图的连通性

对无向图进行BFS/DFS遍历：
- 调用BFS/DFS函数的次数=连通分量数。
- 对于连通图，只需调用1次 BFS/DFS。
对无向图进行BFS/DFS遍历：
- 对于普通有向图，调用BFS/DFS函数的次数不一定，视具体情况。
- 而对于强连通图，只需调用1次 BFS/DFS。

总结：

（五）图的应用

1、最小生成树

（1）概念

生成树：连通图的生成树是指包含图中所有顶点的一个连通子图。

顶点有 $n$ 个，则生成树的边有 $n - 1$ 条。
最小生成树：

边的权值之和最小的生成树。

（2）Prim算法

从某一个顶点开始构建生成树；
每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

时间复杂度为 $O (| V |^{2})$ 。
时间复杂度不依赖于 $| E |$ ，因此适合用于稠密图。

（3）KrusKal算法

每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)，直到所有结点都连通。

时间复杂度为 $O (| E | \log_{2} | E |)$ 。
适合于稀疏图。

2、最短路径

（1）单源最短路径——BFS算法

只适用于无权图，或各边权值都相同的图！

对BFS算法稍加改动即可：

新建一个二维数组，一行d[]记录结点到源结点的最短路径，另一行path[]记录其直接前驱；

visit一个结点时，修改其最短路径长度d[]并在path[]中记录其前驱结点。

//求图G中顶点u作为源顶点到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u){
    //初始化辅助数组
    for(int i=0; i<G.vexnum; i++){
        d[i] = ∞;				//路径长度
        path[i] = -1;			//前驱
        visited[i] = false;		//访问标记数组
    }
    
    //算法开始，源结点u自身路径长度为0
    d[u] = 0;
    //源结点u设为已被访问
    visited[u] = true;
    //源结点u入队
    EnQueue[Q,u];
    //核心代码
    while(!isEmpty(Q)){
        //u先出队
        DeQueue(Q,u);
        //找到u的“后继”
        for(w=FirstNeighbor(G,u); w<G.vexnum; w=NextNeighbor(G,u,w)){
            //如果该节点未被访问，那么“访问”该结点
            if(!visited[w]){
                //路径长度等于前驱的路径长度+1
                d[w] = d[u] + 1;
                //标记其前驱
                path[w] = u;
                //标记为已被访问
                visited(w) = true;
                //入队
                EnQueue(Q, w);
            }
        }//判断是否还有邻接结点，有则继续执行循环体，无则结束循环
    }
}

（2）单源最短路径——Dijkstra算法

迪杰斯特拉算法——无权图和有权图都适用！

带权路径长度：当图是带权图时，一条路径上所有边的权值之和成为该路径的带权路径长度。

需要三个数组：
- bool final[G.vexnum]：标记各顶点是否已找到最短路径，初始化将源结点所在位置设为true，其余为false；
- int dist[G.vexnum]：对应的最短路径长度，初始化将源结点所在位置设为0，与源结点直接相连的结点的值就是其路径权值，其余的设为∞；
- int path[G.vexnum]：路径上的前驱，初始化将源结点设为-1，邻接结点对应数值为源结点所在位置（此例中为0），其余可为-1。
运行过程（该例中以V₀为源结点）
1. 初始化数组；
2. 循环遍历final[]数组，找到所有标记为false的结点（意为还未找出与V₀之间最短路径的结点），在这些节点中找到dist[]值最小的顶点V_i（此处为V₄：dist[4]=5），令final[i]=true：
3. 检查所有邻接自V_i的顶点（V₀、V₁、V₂、V₃），若其final[]值为false（排除了V₀），则更新dist[]和path[]信息：
  
  检查V₁、V₂、V₃与V₄的路径权值各自加上V₀到V₄的路径权值（5）得到的值，是否比原来dist[]中存储的值要小。
  
  若是，则dist[]更改为此值，并把path[]的值改为4。
  
  若否，则不做处理。
4. 循环2、3步骤，直到final[]中所有数据都为true：
  
  循环遍历final[]数组，找到所有标记为false的结点，在这些节点中找到dist[]值最小的顶点V_i，令final[i]=true……
最终结果：

时间复杂度： $O (| V^{2} |$ )。

注：该算法不适用于有负权值的图！

（3）各顶点间的最短路径——Floyd算法

第一阶段：

//初始化矩阵A和path[]

//核心代码
for(int k=0; k<n; k++){								//以结点k为中转点
    for(int i=0; i<n; i++){							//两个for循环遍历整个数组A
        for(int j=0; j<n; j++){
            if(A[i][j] > A[i][k]+A[k][j]){			//判断当前的第k个结点为中转点时的路径是否比原来的路径短
                A[i][j] = A[i][k] + A[k][j];		//若是则应用此路径
                path[i][j] = k;						//同时更改存储路径信息的表path[][]
            }
        }
    }
}

评价：

时间复杂度为 $O (| V^{3} |)$ 。
可用于带有负权值的图。
但不能用于带有负权值回路的图！

（4）总结

	BFS算法	Djkstra算法	Floyd算法
无权图	✔	✔	✔
带权图	❌	✔	✔
带负权值的图	❌	❌	✔
带负权值回路的图	❌	❌	❌
时间复杂度	邻接矩阵$O(	V	^2) $、邻接链表$ O(
通常用于	求无权图的单源最短路径	①求带权图的单源最短路径、②所有顶点间的最短路径	求带权图中各顶点间的最短路径

3、有向无环图描述表达式

有向无环图：没有环路的有向图。DAG图。

用有向无环图表示算术表达式：

这太简单了没什么好说的。

4、拓扑排序

（1）AOV网

定点表示活动的有向无环图：

（2）拓扑排序

找到做事的先后顺序。

拓扑排序的实现：

从AOV网中选择一个没有前驱 (入度为0)的顶点并输出；
从网中删除该顶点和所有以它为起点的有向边。
重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

代码实现

#define MaxVertexNum 100			//图中顶点数目最大值
typedef struct ArcNode{				//边表结点
    int adjvex;						//该弧所指向的顶点的位置
    struct ArcNode *nextarc;		//指向下一条弧的指针
    //InfoType info;				//网的边权值
}ArcNode;
typedef struct VNode{				//顶点表结点
    VertexType data;				//顶点信息
    ArcNode *firstarc;				//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;				//邻接表
    int vex, arcnum;				//图的顶点数和弧数
}Graph;								//Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G){
    InitStack(S);					//初始化栈，存储入度为0的顶点
    for(int i=0; i<G.vexnum; i++)
        if(indegree[i]==0)
            Push(S, i);				//将所有入度为0的顶点进栈
    int count=0;					//计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){				//栈不空，则存在入度为0的顶点
        Pop(S, i);					//栈顶元素出栈
        print[count++]=i;			//输出顶点i
        for(p=G.vertices[i].firstarc; p; p=p->nextarc){
            //将所有i指向的顶点的入度减1，并且将入度为0的顶点压入栈S
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S, v);			//入度为0，则入栈
        }
    }
    if(count<G.vexnum)
        return false;				//拓扑排序失败，有向图中有回路	
    else
        return true;				//拓扑排序成功
}

时间复杂度：
- 邻接表储存：O(|V|+|E|)；
- 邻接矩阵存储：O(|V|²)。

（3）逆拓扑排序

与拓扑排序相反，每次删除的是出度为0的顶点。

（4）基于深度优先遍历算法实现逆拓扑排序

5、关键路径

（1）相关概念

AOE网：

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)。

性质：
1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。
3. 仅有一个入度为0的顶点，称为**开始顶点(源点)**，它表示整个工程的开始；
4. 也仅有一个出度为0的顶点，称为**结束顶点 (汇点)**，它表示整个工程的结束。
从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动；
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
**活动a_i的最早开始时间e_i**——指该活动弧的起点所表示的事件的最早发生时间。
**活动a_i的最迟开始时间l_i**——该活动的弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
**事件v_k的最迟发生时间vl(k)**——在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
**活动a_i的最迟开始时间l(i)**——该活动弧的终点所表示事件的最迟发生时间与该活动所需时间只差。
活动a_i的**时间余量：d_i=l_i-e_i**，表示在不增加工程总时间的情况下，活动a_i可以拖延的时间。
时间余量为0的活动就是关键活动，不可拖延。
由关键活动组成的路径就是关键路径。

（2）求关键路径的步骤：

求所有事件的最早发生时间 ve()；

按拓扑排序序列，依次求各顶点的ve(k)：

$v e (源点) = 0 v e (k) = M a x v e (j) + W e i g h t (v_{j}, v_{k}) ， v_{j} 为 v_{k} 的任意前驱$
求所有事件的最迟发生时间 vl()；

按逆拓扑排序序列，依次求各顶点的vl(k)：
- vl(汇点) = ve(汇点)；
- vl(k) = Min{vl(j) - Weight(v_k, v_j)}，v_j为v_k的任意后继。
求所有活动的最早发生时间e()；

若边<v_k, v_j>表示活动a_i，则有e(i) = ve(k)。
求所有活动的最迟发生时间I()；

若边<v_k, v_j>表示活动a_i，则有l(i) = vl(j) - Weight(v_k, v_j)。
求所有活动的时间余量d()。

时间余量d(i) = l(i) - e(i)。
由此，我们求出了所有关键活动，他们的路径就是这个图的关键路径：

关键活动：a₂、a₅、a₇；

关键路径：V1→V3→V4→V6。

（3）相关特性

若关键活动耗时增加，则整个工程的工期将增长；
缩短关键活动的时间，可以缩短整个工程的工期；
当缩短到一定程度时，关键活动可能会变成非关键活动。
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

🔑数据结构_第六章：图

🔑数据结构_第六章：图

第六章、图

（一）图的基本概念

1、定义：

2、无向图和有向图

3、简单图与多重图

4、顶点的度、入度、出度

5、顶点 - 顶点关系描述

6、连通图与强连通图

7、子图

8、连通分量和强连通分量

9、生成树与生成森林

10、边的权、带权图/网

11、几种特殊的图

（1）完全图

（2）稀疏图和稠密图

（3）树和森林

（二）图的存储与实现

1、邻接矩阵法

（1）普通图

（2）带权图

（3）性能分析

（4）邻接矩阵的特殊性质

2、邻接表法

3、十字链表、邻接多重表（工大不考）

（1）十字链表法

（2）邻接多重表法

（三）图的基本操作

1、Adjacent(G,x,y)：

2、Neighbors(G, x)：

3、InsertVertex(G, x)：

4、DeleteVertex(G, x)：

5、AddEdge(G, x, y)：

6、FirstNeighbor(G,x)：

7、NextNeighbor(G, x, y)：

8、Get_edge_value(G, x, y)和Set_edge_value(G, x, y, v)：

（四）图的遍历

1、广度优先遍历BFS

（1）算法逻辑

（2）代码实现

（3）性能分析

（4）广度优先生成树与森林

2、深度优先遍历DFS

（1）算法逻辑

（2）代码实现

（3）性能分析

（4）深度优先生成树/森林

3、图的遍历和图的连通性

（五）图的应用

1、最小生成树

（1）概念

（2）Prim算法

（3）KrusKal算法

2、最短路径

（1）单源最短路径——BFS算法

（2）单源最短路径——Dijkstra算法

（3）各顶点间的最短路径——Floyd算法

（4）总结

3、有向无环图描述表达式

4、拓扑排序

（1）AOV网

（2）拓扑排序

（3）逆拓扑排序

5、关键路径

（1）相关概念

（2）求关键路径的步骤：

（3）相关特性

1、`Adjacent(G,x,y)`：

2、`Neighbors(G, x)`：

3、`InsertVertex(G, x)`：

4、`DeleteVertex(G, x)`：

5、`AddEdge(G, x, y)`：

6、`FirstNeighbor(G,x)`：

7、`NextNeighbor(G, x, y)`：

8、`Get_edge_value(G, x, y)`和`Set_edge_value(G, x, y, v)`：