6-图的性质总结

简单图、多重图、子图

满足如下条件的就是简单图：

1. 不存在重复边
2. 不存在顶点到自己的表(自环)

多重图：

1. 若图中某两个顶点的边数大于1
2. 允许顶点通过一条边和自身关联

数据结构里面只讨论简单图 子图：

1. $G = (V,E)和G^{'}=(V^{'},E^{'})$
2. 其中$V^{'}是V的子集E^{'}是E的子集$
3. 如果顶点集相同，则是生成子图

简单路径、简单回路

1. 一个路径序列中不存在重复节点的是简单路径
2. 除第一个顶点和最后一个顶点外，其余节点不重复出现的是简单回路

无向图

这些术语跟有向图区分开来

连通	连通图	连通分量	完全图	度
两个顶点可达	图任意两点连通	极大连通子图就是连通分量，要求包含所有边	边数为：n(n-1)/2	度数之和等于边的两倍：Sumn = 2e

有向图

强连通图	强连通分量	完全图	度
v到w和w到v都有路径	极大强连通子图就是强连通分量	边数为：n(n-1)	出度=入度=e

两种存储结构：矩阵和链表

邻接矩阵

邻接矩阵是采用二维数组的存储方式来存储图，为v行v列的矩阵，其中若$v_i到v_j有路径，则A[i][j]为1，或者是对应的路径权值$。 $\begin{aligned} &当(v_i,v_j)是G的边，则a[i][j] = 1 \\ &否则a[i][j] = 0或无穷 \\ \end{aligned}$ 值可以是权值，有向图和无向图有着一定的区别（无向图对称，可以压缩的），能理解其表达的意思就OK。 随便写个矩阵： $\begin{bmatrix} 0 & 1 & 1& 0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &1 \\ 1 & 0 & 0 &0 \\ \end{bmatrix}$ 其中当图是无向图的时候，矩阵是对称的。有向图则不一定，有向图中，行代表顶点的出，列代表顶点的入，比如上述矩阵，顶点$v_1$有指向$v_2和v_3$的两条边，而又有$v_4指向v_1$的一条边。

typedef struct{
	char vex[N];	
    int weight[N][N];	//N*N邻接矩阵，每条边的权值用int变量表示
	int vexnum,arcnum; 	//图的当前顶点数和弧数
}MGraph;

空间复杂度：显而易见空间复杂度跟顶点个数有关，为$O(n^2)$ 对于$A^n$的元素$A^n[i][j]$表示的是由顶点i到j长度为n的路径有多少条。该结论了解即可 邻接矩阵适用于存储相对稠密的图。

邻接表

看下图理解： 设计顶点表结点和边表结点来存储。顶点表节点由顶点域和指向第一条邻接边的指针构成，包含(顶点域data，边表头指针first)。边表结点中包含指向下一跳邻接边的指针。

typedef struct ArcNode{			//边表
	int vexIndex;				
    int weight;                
	struct ArcNode *next;		//指向下一个边表结点
}ArcNode; 

typedef struct VNode{	//顶点表
	char data; 			
	ArcNode *first; 	//指向第一条依附该顶点的弧的指针
}VNode;

typedef struct{
	VNode vex[N];    		
	int vexnum,arcnum; 		//图的顶点数和边数
} ALGraph; 					//ALGraph是以邻接表存储的图类型

空间复杂度：空间复杂度跟顶点个数和边数有关，若为有向图则$O(|V|+|E|)$若为无向图则$O(|V|+2|E|)$。

BFS和DFS

BFS

1）树的广搜 广度优先搜索遍历是在各种算法中广泛应用的一种优先遍历算法。就是往宽了去搜索，再搜索下一层。

1. 若树非空，根节点入队
2. 若队列非空，队头元素出队并且访问，同时将其孩子入队
3. 重复2直到队列为空为止

树的BFS借助了队列的帮助，与此同时因为树中不存在回路，搜索到相邻节点的时候不可能搜索到已经访问到的节点。 2）图的广搜 在图中，广度优先搜索会面临一个问题就是图若存在回路，会重复访问到已经访问过的结点，从而带来不必要的时间开销，此处需要设计一个辅助数组来标记是否被访问过，其余的思想与树的层次遍历思想大致相同，从一个节点开始，访问其邻接点，依次进行。具体思想如下：

1. 从起始节点开始找到与顶点相邻的所有顶点(过程会有入队和出队操作)
2. 辅助数组标记
3. 循环递归
4. 需要借助辅助队列

bool visited[MAX_SIZE];
void BFSTraverse(Graph G){
	for(i = 0;i<G.vexnuml;i++)
		visited[i] = fasle;
	InitQueue(Q);
	for(i = 0;i<G.vexnum;i++){
		if(!visited[i])
			BFS(G,i);
	}
}

void BFS(Graph G){
	visit(v);
	visited[v] =true;
	EnQueue(Q,v);
	while(!isEmpty(Q)){
		DeQueue(Q,v);
		for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v)){
			if(!visited[w]){
				visit(w);
				visited[w] = true;
				EnQueue(Q,v);
			}
		}
	}
}

时间复杂度分析：时间复杂度取决于具体数据结构的搜索方式，也就是跟存储方式有关：邻接表和邻接矩阵。若采用邻接表，每个顶点都搜索一次，需要$O(|V|)$次，搜索邻接边需要$O(|E|)$，故为$O(|V|+|E)$。当采用邻接矩阵的时候，每个顶点都需要访问一次，算上边的访问，一共需要$O(|V|^2)$。

空间复杂度分析：空间开销来源于辅助队列，故空间开销为$O(|V|)$。

DFS

图的DFS就类似于树的先序遍历，理解就是往深了走，顺着一个节点往下一直搜索，直到没有就回溯，持续回溯，直到回溯到一个又可以重新向下搜索的节点。跟BFS一样同样需要一个标记数组来标记节点是否被访问过。如下是伪代码：

bool visited[MAX_SIZE];
void DESTralverse(Graph G){
	for(v = 0;v<G.vexnum;++v)
		visited[v] = false;
	for(v = 0;v<G.vexnum;++v)
		if(!visited[w])
			DFS(G,v);
}

void DFS(Graph G,int v){
	visit(v);
	visited[v] = true;
	for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v))
		if(!visited[w])
			DFS(G,v);
}

时间复杂度分析：时间复杂度取决于具体数据结构的搜索方式，也就是跟存储方式有关：邻接表和邻接矩阵。若采用邻接表，每个顶点都搜索一次，需要$O(|V|)$次，搜索邻接边需要$O(|E|)$，故为$O(|V|+|E)$。当采用邻接矩阵的时候，每个顶点都需要访问一次，算上边的访问，一共需要$O(|V|^2)$。

空间复杂度分析：DFS算法是递归算法，需要借助一个递归空间栈，在最优情况下，空间复杂度可以为$O(1)$，平均的为$O(|V|)$。

生成树

包含所有顶点的极小连通子图子图，其中结点数为n，边数为n-1，少一条边非连通，多一条边有回路。其具有性质：

1. 不一定唯一
2. 不唯一但是权值之和唯一(存在权值相同的边时会存在不唯一)
3. $|E| = |V| -1$

最小生成树的两种算法：“普利姆(Prim)和克鲁斯卡尔(Kruskal)”

普利姆(Prim)

这个算法是选点的算法，一开始选择一个顶点加入集合$S$，此时树中只有一个顶点，然后从剩余顶点集合$T$中选取相距树中顶点集合最近的点，并且将该边加入集合$S$中，过程要记得避开回路，也是离散数学中的避圈法。每次都会加入一个点和一条边，$n-1$次后得到最小生成树。

克鲁斯卡尔(Kruskal)

Prim是选点，而Kruskal就是选边的算法，直接给边按权排序，按从小到大选取，过程需要避开回路，也是避圈法的一种，该算法的思想本质是贪心，有条件的贪心。一直添加$n-1$次即可。

最短路径问题(迪杰斯特拉算法)

耳熟能详的算法了，大致了解算法思路，用个人理解简述：

1. 两个集合$S$和$V$分别用来记录已选结点和剩余结点
2. 选定初始结点$v_0$加入$S$，计算出$v_0$到各可达结点的距离
3. 选出距离最短的结点$v_s$加入$S$
4. 因为加入了$v_s$，所以要适当的更新到剩余结点的距离(比如说原来A到D距离是10，但是加入了B后，通过A->B->D的距离是5，距离更短，所以要更新)
5. 跳转到3，执行$n-1$次即可计算出到每个节点的最短距离(可能存在不可达)

本质是贪心，时间复杂度两种数据结构都是$O(|V|^2)$ 看个例子就明白了：

顶点（这一列不包含起点）	第 1 轮	第 2 轮	第 3 轮	第 4 轮	第 5 轮	第 6 轮	第 7 轮
0	∞	∞	∞	∞	∞	∞	∞
2	4
1→2	已完成	已完成	已完成	已完成	已完成	已完成
3	∞	∞	7
1→5→3	7
1→5→3	已完成	已完成	已完成
4	∞	13
1→2→4	13
1→2→4	13
1→2→4	13
1→2→4	已完成	已完成
5	5
1→5	5
1→5	已完成	已完成	已完成	已完成	已完成
6	5
1→6	5
1→6	5
1→6	已完成	已完成	已完成	已完成
7	∞	∞	∞	∞	∞	14
1→2→4→7	已完成
集合S	{1, 2}	{1,2,5}	{1,2,5,6}	{1,2,5,6,3}	{1,2,5,6,3,4}	{1,2,5,6,3,4,7}	{1,2,5,6,3,4,7,0}

拓扑

AOV

顶点$V$表示事件，$<V_i,V_j>$的这样一条边表示活动$V_j$必须要$V_i$在它之前执行。这两个节点互为前驱后继。

拓扑排序

一个有向无环图的顶点序列满足以下条件：

1. 每个顶点只出现一次
2. 如果A在B前面，则图中不存在B到A的路径

实现步骤：

1. AOV网中选择一个没有前驱的节点(入度为0)
2. 删除该节点和所有以他为起点的有向边
3. 重复1和2，知道网为空或者网中不存在无前驱的顶点位置（此时必有环）

性质：

1. 一个顶点有多个直接后继的话，则可能导致拓扑序列不是唯一的，如果图内的唯一前驱和后继的话，序列唯一
2. 可以对AOV网进行拓扑排序后重新编号，使得新的图用邻接矩阵存储，此时是三角阵，是可以压缩成上（下）三角的(原理？暂不懂)。由此得到一个充分性结论：邻接矩阵是三角阵则存在拓扑排序。

这里用个例子来看一下： 将这个有向无环图进行压缩存储。 有向无环图，一定可以转化为一个上三角或下三角矩阵。但是需要调整顶点的编号。 如果要用上三角矩阵表示有向无环图的邻接矩阵，可以对图进行拓扑排序，按照拓扑排序序列，重新调整各个顶点的编号。这样可以确保，所有的弧都是从小编号顶点指向大编号顶点，从而也就保证了邻接矩阵可以转化为“上三角矩阵”

关键路径

恶心，算四个表，小心计算

1）事件$v_k$的最早发生时间$ve(k)$

1. $ve(0)$为0
2. $ve(k) = Max[ve(j) + weight(v_j,v_k)]$其中k是j的后继
3. 从头开始顺着算，计算一个事件的最早发生时间就是，找到它的所有前驱，计算其前驱的最早发生时间加上其代价(边权)，存在多个前驱取最大的。

2）事件$v_k$的最迟发生时间$vl(k)$

1. 终点等于$ve(0)$
2. $vl(k) = Min[vl(j) - weight(v_k,v_j)]$
3. 从最后开始逆过来算，计算一个事件的最迟发生时间，找到它的所有后继，计算该后继减去代价到该活动点的值，可能有多个后继，取差值最小的。

3）活动$a_i$的最早开始事件$e(i)$

1. 等于该活动起始点(某事件)的最早发生时间
2. 找边，找起始点，找$ve(i)$

4）活动$a_i$的最迟开始事件$l(i)$

1. $<v_k,v_j>$表示活动$a_i$，则$l(i)=vl(i)-weight(v_k,v_j)$
2. 找到边，对应的终点，查该事件点的$vl(k)$，减去该活动的代价得到$l(i)$