第6章-图

目录

图的存储及基本操作

邻接矩阵法

邻接表法

图的基本操作

图的遍历

广度优先搜索

BFS算法求解单源最短路径问题

深度优先搜索

最小生成树

prim算法

Kruskal算法

最短路径

Dijkstra算法求单源最短路径问题

Floyed算法求各顶点之间最短路径问题

有向无环图描述表达式

拓扑排序

关键路径

基本概念

求关键路径算法步骤

关键路径例题

图的存储及基本操作

邻接矩阵法

#define MaxVertexNum 100//顶点数目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum];//顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
	int vexnum,arcnum;//图的当前顶点数和弧数 
}MGraph; 

邻接表法

#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点 
	int adjvex;//该弧所指向的顶点的位置
	struct ArcNode *next;//指向下一条弧的指针
	//InfoType info;//网的边权值 
}ArcNode;

typedef struct VNode{//顶点表结点 
	VertexType data;//顶点信息 
	ArcNode *first;//指向第一条依附该顶点的弧的指针 
}VNode,AdjList[MaxVertexNum]; 

typedef struct{
	AdjList vertices;//邻接表
	int vexnum,arcnum;//图的顶点数个弧数 
}ALGraph;//ALGraph是以邻接表存储的图类型 

图的基本操作

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中添加该边 
RemoveEdge(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 
Get_edge_value(G,x,y);//获取图G中边(x,y)或对应的权值 
Set_edge_value(G,x,y,v);//设置图G中边(x,y)或对应的权值为v 

图的遍历

广度优先搜索

bool visited[MAX_VERTEX_NUM];//访问标记数组
void BFSTraverse(Graph G){//对图G进行广度优先遍历
	for(i=0;i=0;w=NextNeighbor(G,v,w))//检测v所有邻接点
			if(!visited[w]){//w为v的尚未访问的邻接顶点
				visit(w);//访问顶点w
				visited[w]=true;//对w做已访问标记
				EnQueue(G,w);//顶点w入队列 
			} 
	} 
} 

BFS算法求解单源最短路径问题

#define inf 0x4f4f4f
void BFS_MIN_Distance(Graph G,int u){
	//d[i]表示从u到i结点的最短路径
	for(i=0;i=0;w=NextNeighbor(G,u,w))
			if(!visited[w]){//w为u的尚未访问的邻接顶点
				visited[w]=true;//对w做已访问标记	
				d[w]=d[u]+1;//路径长度加1 
				EnQueue(G,w);//顶点w入队列 
			} 
	} 
}

深度优先搜索

bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){//对图G进行深度优先遍历
	for(v=0;v=0;w=NextNeighbor(G,v,w))//检测v所有邻接点
		if(!visited[w]){//w为v的尚未访问的邻接顶点
			DFS(G,w); 
		} 
	} 
} 

最小生成树

通用的最小生成树算法：

GENERIC_MST(G){
	T=NULL;
	while T未形成一棵生成树
		do 找到一条最小代价边(u,v)并且加入T后不会产生回路
			T=T∪(u,v); 
}

prim算法

思想：初始时从图中任取一顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T， 每次操作后T中的顶点数和边数都增加1，以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。

 void Prim(G,T){
	T=空集;//初始化空树
	U={w};//添加任一顶点w 
	while((Y-U)!=空集){//若树中不含全部顶点 
		设(u,v)是使  u属于U 与 v属于(V-U) ，且权值最小的边
		T=T∪{(u,v)};//边归入树 
		U=U∪{v};//顶点归入树 
	} 
}

时间复杂度,不依赖 E，适用于求解边稠密的图的最小生成树。

Kruskal算法

 

思想：是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

初始时为只有n个顶点而无边的非连通图T={ V,{ } },每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边，以此类推，直至T中所有顶点都在一个连通分量上。

void Kruskal(V,T){
	T=V;//初始化树T，仅含顶点
	numS=n;//连通分量数
	while(numS>1){	//若连通分量数大于1
		从E中取出权值最小的边(v,u); 
		if(v和u属于T中不同的连通分量){
			T=T∪{(v,u)};//将此边加入生成树中 
			numS--;//连通分量数减1 
		}
	} 
} 

用堆来存放边的集合，每次选择最小权值边需,采用并查集添加新边，构造T的时间复杂度是。因此适用于边稀疏而顶点较多的图。

最短路径

Dijkstra算法求单源最短路径问题

单源最短路径：图中某一顶点到其他各个顶点的最短路径。

1 初始化：集合S初始为{0}，dist[ ]的初始值dist[ i ]=arcs[0][i],i=1,2,...,n-1.

2 从顶点集合V-S中选出，满足dist[j]=Min{dist[ i ]|  V-S} ，就是当前求得的一条从出发的最短路径的终点。令S=S∪{j}。

3 修改从出发到集合V-S上任一顶点可达的最短路径长度：若dist[ j ]+arcs[j][k]

4 重复2&3操作n-1次，直到所有的顶点都包含在S中。

不适用边上带有负权值。 

Floyed算法求各顶点之间最短路径问题

递推产生一个n阶方阵序列，其中表示从顶点到的路径长度，k表示绕行第k个顶点的运算步骤。

定义一个n阶方阵序列，其中，

 是从顶点到、中间顶点是的最短路径的长度，是从顶点到、中间顶点的序号不大于k的最短路径长度。

,允许图中带有负权值的边，不允许有包含负权值的边组成的回路。

同样适用于带权无向图。

有向无环图描述表达式

有向无环图:若一个有向图中不存在环，则称为有向无环图，简称DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式
((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间，图6.21所示为该表达式的有向无环图表示。

拓扑排序

有向无环图：DAG

AOV网：DAG图&顶点表示活动的网络

邻接表存储时，拓扑排序，邻接矩阵

bool TopLogicalSort(Graph G){
	InitStack(S);//初始化栈，存储入度为0的顶点
	for(int i=0;inextarc){
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
			v=p->adjvex;
			if(!(--indegree[v]))
				Push(S,v);//入度为0，入栈 
		} 
	} 
	if(count 
关键路径 
基本概念 
 
 
关键路径：从源点到汇点的所有路径中，最大路径长度的路径。
 
 
关键活动：关键路径上的活动    l(i)-e(i)=0，即 l(i)=e(i)的活动
 
 
 
 
事件的最早发生时间ve(k):源点到顶点的最长路径长度
 
 
ve(源点)=0
 
 
ve(k)=Max{ve(j)+Weight(,)，}
 
 
Weight(,)表示<,>上的权值，为 的任意后继
 
 
 
 
事件的最迟发生时间vl(k):不推迟整个工程完成时间的前提下，后继事件在其最迟发生时间vl(j)能够发生时，该事件最迟必须发生的时间。
 
 
vl(汇点)=ve(汇点)
 
 
vl(k)=Min{vl(i)-Weight(,) }
 
 
 为 的任意前驱 
 
 
 
 
活动的最早开始时间e(i):该活动弧的起点所表示的事件的最早发生时间，若< , >表示活动，则
 
 
e(i)=ve(k)
 
 
 
 
活动的最迟开始时间l(i):该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差， 若< , >表示活动，则
 
 
l(i)=vl(i)-Weight( ,)
 
 
 
 
一个活动的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i)
 
 
指该活动完成的时间余量
 
 
求关键路径算法步骤 
 
 
1  从汇点出发，令 ve(源点)=0，按拓扑有序求其余顶点的最早发生时间ve( )
 
 
2  从汇点出发，令vl(汇点)=ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl( )
 
 
3  根据各顶点的ve( )值求所有弧的最早开始时间e( )
 
 
4  根据各顶点的vl( )值求所有弧的最迟开始时间l( )
 
 
5  求AOE网中所有活动的差额d( ),找出所有d( )=0的活动构成关键路径。
 
 
关键路径例题 
1)求ve():初始ve(1)=0，在拓扑排序输出顶点过程中，求得ve(2) = 3，ve(3)= 2，ve(4)=max {ve(2)+ 2, ve(3)+4} =max{5,6} =6, ve(5)=6, ve(6)= max {ve(5)+ 1, ve(4)+2, ve(3)+3}= max{7,8,5} =8。
 如果这是一道选择题，根据上述求ve()的过程就已经能知道关键路径。
 2)求vl():初始vl(6)=8，在逆拓扑排序出栈过程中，求得vl(5)=7，vl以(4)=6，vl(3) = min
 {vl(4)-4, vl(6)-3} = min{2,5} =2，vl(2) = min{vl(5)-3, vl(4)-2} = min{4,4} =4，vl(1)必然为0而无须再求。
 3)弧的最早开始时间e()等于该弧的起点的顶点的ve()，求得结果如下表所示。
 4)弧的最迟开始时间l(i)等于该弧的终点的顶点的vl()减去该弧持续的时间，求得结果如下
 表所示。
 5)根据l(i)-e(i)=0的关键活动，得到的关键路径为(v1, v3, v4, v6).