数据结构——图的应用（仅于考试）

1、概念

• 图：由顶点集V和边集E组成，图不可以是空图，不能一个顶点都没有，边集可以为空
• 有向图：E是有向边（弧）的集合时，弧是顶点的有序对
• 无向图：E是无向边的有限集合，G是无向图
• 简单图：不存在重复边，不存在顶点到自身的边
• 完全图：有n(n-1)/2条边的无向图【完全图中任意两个顶点之间都存在边】，有n(n-1)条弧的有向图
• 连通图：图中任意两个顶点都是相通的，无向图中的极大连通子图就是连通分量
• 强连通图：图中任意一对顶点v和w，从v到w和从w到v之间都有路径。有向图的极大强连通子图称为有向图的强连通分量
• 生成树：连通图的生成树包含图中所有顶点的一个极小连通子图，
• 生成森林:在非连通图中，连通分量的生成树构成了非连通图的生成森林
• 无向图的度：n个顶点，e条边，全部顶点度的和等于边数的2倍，d=2e
• 有向图的度：n个顶点，e条边，全部顶点的入度=出度=e

2、存储

（1）邻接矩阵法

邻接矩阵存储是用一个一维数组存储图中顶点的信息，用二维数组存储边的信息（各顶点之间的邻接关系）,空间复杂度是o(n^2)

#define MaxVerterNum 100 //数组的长度

typedef char VertexType;
typedef int EdgeType;

typedef struct{

    VertexType Vex[MaxVerterNum];
    EdgeType Edge[MaxVerterNum];
    int vexnum,arcnum;

}graph;

（2）邻接表

邻接表是对图中每个顶点建立一条单链表，第i个单链表中的节点表示依附于顶点Vi的边，即边表，边表的头指针的顶点信息用顺序存储（顶点表）来表示，无向图的存储空间是o(|V|+2|E|),有向图的存储空间是o(|V|+|E|)，邻接表不唯一

#define MaxVertexNum 100

//边表
typedef struct ArcNode{
    
    int adjvex;
    struct ArcNode * next;
}arcnode;
//顶点表节点
typedef struct VNode{
    
    VertexType data;
    ArcNode * first;
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;
    int vexnum,arcnum
}ALgraph;

3、遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。方法是广度优先搜索和深度优先搜索。

（1）广度优先搜索【树的层次遍历】

BFS需要借助一个辅助队列进行搜索，邻接表的时间复杂度是o(|v|+|e|)，邻接矩阵的时间复杂度是o(|v|^2)

（2）深度优先搜索【树的先序遍历】

DFS需要借助一个递归工作栈，邻接表的时间复杂度是o(|v|+|e|)，邻接矩阵的时间复杂度是o(|v|^2)

4、应用

（1）最小生成树

一个连通图的生成树包含图的所有顶点，并且只含尽可能最少的边。对于带权连通无向图，可能存在多棵生成树，权值之和最小的生成树为最小生成树。

性质：

• 最小生成树不唯一，当权值互不相等时，最小生成树唯一
• 最小生成树的边数为顶点数-1

常见的最小生成树方法：Prim（普里姆算法）和Kruskal（克鲁斯卡尔）

Prim思路：任取一个顶点，选择与该顶点的集合中最近的点为下一个点，知道所有的顶点都遍历了，适合求解边稠密的图

Kruskal思路：按照边的权值由小到大的顺序进行，直到所有的顶点都在一个连通分量上

（2）最短路径

带权路径长度最短的那条路径称为最短路径，最短路径可以分为两种：单源最短路径，求解图中某一顶点到其他各顶点的最短路径，通过Dijkstra（迪杰斯特拉）求解；每对顶点间的最短路径，可以通过Floyd（弗洛伊德）求解。

Dijkstra不适合边上带有负权值

Floyd不适合边带负权值且组成回路的

（3）拓扑排序和逆拓扑排序

拓扑排序满足以下条件：

1）每个顶点出现且只出现一次

2）若顶点A在序列中排在B前面，则在图中不存在从顶点B到A的路径。

步骤：

1）从AOV网中选择一个没有前驱的顶点并输出

2）从网中删除该顶点和所有以它为起点的有向边

3）重复前边两个步骤，直到网为空或网中不存在无前驱的顶点为止，若网不为空，则说明AOV中存在环。

逆拓扑排序步骤：

1）从AOV网中选择一个没有后续的顶点并输出

2）从网中删除该顶点和所有以它为终点的有向边

3）重复前边两个步骤，直到网为空

例：

 拓扑排序：V1->V2->V3->V4->V5->V6

逆拓扑排序：V6->V5->V4->V3->V2->V1

（4）关键路径

AOE网是以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销。AOE网的性质：

• 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
• 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生

从源点到汇点的所有路径中，最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，关键活动会影响整个工程的时间。

• 事件vk的最早发生时间Ve：V1到Vk的最长路径长度【拓扑排序:v1->v2->v3->v4->v5->v6】,多路选最大值
• 事件vk的最迟发生时间Vl：保证Vk的后续事件Vj在其最迟发生时间Vl能够发生时，该事最迟必须发生的时间【逆拓扑排序,V6->v5->v4->v3->v2->v1】，多路选最小值
• 活动ai的最早开始时间e(i)：活动弧的起点所表示的事件的最早发生时间【弧尾顶点最早开始时间】
• 活动ai的最迟开始时间l(i)：活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差。【弧尾顶点最迟开始时间-权重】

例：

跟事件相关：

跟活动相关：

关键路径是d(i) = l(i)-e(i)=0的关键活动的路径，a2对应V1-V3,a5对应V3-V4，a7对应V4-V6，{V1,V3,V4,V6}。

5、常用公式

• n个顶点，n条边的无向图，是有环的，n个顶点，n-1条边的无向图是连通的
• 从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，该图是连通图
• 一个28条边的非连通无向图至少有（8+1）个顶点，完全图【n(n-1)/2=28】+一个顶点就是非连通无向图
• n个顶点，连通无向图，边的个数是n-1，强连通有向图，边的个数是n，形成回路
• n个顶点和e条边的无向图的邻接矩阵中零元素的个数为n^2-2e，非零元素是2e
• n个顶点和k条边的有向图的邻接表中，删除与图中某个顶点相关的所有边的时间复杂度是o（n+k）

6、例题

6.1、

有100个顶点，200条边的有向图采用邻接矩阵存储（小于15%，算稀疏矩阵），该邻接矩阵是否是稀疏矩阵？为什么？

是系数矩阵，因为连接矩阵是100×100=10000，只有200个非零元素，非零元素只占总元素总个数的2%。按照题目假设，该邻接矩阵时稀疏矩阵