Monodyee

这个屌丝很懒，什么也没留下！

热门标签

数据结构及算法之图_有向图数据结构

作者：Monodyee | 2024-03-13 03:07:03

踩

有向图数据结构

图

图的一些概念定义在这里不做介绍了。

1 抽象数据类型图的形式定义

ADT Graph{
数据对象V: V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R:R = {VR}
VR={<v,w> | v,w ε V且p(v,w)，<v,w>表示从v到w的弧，谓词p(v,w)定义了弧<v,w>的意义或信息}
基本操作P:
CreateGraph( &G, V, VR )
初始条件:V是图的顶点集，VR是图中弧的集合。
操作结果:按V和VR的定义构造图G。
LocateVex( G, u )
初始条件:图G存在，u和G中顶点有相同特征。
操作结果:若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
DFSTraverse( G )
初始条件:图G存在。
操作结果:对图进行深度优先遍历。
BFSTraverse( G )
初始条件:图G存在。
操作结果:对图进行广度优先遍历。
}ADT Graph

2 图的存储结构

由于图的结构比较复杂，任意两个顶点之间都有可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构。

(1) 数组表示法

用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。

#define MaxInt    32767            //表示极大值，即00
#define MVNum     100              //最大顶点数
typedef char VerTexType;           //设顶点的数据类型为字符型
typedef int  ArcType;              //假设边的权值类型为整型
typedef struct{
	VerTexType     vexs[ MVNum ];           //顶点表
	ArcType        arcs[ MVNum ][ MVNum ];  //邻接矩阵
	int            vexnum,arcnum;           //图的当前点数和边数
}AMGraph;
1
2
3
4
5
6
7
8
9

创建图：
在这里插入图片描述

Status
CreateUDN( AMGraph &G ){
	//采用邻接矩阵表示法，创建无向网
	cin>>G.vexnum>>G.arcnum                     //输入总顶点数，总边数
	for( i = 0; i < G.vexnum; ++i )             //依次输入顶点信息
		cin >> G.vexs[ i ];
	for( i = 0; i < G.vexnum ; ++i )            //初始化邻接矩阵
		for( j = 0; j < G.vexnum; ++j )
			G.arcs[ i ][ j ] = MaxInt;          //边的权值均置为极大值
	for( k = 0; k < G.arcnum; ++k ){            //构造邻接矩阵
		cin>>v1>>v2>>w;                         //输入一条边所依附的顶点v1和v2以及边的权值w
		i = LocateVex( G, v1 );
		j = LocateVex( G, v2 );                 //确定v1和v2在G中的位置
		G.arcs[ i ][ j ] = w;                   //边<v1,v2>的权值置为w
		G.arcs[ i ][ j ] = G.arcs[ j ][ i ];    //置<v1,v2>的对称边<v2,v1>的权值为w;无向网和无向图的邻接矩阵均为对称矩阵
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Status
LocateVex( AMGraph &G, VerTexType u ){
	//图G中查找顶点u，存在则返回顶点表中的下标，否则返回-1
	int i;
	for( i = 0; i < G.vexnum; ++i )
		if( u == G.vexs[ i ] )
			return i;
	return -1;
}
1
2
3
4
5
6
7
8
9

Status
CreateUDG( AMGraph &G ){
	//采用邻接矩阵表示法，创建无向图
	cin>>G.vexnum>>G.arcnum                     //输入总顶点数，总边数
	for( i = 0; i < G.vexnum; ++i )             //依次输入顶点信息
		cin >> G.vexs[ i ];
	for( i = 0; i < G.vexnum ; ++i )            //初始化邻接矩阵
		for( j = 0; j < G.vexnum; ++j )
			G.arcs[ i ][ j ] = 0;              //均置为0
	for( k = 0; k < G.arcnum; ++k ){            //构造邻接矩阵
		cin>>v1>>v2>>w;                         //输入一条边所依附的顶点v1和v2以及边的权值w=1
		i = LocateVex( G, v1 );
		j = LocateVex( G, v2 );                 //确定v1和v2在G中的位置
		G.arcs[ i ][ j ] = w;                   //边<v1,v2>的权值置为w
		G.arcs[ i ][ j ] = G.arcs[ j ][ i ];    //置<v1,v2>的对称边<v2,v1>的权值为w;无向网和无向图的邻接矩阵均为对称矩阵
	}
	return OK;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Status
CreateDN( AMGraph &G ){
	//采用邻接矩阵表示法，创建有向网
	cin>>G.vexnum>>G.arcnum                     //输入总顶点数，总边数
	for( i = 0; i < G.vexnum; ++i )             //依次输入顶点信息
		cin >> G.vexs[ i ];
	for( i = 0; i < G.vexnum ; ++i )            //初始化邻接矩阵
		for( j = 0; j < G.vexnum; ++j )
			G.arcs[ i ][ j ] = MaxInt;          //边的权值均置为极大值
	for( k = 0; k < G.arcnum; ++k ){            //构造邻接矩阵
		cin>>v1>>v2>>w;                         //输入一条边所依附的顶点v1和v2以及边的权值w
		i = LocateVex( G, v1 );
		j = LocateVex( G, v2 );                 //确定v1和v2在G中的位置
		G.arcs[ i ][ j ] = w;                   //边<v1,v2>的权值置为w
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Status
CreateDG( AMGraph &G ){
	//采用邻接矩阵表示法，创建有向图
	cin>>G.vexnum>>G.arcnum                     //输入总顶点数，总边数
	for( i = 0; i < G.vexnum; ++i )             //依次输入顶点信息
		cin >> G.vexs[ i ];
	for( i = 0; i < G.vexnum ; ++i )            //初始化邻接矩阵
		for( j = 0; j < G.vexnum; ++j )
			G.arcs[ i ][ j ] = 0;               //均置为0
	for( k = 0; k < G.arcnum; ++k ){            //构造邻接矩阵
		cin>>v1>>v2>>w;                         //输入一条边所依附的顶点v1和v2以及边的权值w=1
		i = LocateVex( G, v1 );
		j = LocateVex( G, v2 );                 //确定v1和v2在G中的位置
		G.arcs[ i ][ j ] = w;                   //边<v1,v2>的权值置为w
	}
	return OK;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

邻接矩阵的缺点:
不便于增加和删除顶点
浪费空间
浪费时间

(2) 邻接表

在这里插入图片描述
顶点的结点结构：

typedef struct VNode{
	VerTexType       data;          //顶点信息
	ArcNode          *firstarc;    //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];             //AdjList表示邻接表类型
1
2
3
4

边结点的结构：

typedef struct ArcNode{
	int                adjvex;          //该边所指向的顶点的位置
	struct ArcNode     *nextarc;        //指向下一条边的执行
	Otherlnfo          info;            //和边相关的信息
}ArcNode;
1
2
3
4
5

图的结构：

typedef struct{
	AdjList           vertices;          //verticex-vertex的复数
	int               vexnum,arcnum;     //图的当前顶点数和边数
}ALGraph; 
1
2
3
4

在这里插入图片描述
创建图：

Status
CreateUDG( ALGraph &G ){
	//采用邻接表表示法，创建无向图
	cin>>G.vexnum>>G.arcnum;               //输入总顶点数和边数
	for( i = 0; i < G.vexnum; ++i ){       //输入各点，构造表头结点表
		cin>>G.vertices[ i ].data;         //输入各顶点值
		G.vertices[ i ].firstarc = NULL;   //初始化表头结点的指针域
	}
	for( k = 0; k < G.arcnum; ++k ){       //输入各边，构造邻接表
		cin>>v1>>v2;                       //输入一条边依附的2个顶点
		i = LcoateVex( G, v1);
		j = LcoateVex( G, v2);
		
		p1 = new ArcNode;                          //生成一个新的边结点
		p1->adjvex = j;                           //邻接点序号为j
		p1->nextarc = G.vertices[ i ].firstarc;   //头插法，将新结点片p1插入顶点vi的边表头部
		G.vertices[ i ].firstarc = p1;

		p2 = new ArcNode;                          //生成一个新的边结点
		p2->adjvex = i;                           //邻接点序号为j
		p2->nextarc = G.vertices[ j ].firstarc;   //头插法，将新结点片p2插入顶点vi的边表头部
		G.vertices[ j ].firstarc = p2;		           
	}
	return OK;
}
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

Status
CreateDG( ALGraph &G ){
	//采用邻接表表示法，创建有向图
	cin>>G.vexnum>>G.arcnum;               //输入总顶点数和边数
	for( i = 0; i < G.vexnum; ++i ){       //输入各点，构造表头结点表
		cin>>G.vertices[ i ].data;         //输入各顶点值
		G.vertices[ i ].firstarc = NULL;   //初始化表头结点的指针域
	}
	for( k = 0; k < G.arcnum; ++k ){       //输入各边，构造邻接表
		cin>>v1>>v2;                       //输入一条边依附的2个顶点
		i = LcoateVex( G, v1);
		j = LcoateVex( G, v2);
		
		p1 = new ArcNode;                          //生成一个新的边结点
		p1->adjvex = j;                           //邻接点序号为j
		p1->nextarc = G.vertices[ i ].firstarc;   //头插法，将新结点片p1插入顶点vi的边表头部
		G.vertices[ i ].firstarc = p1;
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Status
CreateDG( ALGraph &G ){
	//采用邻接表表示法，创建有向图逆邻接表
	cin>>G.vexnum>>G.arcnum;               //输入总顶点数和边数
	for( i = 0; i < G.vexnum; ++i ){       //输入各点，构造表头结点表
		cin>>G.vertices[ i ].data;         //输入各顶点值
		G.vertices[ i ].firstarc = NULL;   //初始化表头结点的指针域
	}
	for( k = 0; k < G.arcnum; ++k ){       //输入各边，构造邻接表
		cin>>v1>>v2;                       //输入一条边依附的2个顶点
		i = LcoateVex( G, v1);
		j = LcoateVex( G, v2);
		
		p2 = new ArcNode;                          //生成一个新的边结点
		p2->adjvex = i;                           //邻接点序号为j
		p2->nextarc = G.vertices[ j ].firstarc;   //头插法，将新结点片p2插入顶点vi的边表头部
		G.vertices[ j ].firstarc = p2;		           
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

邻接矩阵多应用于稠密图，而邻接表多应用于稀疏图。

3 图的遍历

我们希望从图的某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。我们设置一个辅助数组visited[0…n-1]，它的初始置为FALSE，一旦访问了顶点v_i，便置visited[i]为 TRUE。

(1) 深度优先遍历DFS

在这里插入图片描述

void 
DFS( AMGraph G, int v ){                //图G为邻接矩阵类型
	cout<<v; visited[ v ] = TRUE;      //访问第v个顶点
	for( w = 0; w < G.vexnum; ++w )    //依次检查邻接矩阵v所在的行
		if( (G.arcs[v][w] != 0) && ( !visited[ w ] ))
			DFS( G, w );               //w是v的邻接点，如果w未被访问，则递归调用DFS
}
1
2
3
4
5
6
7

void
DFS( ALGraph G, int v ){               //图G为邻接表类型
	cout<<v; visited[ v ] = TRUE;      //访问第v个顶点
	for( w = firstAdjVex( G, v ); w >= 0; w = NextAdjVex( G, v, w ))
		if( !visited[ w ] )
			DFS( G, w );             //对v的尚未访问的邻接顶点w递归调用DFS
}
1
2
3
4
5
6
7

(2) 广度优先遍历BFS

从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的结点作起始点，重复上述过程。

void
BFS( Graph G, int v ){                    //按广度优先非递归遍历连通图G
	cout<<v;      visited[ v ] = TRUE;   //访问第v个顶点
	InitQueue( Q );                      //辅助队列Q初始化，置空
	EnQueue( Q, v );                     //v进队
	while( !QueueEmpty( Q )){            //队列非空
		DeQueue( Q, u );                 //队头元素出队并置为u
	for( w = firstAdjVex( G, u ); w >= 0; w = NextAdjVex( G, u, w ))
		if( !visited[ w ] ){
			cout<<w;
			visited[ w ] = TRUE;
			EnQueue( Q, w );             //w进队
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4 最小生成树

构造最小生成树有很多中算法，其中多数算法利用了最小生成树的MST性质。
在这里插入图片描述

(1) 普里姆算法

在这里插入图片描述

void
MinSpanTree_PRIM( MGraph G, VertexType u ){
	//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各边
	//记录从顶点集U到V-U的代价最小的边的辅助数组定义
	//struct{
	//		VertexType      adjvex;
	//		VRType          lowcost;
	//}closedge[ MVNum ];
	k = LocateVex( G, u );
	for( j = 0; j < G.vexnum; ++j )         //辅助数组初始化
		if( j != k )
			closedge[ j ] = { u, G.arcs[ k ][ j ].adj };
			closedge[ k ].lowcost = 0;     //初始U={u}
	for( i = 1; i < G.vexnum; ++i ){       //选择其余G.vexnum-1个顶点
		k = mininum(closedge);            //求出T的下一个顶点:第k顶点
		//此时closedge[k].lowcost=
		//MIN{closedge[vi].lowcost | closedge[vi].lowcost>0,vi ε V-U}
		printf( closedge[ k ].adjvex, G.vexs[ k ] );   //输出生成树的边
		closedge[ k ].lowcost = 0;        //第k顶点并入U集
	for( j = 0; j < G.vexnum; j++ )
	//新顶点并入U后重新选择最小边
		if( G.arcs[ k ][ j ].adj < closedge[ j ].lowcost )
			closedge[ j ] = { G.vexs[ k ], G.arcs[ k ][ j ].adj};
	}
}
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

(2) 克鲁斯卡尔算法

在这里插入图片描述

5 最短路径

单源最短路径-----------用DijKstra算法(迪杰斯特拉算法)
所以顶点之间的最短路径----------用Floyd算法(弗洛伊德算法)

DijKstra算法

在这里插入图片描述

void
ShortestPath_DIJ( MGraph G, int v0, PathMatrix &p, shortPathTable &D){
	//用DijKstra算法求有向网G的v0顶点到其余顶点v的最短路径p[v]及其带权长度D[v]
	//若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
	//final[v]为TRUE当且仅当v ε S,即已经求得从v0到v的最短路径
	for( v = 0; v < G.vexnum; ++v ){
		final[ v ] = FALSE;
		D[ v ] = G.arcs[ v0 ][ v ];
		for( w = 0; w < G.vexnum; ++w )
			p[ v ][ w ] = FALSE;       //设空路径
			if( D[ v ] < INFINITY ){
			p[ v ][ v0 ] = TRUE;
			p[ v ][ v ] = TRUE;
		}
	}
	D[ v0 ] = 0;   
	final[ v0 ] = TRUE;         //初始化，v0顶点属于S集
	//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集
	for( i = 1; i < G.vexnum; ++i ){          //其余G.vexnum-1个顶点
		min = INFINITY;                       //当前所知离v0顶点最近距离
		for( w = 0; w < G.vexnum; ++w )
			if( !final[ w ] )                 //w顶点在V-S中
				if( D[ w ] < min){            //w顶点离v0顶点更近
					v = w;
					min = D[ w ];
		}
		final[ v ] = TRUE;                  //离v0顶点最近的v加入S集
		for( w = 0; w < G.vexnum; ++w )     //更新当前最短路径及距离
			if( !final[ w ] && ( min + G.arcs[ v ][ w ] < D[ w ])){
			//修改D[w]和P[w]，w ε V-S
				D[ w ] = min + G.arcs[ v ][ w ];
				p[ w ] = p[ v ];
				p[ w ][ w ] = TRUE;
			}	
	}
}
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
36

Floyd算法

void
ShortestPath_FLOYD( MGraph G, PathMatrix &p[], DistancMatrix &D){
	//用Floyd算法求有向网G中各对顶点v和w之间的最短路径p[v][w]及其
	//带权长度D[v][w].若p[v][w][u]为TRUE，则u是从v到w当前求得
	//最短路径上的顶点。
	for( v = 0; v < G.vexnum; ++v )             //各对结点之间初始已知路径及距离
		for( w = 0; w < G.vexnum; ++w ){
			D[ v ][ w ] = G.arcsD[ v ][ w ];
			for( u = 0; u < G.vexnum; ++u )
				p[ v ][ w ][ u ] = FALSE;
			if( D[ v ][ w ] < INFINITY ){      //从v到w有直接路径
				p[ v ][ w ][ v ] = TRUE;
				p[ v ][ w ][ w ] = TRUE;
		}
	}
	for( u = 0; u < G.vexnum; ++u )
		for( v = 0; v < G.vexnum; ++v )
			for( w = 0; w < G.vexnum; ++w )
				if( D[ v ][ u ] + D[ u ][ w ] < D[ v ][ w ] ){
				//从v经u到w的一条路径更短
					D[ v ][ w ] + D[ v ][ u ] < D[ u ][ w ];
					for( i = 0; i < G.vexnum; ++i )
						p[ v ][ w ][ i ] = p[ v ][ u ][ i ] || p[ u ][ w ][ i ];
	}
}
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

6 拓扑排序

一个无环的有向图称做有向无环图。拓扑排序算法:
(1) 在有向图中选一个没有前驱的结点且输出之。
(2)从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或当前图中不存在无前驱的顶点为止，后一种情况则说明有向图中存在环。
在这里插入图片描述

Status
TopologicalSort( ALGraph G ){
	//有向图G采用邻接表存储结构
	//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR
	FindInDegree( G,indegree );        //对各顶点求入度
	InitStack( S );
	for( i = 0; i < G.vexnum; ++i )    //建零入度顶点栈S
		if( !indegree[ i ] )           //入度为0者进栈
			push( S, i );
		count = 0;                     //对输出顶点计数
	while( !StackEmpty( S )){
		Pop( S, i );
		printf( i ,G.vertices[ i ].data );       //输出i号顶点并计数
		++count;
		for( p = G.vertices[ i ].firstarc; p; p = p->nextarc ){
			k = p->adjvex;        //对i号顶点的每个邻接点的入度减1
			if( !( --indegree[ k ] ))         //如入度减为0，则入栈
				Push( S, k );
		}
	}
	if( count < G.vexnum )                   //该有向图有回路
		return ERROR;
	else
		return OK;
}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/227464

数据结构及算法之图_有向图数据结构

目录

图

1 抽象数据类型图的形式定义

2 图的存储结构

(1) 数组表示法

(2) 邻接表

3 图的遍历

(1) 深度优先遍历DFS

(2) 广度优先遍历BFS

4 最小生成树

(1) 普里姆算法

(2) 克鲁斯卡尔算法

5 最短路径

DijKstra算法

Floyd算法

6 拓扑排序