图 知识点总结（王道）

图的定义

图G由顶点集V和边集E组成，记为G=（V,E），其中V（G）表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V={v1，v2vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(U,V)|u∈V，v∈V}，用|E|表示图中边的条数。

注意：线性表可以是空表，树可以是空树，但是图不可以是空图，即V一定是非空集

无向图、有向图

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序树，记为（v，w）或（w，v），因为（v，w）=（w，v），其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边（v，w）依附于v和w两个顶点，或者说边（v，w）和顶点v、w相关联。

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为，其中v和w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。≠

顶点的度、入度、出度

对于无向图：顶点的度是指依附于该顶点的边的条数，记为TD（v）。

对于有向图：
入度是以顶点v为终点的有向边的数目，记为ID（v）
出度是以顶点v为起点的有向边的数目，记为OD（v）
顶点v的度等于其入度和出度之和，即TD（v)=ID(v)+OD(v)

顶点-顶点的关系描述

路径：顶点到顶点之间的一条路径是指顶点序列
回路：第一个顶点和最后一个顶点相同的路径称为回路或者环
简单路径：在路径序列中，定点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度：路径上边的数目
点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为u到v的距离。若不存在路径，则记距离为正无穷。
无向图： 无向图中若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图：有向图中若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是连通的
连通图：若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
强连通图:若图中任意一对顶点都是强连通的，则称此图为强连通图。

常见考点
对于n个顶点的无向图G，若G是连通图，则最少有n-1条边
若G是非连通图，则最多有
条边

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

子图

设有两个图G=（V,E）和G=（A,B),若A是V的子集，B是E的子集，就称G`是G的子图。
若有 满足V(G’)=v(G)的子图G’，则称其为G的生成子图

连通分量

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

强连通分量

有向图中的极大强连通子图省委有向图的强连通分量

生成树

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

若图中顶点数为n，则他的生成树含有n-1条边。对于生成树而言，若砍去他的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

生成森林

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

边的权、带权图/网

边的权：在一个图中，每条边都可以标上具有某种含义的数值，这个数值被称为该边的权值。
带权图/网：边上带有权值的图称为带权图，也叫做网
带权路径长度：当图是带权图时，一条路径上所有边的权值之和称为该路径的带权路径长度。

几种特殊形态的图

无向完全图:无向图中任意两个顶点之间都存在边
有向完全图：有向图中任意两个顶点之间都存在方向相反的两个弧
稀疏图：边数很少的图称为稀疏图
稠密图：边数很多的图称为稠密图
树：不存在回路，且连通的无向图
n个顶点的树，必有n-1条边
常见考点：n个顶点的图，若|E|>n-1,则一定有回路
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树

常见考点

对于n个顶点的无向图G，
①所有顶点的度之和=2|E|
②若G是连通图，则最少有n-1条边（树），若|E|>n-1,则一定有回路
③若G是非连通图，则最多可能有
条边
④无向连通图共有
条边

对于n个顶点的有向图G：
①所有顶点的出度之和=入度之和=|E|
②所有顶点的度之和=2|E|
③若G是连通图，则最少有n条边（形成回路）
④有向完全图共有
条边

图的存储

邻接矩阵法

#define MaxVertexNum 100//顶点数目的最大值

typedef struct{
	char Vex[MaxVertexNum];//顶点表
	int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
	int vexnum,arcnum;//图的当前顶点数和边数/弧数
}MGraph;

1
2
3
4
5
6
7
8

无向图：
第i个结点的度=第i行（或第i列）的非零元素的个数

有向图：
第i个结点的出度=第i行的非零元素的个数
第i个结点的入读=第i列的非零元素的个数
第i个结点的度=第i行、第i列的非零元素个数之和。

邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|v|)

邻接矩阵存储带权图（网）

#define MaxVertexNum 100//顶点数目的最大值
#define INFINITY 最大的int值 //宏定义常量“无穷”
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum];//顶点
	EdgeType Edge[MaxVertexNum][MaxVertexNum];//边的权
	int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;
1
2
3
4
5
6
7
8
9

性能分析：
空间复杂度O(|V|^2) ——只和顶点数相关，和实际的边数无关
适合用于存储稠密图
性质：
设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素等于由顶点i到顶点j的长度为n的路径的数目

邻接表法（顺序+链式存储）

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

//顶点
typedef struct VNode{
	VertexType data;//顶点西悉尼
	ArcNode *first;//第一条边/弧
}VNode,AdjList[MaxVertexNum];
1
2
3
4
5
6
7
8
9
10
11
12

对比孩子表示法：顺序存储各个节点，每个节点中保存孩子链表头指针。

邻接表法存储图
无向图：边结点的数量是2|E|，整体空间复杂度为O(|V|+2|E|)；
有向图：边结点的数量是|E|，整体空间复杂度为O(|V|+|E|)；

图的邻接表表示方式并不唯一，只要确定了顶点的编号，图的邻接矩阵表示方法唯一。

十字链表、邻接多重表

图的基本操作

①Adjacent(G,x,y)：判断图G是否存在边或者（x，y）
②Neighbors(G,x):列出图G中与结点x邻接的边
③InsertVertex(G,x):在图G中插入顶点x
④DeleteVertex(G,x)：从图G中删除顶点x
⑤AddEdge(G,x,y)：若无向边（x，y）或有向边不存在，则向图G中添加边
⑥FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点，或图中不存在x，则返回-1
⑦NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个不邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

此外，还有图的遍历算法，包括深度优先遍历和广度优先遍历

图的广度优先遍历BFS

广度优先遍历要点（BFS)：
1.找到一个与顶点相邻的所有顶点
2.标记哪些顶点被访问过
3.需要一个辅助队列

bool visited[MAX_VERTEX_NUM];//访问标记数组
void BFSTraverse(Graph G){
	//对图G进行广度优先遍历
	for(i=0;i<G.vexnum;++i)
		visited[i]=FALSE;//访问标记数组初始化
	InitQueue(Q);//初始化辅助队列Q
	for(i=0;i<G->vexnum;++i){
		//从0号顶点开始遍历
		if(!visited[i])//对每个连通分量调用一次BFS
			BFS(G,i);//vi未访问过，从vi开始BFS 
	} 
} 
//广度优先遍历
void BFS(Graph G,int v){
	//从顶点v出发，广度优先遍历图G
	visit(v);//访问初始顶点v 
	visited[v]=TRUE;//对v做已访问标记
	ENqueue(Q,v);//顶点v入队列Q
	while(!isEmpty(Q)){
		DeQueue(Q,v);//顶点v出队列
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		//检测v的所有邻接点
		if(!visited[w]){
			//w为v的尚未访问的邻接顶点
			visit(w);//访问顶点w
			visited[w]=TRUE;//对w做已访问标记
			EnQueue(Q,w);//顶点w入队列 
		} 
	} 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

结论：
对于无向图，调用BFS的次数=连通分量数

复杂度分析：
邻接矩阵存储的图 O(|V|^2)
邻接表存储的图 O(|v|+|E|)

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方法不唯一，因此基于邻接表的广度优先生成树也不唯一。
对于非连通图的广度优先遍历，可以得到广度优先生成森论。

图的深度优先遍历DFS

bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){
	//对图G进行深度优先遍历
	for(v=0;v<G->vexnum;++v)
		visited[v]==FALSE;//初始化已访问标记数组
	for(v=0;v<G->vexnum;++v)//本代码中是从v=0开始遍历 
		if(!visited[v])
			DFS(G,v); 
} 

void DFS(Graph G,int v){
	//从顶点v出发，深度优先遍历图G
	visie(v);//访问顶点v
	visited[v]=TRUE;//设已访问标记
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w]){
			//w为u的尚未访问的邻接顶点
			DFS(G,w); 
		}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析：
时间复杂度=访问各个结点所需要的时间+探索各边所需要的时间
邻接矩阵存储的图：
访问|V|个顶点需要O(|v|)的时间
查找每个顶点的邻接点都需要O(|v|)的时间，而总共有|V|个顶点，时间复杂度为O(|V^2|)

邻接表存储的图：
访问|v|个顶点所需要O(|v|)的时间，查找各个顶点的邻接点共需要O(|E|)的时间。时间复杂度为O(|v|+|E|)

深度优先生成树：同一个图的邻接矩阵的表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一，同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一。

对无向图进行BFS/DFS遍历
调用BFS/DFS函数的次数=连通分量数
对于连通图，只需要调用1次BFS/DFS

对有向图进行BFS/DFS遍历
调用BFS/DFS函数的次数要具体问题具体分析
若起始顶点到其他各顶点都有路径，那么只需要调用一次

对于强连通图，从任一顶点出发都只需要调用1次BFS/DFS函数

最小生成树

对于一个带权连通无向图G=(V.E),生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则称T为G的最小生成树

最小生成树可能有多个，但边的权值之和总是唯一且最小的
最小生成树的边数=顶点数-1 砍掉一条则不连通，增加一条则出现回路

如果一个连通图本身就是一棵树，则其最小生成树是他本身
只有连通图才有生成树，非连通图只有生成森林

Prim算法：适合边稠密图
（普里姆）从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树吗，直到所有顶点都纳入为止。

Kruskal算法（克鲁斯卡尔）：适合边稀疏图
每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）
直到所有结点都连通

Prim算法的实现：
从v0开始，总共需要n-1轮处理。
每一轮处理：循环遍历所有个结点，找到lowCast最低的，且还没加入树的顶点。
再次循环遍历，更新还没加入的各个顶点的lowCast值

Kruskal算法的实现：
初始：将各条边按权值排序
共执行e轮，每轮判断两个顶点是否属于同一集合

最短路径

BFS算法

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
	//d[i]表示从u到i结点的最短路径
	for(i=0;i<G.vexnuml;++i){
		d[i]=∞；//初始化路径长度
		path[i]=-1;//最短路径从哪个顶点过来 
	} 
	d[u]=0;
	visited[u]=TRUE;
	EnQueue(Q,u);
	while(!isEmpty(Q)){
		//BFS算法主过程 
		DeQueue(Q,u);//队头元素u出队
		for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
			if(!visited[w]){
				//w为u的尚未访问的邻接顶点
				d[w]=d[u]+1;//路径长度加1
				path[w]=u;//最短路径应从u到w
				visited[w]=TRUE;//设已访问标记
				EnQueue(Q,w);//顶点w入队 
			} 
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BFS算法的局限性：
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图
Dijkstra算法
不适用于有负权值的带权图

#include
using namespace std;
const int N=510;
int dist[N],g[N][N],n,m;
bool st[N];
int dijkstra()
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=0;i<n-1;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
				t=j;
		st[t]=true;
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],dist[t]+g[t][j]);
	}
	if(dist[n]==0x3f3f3f3f)	return -1;
	return dist[n];
}
int main()
{
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
	}
	cout<<dijkstra();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Floyd算法

求出每一对顶点之间的最短路径。
使用动态规划思想，将问题的求解分为多个阶段。

//核心代码
//...准备工作，根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){//考虑以vk作为中转点
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){//遍历整个矩阵，i为行号，j为列号
			if(A[i][j]>A[i][k]+A[k][j])//以vk为中转点的路径更短
				A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
				path[i][j]=k;//中转点
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

有向无环图

有向无环图：
若一个有向图中不存在环，则称为有向无环图，简称DAG图。
解题方法：
step1:把各个操作数不重复地排成一排
step2:标出各个运算符的生效顺序（先后顺序有点出入无所谓）
step3:按顺序加入运算符，注意“分层”
step4:从底向上逐层检查同层的运算符是否可以合体

AOV网：
用顶点表示活动的网
用DAG图表示一个工程。顶点表示活动，有向边表示活动vi必须先于vj进行。

拓扑排序：
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
①每个顶点出现且只出现一次
②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。
若图中有环，则不存在拓扑排序序列/逆拓扑排序序列
拓扑排序的实现：
①从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或者当前网中不存在无前驱的顶点为止。

bool TopoLogicalSort(Graph G){
	InitStack(S);
	for(int i=0;i<G.vexnum;i++)
		if(indegree[i]==0)	Push(S,i);
	int count=0;
	while(!isEmpty(S)){
		Pop(S,i);
		print[count++]=i;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			v=p->adjvex;
			if(!(--indegree[v]))	Push(S,v);
		}
	}
	if(count<G.vexnum)	return false;
	else	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

AOE网：
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动所需要的时间），称之为用边表示活动的网络，简称AOE网。

AOE网具有以下两个性质：
①只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才发生。另外，有些活动是可以并行进行的。

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

求关键路径的步骤
①求所有事件的最早发生时间ve（）
②求所有事件的最迟发生时间vl（）
③求所有活动的最早发生时间e（）
④求所有活动的最迟发生时间l（）
⑤求所有活动的时间余量d（）
d（i）=0的活动就是关键活动

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