菜鸟追梦旅行

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

热门标签

[C语言]图的总结_c语言图

作者：菜鸟追梦旅行 | 2024-05-28 01:32:25

踩

c语言图

文章目录

图

在这里插入图片描述

定义: 由顶点的有穷非空集合和顶点之间的边的集合组成,表示为:G(V,E),其中,G表示一个图,V表示顶点集合,E表示边的集合

注:顶点集合不能为空,边集为空

各种图定义

无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),可用无序偶对表示为:(Vi,Vj)

若图中任意两个顶点之间的边都是无向边,则称该图为无向图.

G = (V,{E})

V = {A,B,C,D}

E = {(A,B),(A,C),(B,C),(C,D),(D,A)}
有向边:若顶点Vi到Vj的边有方向,则称此条边为有向边,也成为弧(Arc),可用有序偶对表示为:<Vi,Vj>,

Vi为弧尾(Tail),Vj为弧头(Head).

若图中任意两个顶点之间的边都是有向边,则称此图为有向图.

G = (V,{E})

V = {A,B,C,D}

E = {<A,D>,<B,A>,<C,A>,<B,C>}
简单图:在图中不存在顶点到自身的边,且同一条边不重复出现,则称这样的图为简单图
无向完全图:在无向图中,任意两个顶点之间都有边,称此图为无向完全图.

含有N个顶点的无向完全图拥有的边数为:
$N * (N - 1) / 2$
所以N个顶点的无向图最多拥有N*(N-1)/2条边
有向完全图:在有向边中,任意两个顶点之间都存在方向互为相反的两条弧,则称此图为有向完全图,

含有N个顶点的有向完全图拥有的边数为:
$N * (N - 1)$
所以N个顶点的有向图最多拥有N*(N-1)/2条边
稠密图与稀疏图:对于N个顶点和M条边的图,M远小于N^2的图成为稀疏图,M较大的图称为稠密图(边或弧多称为稠密图,反之称为稀疏图).
权值:与图的边或弧相关的数叫做权,带权的图称为网.
子图:存在两个图 G = (V,{E}) 和 G’ = (V’,{E’}) 若V’ 包含于 V,E’ 包含于 E.则称G’为G的子图(Subgraph)

图的顶点与边间关系

对于无向图G = (V,{E}),若(V,V’) 属于 E则称V和V’互为邻接点(Adjacent),即V和V’相邻接

V的度(Degree)是与V相连接的边的数目记为:TD(V).

边数(e)是各顶点度数和的一半即
$1/2*\sum (i = 1,n)TD(Vi)$
对于有向图G = (V,{E}),以顶点V为头的弧的数目称为V的入度(InDegree),记作ID(V)

以顶点V为尾的弧的数目称为V的出度(OutDegree),记作OD(V).

顶点D的度为TD(V) = ID(V) + OD(V)

所以边数(e)为所有顶点的入度和或者出度和:
$\sum(i = 1,n)ID(Vi) = \sum(i = 1,n)OD(Vi)$
无向图G = (V,{E})中的路径(Path)是一个顶点序列(Vi,Vj),其中(Vi,Vj) 属于 E.

路径的长度是路径上的边或弧的数目
第一个顶点到最后一个顶点相同的路径称为回路或者环(Cycle).序列中顶点不重复出现的路径称为简单路径,除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路或者简单环.

连通图的相关术语

连通图:在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点Vi, Vj∈E, Vi和Vj都是连通的，则称G是连通图(ConnectedGraph).

例子:

此图的连通分量为:

和
一个连通图的生成树是一个极小的连通子图,它含有全部N个顶点,拥有构成一颗树的N-1条边.

所以:一个图有N个顶点和小于N-1条边,一定不是连通图,多余N-1条边,则一定有环.

图的存储结构

邻接矩阵(AdjGraph):使用两个矩阵来表示图:一维数组Vex存储顶点,二维数组map存储边或弧的信息

可以存储边数较多的稠密图

/*构建邻接矩阵*/
typedef char VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define MAXVEX 100  //最大顶点数
#define INF	9999	//表示无穷大

typedef struct
{
	VexType vexs[MAXVEX];	//顶点表
	EdgeType map[MAXVEX][MAXVEX];	//邻接矩阵
	int vexnum,edgenum;	//顶点数和边数
} AdjGraph; //邻接矩阵

void InitAdjGraph(AdjGraph* M)//初始化邻接矩阵
{
	printf("输入顶点数和边数:");
	scanf("%d%d",&(M->vexnum),&(M->edgenum));
	for(int i = 0; i<M->vexnum; i++)
	{
		for(int j = 0; j<M->vexnum; j++)
		{
			if(i == j)
				M->map[i][j] = 0;//自身不能到自身
			else
				M->map[i][j] = INF;
		}
	}
	fflush(stdin);
	printf("输入顶点:");//构建顶点表
	for(int i = 0; i<M->vexnum; i++)
		scanf("%c",&(M->vexs[i]));
	fflush(stdin);
	for(int i = 0; i<M->edgenum; i++) //构建邻接矩阵
	{
		printf("输入边(Vi,Vj)的下标i,j和该边权值w:");
		int l,r;
		EdgeType w;
		scanf("%d%d%d",&l,&r,&w);
		M->map[l][r] = w;
//		M->map[r][l] = w;//有向图 
	}
}

void Print(AdjGraph* M)//展示
{
	printf("顶点表为\n");
	for(int i = 0; i<M->vexnum; i++)
		printf("%c ",M->vexs[i]);
	printf("\n邻接矩阵为\n");
	for(int i = 0; i<M->vexnum; i++)
	{
		for(int j = 0; j<M->vexnum; j++)
			printf("%-4d ",M->map[i][j]);
		putchar('\n');
	}
}

int main()
{
    AdjGraph *M = (AdjGraph*)malloc(sizeof(AdjGraph));
	InitAdjGraph(M);
	Print(M);
    return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

效果图:
在这里插入图片描述

邻接表(AdjList):采用数组和链表相结合的方式

可以存储边较少的图

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define MAXVEX 100  //最大顶点数
#define INF 9999//表示不连通

typedef struct EdgeNode
{
	int index;	//节点下标
	EdgeType weight;	//权值
	struct EdgeNode* next;
} EdgeNode;	//边表节点

typedef struct
{
	VexType vex;	//顶点
	EdgeNode *firstedge;	//指向第一个边节点
} VexNode; //顶点表节点

typedef struct
{
	VexNode list[MAXVEX];	//顶点表节点数组
	int vexnum,egdenum;  //顶点数和边数
} AdjList; //邻接表

void InitAdjList(AdjList* M)//初始化邻接表
{
	printf("输入顶点数和边数:");
	scanf("%d%d",&(M->vexnum),&(M->egdenum));
	fflush(stdin);
	printf("输入顶点:");
	for(int i = 0; i<M->vexnum; i++)
	{
		scanf("%c",&(M->list[i].vex));
		M->list[i].firstedge = NULL;  //将边表制空
	}
	fflush(stdin);
	for(int i = 0; i<M->egdenum; i++)//输入边
	{
		printf("输入边(Vi,Vj)的下标i,j和该边权值w:");
		int l,r;
		EdgeType w;
		scanf("%d%d%d",&l,&r,&w);

		EdgeNode* edge;

		edge = (EdgeNode*)malloc(sizeof(EdgeNode));//头插法
		edge->index = r;//记录下标
		edge->weight = w;
		edge->next = M->list[l].firstedge;
		M->list[l].firstedge = edge;

//		edge = (EdgeNode*)malloc(sizeof(EdgeNode));//无向图
//		edge->index = l;
//		edge->weight = w;
//		edge->next = M->list[r].firstedge;
//		M->list[r].firstedge = edge;
	}
}

void Print(AdjList* M)//展示
{
	for(int i = 0; i<M->vexnum; i++)
	{
		printf("%c:\n",M->list[i].vex);
		EdgeNode *p = M->list[i].firstedge;
		while(p)
		{
			printf("_%c -> %c = %d\n",M->list[i].vex,M->list[p->index].vex,p->weight);
			p = p->next;
		}
	}
}

int main()
{
    AdjList *M = (AdjList*)malloc(sizeof(AdjList));
    InitAdjList(M);
    Print(M);
    return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

效果图:
在这里插入图片描述

十字链表(OrthList)–有向图邻接表的改进,可以获取某顶点入度和出度

#include<stdio.h>
#include<stdlib.h>
typedef char VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define MAXVEX 100  //最大顶点数 

typedef struct EdgeNode
{
	int startvex;  //弧起点的下标
	int endvex;	   //弧终点的下标
	EdgeType weight;	//权值
	struct EdgeNode *endnext;	//入边表指针域,指向终点相同的下一条边,查找in入度时用找和endvex相同的点
	struct EdgeNode *startnext; //出边表指针域,指向起点相同的下一条边,查找out出度时用找和start相同的点
} EdgeNode; //边表节点

typedef struct
{
	VexType vex;  //顶点
	EdgeNode *firstin;  //指向入边表的第一个节点
	EdgeNode *firstout;  //指向出边表的第一个节点
} VexNode;  //顶点表节点

typedef struct
{
	VexNode list[MAXVEX];  //顶点表节点数组
	int vexnum,edgenum;    //顶点数和边数
} OrthList;  //正交链表

void InitOrthList(OrthList* M)//初始化
{
	printf("输入顶点数和边数:");
	scanf("%d%d",&(M->vexnum),&(M->edgenum));
	fflush(stdin);
	printf("输入顶点:");
	for(int i = 0; i<M->vexnum; i++)
	{
		scanf("%c",&(M->list[i].vex));
		M->list[i].firstin = NULL;
		M->list[i].firstout = NULL;
	}
	fflush(stdin);
	for(int i = 0; i<M->edgenum; i++)
	{
		printf("输入边(Vi,Vj)的下标i,j:");
		int l,r;
		scanf("%d%d",&l,&r);

		EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//头插法
		edge->startvex = l;
		edge->endvex = r;

		edge->startnext = M->list[l].firstout;  //让下标为start的表头节点的firstout为这个,来找end 
		M->list[l].firstout = edge;
		edge->endnext = M->list[r].firstin;		//让下标为end的表头节点的firstin为这个,来找start 
		M->list[r].firstin = edge;
	}
}

void Print(OrthList* M)//展示
{
	for(int i = 0; i<M->vexnum; i++)
	{
		printf("%c的入度为:",M->list[i].vex);
		for(EdgeNode *p = M->list[i].firstin; p; p = p->endnext)
			printf("%c ",M->list[p->startvex].vex);
		putchar('\n');
	}
	for(int i = 0; i<M->vexnum; i++)
	{
		printf("%c的出度为:",M->list[i].vex);
		for(EdgeNode *p = M->list[i].firstout; p; p=p->startnext)
			printf("%c ",M->list[p->endvex].vex);
		putchar('\n');
	}
}

int main()
{
	OrthList *M = (OrthList*)malloc(sizeof(OrthList));
	InitOrthList(M);
	Print(M);
	return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

效果图:
在这里插入图片描述

邻接多重表–无向图的优化,便于对边进行操作

//有向图,当对边进行删除或者标记时很方便 
#include<stdio.h>
#include<stdlib.h>
typedef char VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define MAXVEX 100  	//最大顶点数

typedef struct EdgeNode
{
	int lvex;				//左边的节点下标
	int rvex;				//右边的节点下标
	EdgeType weight;		//权重
	struct EdgeNode *lnext;	//指向rvex和目前这个的lvex一样的节点
	struct EdgeNode *rnext; //指向rvex和目前这个的rvex一样的节点
} EdgeNode;	//边表节点

typedef struct
{
	VexType vex;
	EdgeNode *firstedge;
} VexNode;//表头结点

typedef struct
{
	VexNode list[MAXVEX];//邻接多重表
	int vexnum,edgenum;
} AdjList;
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

边集数组–边的集合,便于对边进行操作

由两个一维数组构成,一个一维数组存储顶点信息,一个一维结构体数组存储一条边的起点下标(begin),终点下标,权值组成

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define MAXVEX 100  //最大顶点数
#define MAXEDGE 200 //最大边数
#define INF 9999

typedef struct
{
	int begin,end;    //起点和终点的下标
	EdgeType weight;  //权值
} EdgeNode;

typedef struct
{
	VexType vexs[MAXVEX];   //顶点表
	EdgeNode edge[MAXEDGE];	//边数组
	int vexnum,edgenum;     //顶点数和边数
} EdgeArray;//边集数组 

void InitEdgeArray(EdgeArray* M)
{
	printf("输入顶点数和边数:");
	scanf("%d%d",&(M->vexnum),&(M->edgenum));
	fflush(stdin);
	printf("输入顶点:");
	for(int i = 0; i<M->vexnum; i++)
		scanf("%c",&(M->vexs[i]));
	fflush(stdin);
	for(int i = 0; i<M->edgenum; i++)
	{
		printf("输入边(Vi,Vj)的下标i,j和该边权值w:");
		scanf("%d%d%d",&(M->edge[i].begin),&(M->edge[i].end),&(M->edge[i].weight));
	}
}

void Print(EdgeArray* M)
{
	printf("顶点表为\n");
	for(int i = 0; i<M->vexnum; i++)
		printf("%c ",M->vexs[i]);
	putchar('\n');
	printf("边数组为\n");
	for(int i = 0; i<M->edgenum; i++)
		printf("%d %d %d\n",M->edge[i].begin,M->edge[i].end,M->edge[i].weight);
}

int main()
{
	EdgeArray *M = (EdgeArray*)malloc(sizeof(EdgeArray));
	InitEdgeArray(M);
	Print(M);
	return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

效果图:
在这里插入图片描述

图的遍历

邻接矩阵

深度优先搜索(DFS)

int visited[MAXVEX];//访问标记的数组

void DFS(AdjGraph* M,int i)//邻接矩阵的深度优先遍历算法--以每个点为跳板找其他连着的点 
{
	visited[i] = 1;//标记为已经访问过
	printf("%c ",M->vexs[i]);
	for(int j = 0; j<M->vexnum; j++)//遍历顶点 
	{
		if(M->map[i][j]!=INF && visited[j]==0)//如果有边而且没有被访问过就DFS它 
		{
			DFS(M,j);
		}
	}
}

void DFSTraverse(AdjGraph* M)//邻接矩阵的深度优先遍历操作
{
	memset(visited,0,M->vexnum*(sizeof(int)));//初始化标记数组为0表示未被访问过
	printf("深度优先遍历为:\n");
	for(int i = 0; i<M->vexnum; i++)
		if(visited[i]==0)//没有被访问过就DFS它 
		{
			DFS(M,i);
			printf("\n");
		}
}
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

广度优先搜索(BFS)

int visited[MAXVEX];//访问标记的数组

void BFSTraverse(AdjGraph* M)//邻接矩阵的广度优先遍历算法-- 遇到一个点就把和它相连接的点压入队列,然后继续往下遍历 
{
	memset(visited,0,M->vexnum*(sizeof(int)));//初始化visited数组
	printf("广度优先遍历为:\n");
	queue<int> Que;
	for(int i = 0; i<M->vexnum; i++)//遍历顶点 
	{
		if(visited[i] == 0)//找到没访问过的点 
		{
			visited[i] = 1;//标记访问过然后压入队列尾并打印 
			Que.push(i);
			printf("%c ",M->vexs[i]);
			
			while(!Que.empty())
			{
				i = Que.front();//这里i可以更新到最近的一个已经访问过的点 
				for(int j = 0; j<M->vexnum; j++)//遍历顶点 
				{
					if(M->map[i][j] != INF && visited[j]==0)//如果有边而且没有被访问过 
					{
						visited[j] = 1;//标记访问过然后压入队列尾并打印 
						Que.push(j);
						printf("%c ",M->vexs[j]);
					}
				}
				Que.pop();//弹出队首顶点 
			}
		}
	}
}
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

邻接表

深度优先搜索(DFS)

int visited[MAXVEX];//访问标记数组

void DFS(AdjList* M,int i)//邻接表的深度优先搜索算法
{
	visited[i] = 1;
	printf("%c ",M->list[i].vex);
	EdgeNode* p = M->list[i].firstedge;//从第一个与它连着的边开始 
	while(p)
	{
		if(visited[p->index]==0)//判断这个点有没有被访问过,没访问过就DFS它 
			DFS(M,p->index);
		p=p->next;
	}
}

void DFSTraverse(AdjList* M)//邻接表的深度优先搜索操作
{
	memset(visited,0,M->vexnum*(sizeof(int)));
	printf("\n深度优先搜索:\n");
	for(int i = 0; i<M->vexnum; i++)//遍历顶点 
		if(visited[i]==0)//遇到没被访问过的点就DFS它 
		{
			DFS(M,i);
			printf("\n");
		}
}
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

广度优先搜索(BFS)

void BFSTraverse(AdjList* M)//邻接表的广度优先搜索操作
{
	memset(visited,0,M->vexnum*(sizeof(int)));
	printf("广度优先遍历为:\n");
	queue<int> Que;
	for(int i = 0;i<M->vexnum;i++)//遍历顶点 
	{
		if(visited[i]==0)
		{
			visited[i] = 1;
			Que.push(i);
			printf("%c ",M->list[i].vex);
			while(!Que.empty())
			{
				i = Que.front();//更新i为最近的一个已经被访问的点 
				EdgeNode* p = M->list[i].firstedge;//遍历与它相连的顶点 
				while(p)
				{
					if(visited[p->index]==0)//如果这个点没被访问过,就压入队列尾 
					{
						Que.push(p->index);
						visited[p->index] = 1;
						printf("%c ",M->list[p->index].vex);
					}
					p = p->next;
				}
				Que.pop();//弹出队首的点 
			}
		}
	}
}
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

最小生成树

普里姆(Prim)算法–从某一顶点开始构建树,每次找到目前离顶点最近的点,然后通过这个点来更新顶点与其他点的权值,从而构建最小树 --使用邻接矩阵存储

void MiniSpanTree_Prim(AdjGraph* M) 
{
	printf("最小生成图为:\n");
	int adjvex[MAXVEX];//保存相关顶点的下标,表示该顶点是由某个顶点延伸下来的
	EdgeType edgewight[MAXVEX];//保存顶点到各顶点的权值
	for(int i = 0; i<M->vexnum; i++)
	{
		adjvex[i] = 0;//先初始化都是0
		edgewight[i] = M->map[0][i];//存储根节点vexs[0]到各个顶点的距离,0表示已经被纳入树的节点 
	}
	for(int i = 1; i<M->vexnum; i++)
	{
		int min = INF,num;//min为搜索到离根节点的最小权值,num为离根节点最近的顶点的下标
		for(int j = 1; j<M->vexnum; j++)//搜索目前最短的边 
		{
			if(edgewight[j]!=0 && edgewight[j]<min)
			{
				min = edgewight[j];
				num = j;
			}
		}
		//此时的num存的就是离根节点最短的点的下标 
		printf("%c -> %c : %d\n",M->vexs[adjvex[num]],M->vexs[num],M->map[adjvex[num]][num]);//打印当前顶点中权值最小的边 
		edgewight[num] = 0;//表示该顶点已经被打印
		for(int j = 1; j<M->vexnum; j++)//循环所有定点,通过目前最短的边来更新根节点到其他顶点的权值 
		{
			if(edgewight[j] != 0 && M->map[num][j] < edgewight[j])//判断这个边是否可以通过此节点变得更小[因为此节点是目前离根节点最近的顶点了] 
			{
				edgewight[j] = M->map[num][j];
				adjvex[j] = num; //表示此顶点是由下标为num的顶点所连接 
			}
		}
	}
}
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

样例:

在这里插入图片描述
效果图:

克鲁斯卡尔(KrusKul)算法–先按照权值从小到大排序,每次遍历,如果可以加入树就加入树,可以从图中某一顶点开始构建树–使用边集数组存储

int Find(int *parent,int num)//找头头
{
	if(parent[num] == num)//发现自己就是头头,说明找到这个组织的头了 
		return num;
	else
	{
		parent[num] = Find(parent,parent[num]);//顺便可以统一下头头,我的头头是我头头的头头 
		return parent[num];
	}
}

void MiniSpanTree_Kruskal(EdgeArray* M)//最小生成树 Kruskal 算法--先按照权值从小到大排序,每次遍历,如果可以加入树就加入树,可以从图中某一顶点开始构建树--边集数组 
{
	printf("\n最小生成树为:\n");
	int parent[MAXEDGE];//判断是否会形成回路的数组
	for(int i = 0; i<M->vexnum; i++) //先初始化为自身下标表示自己是自己的头头
		parent[i] = i;
	qsort(M->edge,M->edgenum,sizeof(M->edge[0]),cmp);//按照边的权值将边从小到大排序
	for(int i = 0; i<M->edgenum; i++)
	{
		int m = Find(parent,M->edge[i].begin);//寻找左边节点的头头
		int n = Find(parent,M->edge[i].end);//寻找右边节点的头头
		if(m!=n)//如果两个节点的头头不相同说明两个节点不在一个集合中,即不会形成回路,即可以构成树
		{
			parent[n] = m;//表示m点已经在以n点为头的集合之中,[人为规定靠左]
			printf("%c -> %c : %d\n",M->vexs[M->edge[i].begin],M->vexs[M->edge[i].end],M->edge[i].weight);//打印 
		}
	}
}
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

测试样例和上面那个一样

效果图:
在这里插入图片描述

最短路径

Floyd_Warshall 算法–多源求解最短路径–注:可以解决带有负边权的图–邻接矩阵

int cmp(const void* a,const void* b)
{
    EdgeNode *m = (EdgeNode*)a;
    EdgeNode *n = (EdgeNode*)b;
    return m->weight - n->weight;
}
void Floyd_Warshall(AdjGraph* M)//多源求解最短路径 注:可以解决带有负边权的图--邻接矩阵
{
	for(int i = 0; i<M->vexnum; i++)//通过此顶点来松弛各边
		for(int j = 0; j<M->vexnum; j++)
			for(int k = 0; k<M->vexnum; k++)
				if(M->map[j][k]>M->map[j][i]+M->map[i][k])//判断j到k顶点能否通过k顶点来松弛
					M->map[j][k] = M->map[j][i]+M->map[i][k];
	int start,end;
	printf("输入从ai到aj顶点的下标i和j:");
	scanf("%d%d",&start,&end);
	if(M->map[start][end]==INF)
		printf("INF\n");
	else
		printf("%d\n",M->map[start][end]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

在这里插入图片描述

Dijkstra算法–单源求解最短路径–稠密图适合用这种方式–注:不能解决负边权–邻接矩阵

void Dijkstra(AdjGraph* M) //单源求解最短路径--稠密图适合用这种方式--注:不能解决负边权--邻接矩阵
{
	int num;
	EdgeType dis[MAXVEX];//到每个顶点的距离
	int book[MAXVEX] = {0};//标记是否通过此顶点进行松弛过
	printf("输入需要求解的顶点的下标:");
	scanf("%d",&num);
	for(int i = 0; i<M->vexnum; i++)//先初始化dis数组为num到各个顶点的距离
		dis[i] = M->map[num][i];
	book[num] = 1;//表示不需要通过num顶点松弛
	for(int i = 0; i<M->vexnum; i++)
	{
		int min = INF;
		int p;
		for(int j = 0; j<M->vexnum; j++)//找到目前离顶点最近的顶点 下标为p
		{
			if(book[j]==0 && dis[j]<min)
			{
				min = dis[j];
				p = j;
			}
		}
		for(int j = 0; j<M->vexnum; j++)//通过这个最近的顶点所连接的边来松弛dis数组 
		{
			if(M->map[p][j]!=INF)
			{
				if(dis[p]+M->map[p][j]<dis[j])
					dis[j] = dis[p]+M->map[p][j];
			}
		}
		book[p] = 1;//表示此通过顶点松弛过了
	}
	for(int i = 0; i<M->vexnum; i++)
	{
		printf("%d ",dis[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
26
27
28
29
30
31
32
33
34
35
36
37

在这里插入图片描述

Dijkstra邻接表改进算法–单源求解最短路径–稀疏图适合这种–注:不能解决负边权–邻接表

void Dijkstra(AdjList* M)//稀疏图适合这种--注:不能解决负边权
{
	int num;
	EdgeType dis[MAXVEX];//顶点到各个顶点的距离
	int book[MAXVEX] = {0};//标记该顶点是否用于松弛过
	printf("输入需要求解的点的下标:");
	scanf("%d",&num);
	for(int i = 0; i<M->vexnum; i++)//都先初始化为INF
		dis[i] = INF;
	dis[num] = 0;//到自己初始化为0
	book[num] = 1;
	for(EdgeNode *p = M->list[num].firstedge;p;p=p->next)//遍历和目标节点相连接的顶点并且填充到dis数组中
	{
		dis[p->index] = p->weight;
	}
	while(1)
	{
		int min = INF;
		int t = -1;
		for(int i = 0;i<M->vexnum;i++) //遍历dis数组 
		{
			if(book[i]==0 && dis[i]<min)
			{
				min = dis[i];
				t = i;
			}
		}
		if(t == -1)//当t为-1说明所有连接的点都已经被用于松弛过就可以结束了
			break;
		book[t] = 1;
		
		for(EdgeNode* p = M->list[t].firstedge;p;p=p->next)//通过目前最近的点来松弛
		{
			if(dis[p->index]>dis[t]+p->weight)
			{
				dis[p->index] = dis[t]+p->weight;
			}
		}
	}
	for(int i = 0; i<M->vexnum; i++)
	{
		printf("%d ",dis[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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

Bellman_Ford算法–单源求解算法–注:可以求解负权–边集数组

void Bellman_Ford(EdgeArray* M)//单源求解算法--注:可以求解负权--边集数组 
{
	int num;
	printf("输入需要求解的顶点下标:\n");
	scanf("%d",&num);
	EdgeType dis[MAXVEX];//存求解的顶点到各顶点的距离,先初始化为INF
	for(int i = 0; i<M->vexnum; i++) 
	{
		dis[i] = INF;
	}
	dis[num] = 0;
	for(int i = 0; i<M->vexnum-1; i++)//在一个含有n个顶点的图中,任意两点之间的最短路径最多只含有n-1条边,所以只需要通过最多n-1条边来松弛
	{
		int flag = 1;//判断是否此次循环是否存在松弛,如果没有松弛说明所有松弛已经结束
		for(int j = 0; j<M->edgenum; j++)//遍历边尝试优化  即遍历所有的边B  dis[B] = min(dis[B],dis[A] + len<A,B>) 
		{
			if(dis[M->edge[j].end] > M->edge[j].weight + dis[M->edge[j].begin])
			{
				dis[M->edge[j].end] = M->edge[j].weight+dis[M->edge[j].begin];
				flag = 0;
			}
		}
		if(flag)
		{
			break;
		}
	}
	for(int i = 0; i<M->edgenum; i++)//检测负权回路--如果n-1此优化后还能再优化说明存在负权回路 
	{
		if(dis[M->edge[i].end]>M->edge[i].weight+dis[M->edge[i].begin])
		{
			printf("该图存在负权回路\n");
			break;
		}
	}
	for(int i = 0; i<M->vexnum; i++)
	{
		printf("%d ",dis[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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

拓扑排序

说明:

//AOV网: 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动间的优先关系,这样的有向图为 顶点表示活动的网
//若存在 vi-->vj 路径 则vi一定在vj前 -- 拓扑序列
/*
求解拓扑序列:使用邻接表 
1.将每个没有入度的顶点纳入栈stack.push()中
2.通过弹出栈中的顶点stack.pop()然后将此顶点加入拓扑序列数组List并且断开此顶点与其他顶点的边,并且将入度为0的其他顶点再入栈stack.push()
3.如果List中元素数目小于总顶点数,说明存在回路,否则应该全部被按顺序弹出. 
*/ 
1
2
3
4
5
6
7
8

拓扑序列中的邻接表相对于普通邻接表增加了一个入度in

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
using namespace std;
typedef int VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define ERROR 0;
#define OK 1;
#define MAXVEX 100  //最大顶点数 

typedef struct EdgeNode
{
	int index;	//节点下标
	struct EdgeNode* next;
} EdgeNode;	//边表节点

typedef struct
{
	int in;			//入度
	VexType vex;	//顶点
	EdgeNode *firstedge;	//指向第一个边节点
} VexNode; //顶点表节点

typedef struct
{
	VexNode list[MAXVEX];	//顶点表节点数组
	int vexnum,egdenum;  //顶点数和边数
} AdjList; //邻接表

void InitAdjList(AdjList* M)//初始化图
{
	printf("输入顶点数和边数:");
	scanf("%d%d",&(M->vexnum),&(M->egdenum));
	fflush(stdin);
	printf("输入顶点:");
	for(int i = 0; i<M->vexnum; i++)
	{
		scanf("%d",&(M->list[i].vex));
		M->list[i].firstedge = NULL;  //将边表制空
		M->list[i].in = 0;
	}
	fflush(stdin);
	for(int i = 0; i<M->egdenum; i++)
	{
		printf("输入边(Vi,Vj)的下标i,j:");
		int l,r;
		EdgeType w;
		scanf("%d%d",&l,&r);

		EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//头插法
		edge->index = r;//记录下标
		edge->next = M->list[l].firstedge;
		M->list[l].firstedge = edge;
		M->list[r].in++;//入度+1
	}
}
//(int *)returnList拓扑序列数组
//(int *)returnList拓扑序列的元素个数
int TopologicalSort(AdjList *M,int *returnList,int *returnSize)//拓扑排序
{
	*returnSize = 0;//记录弹出的顶点数
	stack<int> Stack;
	printf("拓扑排序为:\n");
	for(int i = 0; i<M->vexnum; i++) //先把所有入度为0的节点入栈
	{
		if(M->list[i].in==0)
		{
			Stack.push(i);
		}
	}
	while(!Stack.empty())
	{
		int num = Stack.top();//取栈顶元素
		Stack.pop();
		returnList[(*returnSize)++] = num;//保存下标
		EdgeNode* p = M->list[num].firstedge;
		while(p)//删除它连向的点,即减少该点的入度
		{
			if(--(M->list[p->index].in)==0)//如果此点入度变为0说明可以被打印就入栈
			{
				Stack.push(p->index);
			}
			p = p->next;
		}
	}
	if((*returnSize) < M->vexnum)//存在回路
	{
		(*returnSize) = 0;
		return ERROR;
	}
	return OK;
}

int main()
{
	AdjList* M = (AdjList*)malloc(sizeof(AdjList));
	InitAdjList(M);
	int List[MAXVEX];//拓扑序列数组,保存拓扑排序后数组的元素下标
	int ListSize = 0;//拓扑序列数组的大小
	if(TopologicalSort(M,List,&ListSize))
	{
		for(int i = 0; i<ListSize; i++)
		{
			printf("%d ",M->list[List[i]].vex);
		}
	}
	else
	{
		printf("此图存在回路\n");
	}
	return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

样例:

14 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 4
0 5
0 11
1 2
1 4
1 8
2 5
2 6
2 9
3 2
3 13
4 7
5 8
5 12
6 5
8 7
9 10
9 11
10 13
12 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在这里插入图片描述

效果图:

在这里插入图片描述

关键路径

//AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网称为AOE网
/*
求解关键路径:使用邻接表 
1.求解n个顶点(事件)的最早发生时间(etv)和最晚发生时间(ltv)
    etv求法:先初始化为0,对顶点进行拓扑排序,对于每个顶点的最早发生时间 etv[k] = max(etv[k],etv[i]+len<i,k>)就是每次取到此节点路径的最大值
	ltv求法:先初始化ltv为etv[n-1]即初始化为最早发生时间的最大值,从后往前遍历拓扑序列,使每个 ltv[k] = min(ltv[k],ltv[i]-len<k,i>)就是反着推看最多有多少空余时间
2.求解m个边(活动)的最早发生时间(ete)和最晚发生时间(lte) 
	ete和lte求法:早头晚尾: 最早活动时间(ete)看此边(活动)的 头顶点的最早发生时间(etv),最晚活动时间(lte)看尾顶点的最晚发生时间(ltv)
	即:遍历拓扑序列:对于顶点k的每一条边<k,i>而言: ete = etv[k] lte = ltv[i] - len<k,i>
	对于每个顶点如果ete == lte 说明这个活动的发生没有延迟可言,说明它就是关键活动,打印出来就可以. 
*/ 
1
2
3
4
5
6
7
8
9
10
11

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
using namespace std;
typedef int VexType;	//顶点的数据类型
typedef int EdgeType;	//边上的权值类型
#define ERROR 0;
#define OK 1;
#define MAXVEX 100  //最大顶点数

typedef struct EdgeNode
{
	int index;	//节点下标
	EdgeType weight;	//权值
	struct EdgeNode* next;
} EdgeNode;

typedef struct
{
	int in;			//入度
	VexType vex;
	EdgeNode* firstedge;
} VexNode;

typedef struct
{
	VexNode list[MAXVEX];
	int vexnum,edgenum;
} AdjList;

void InitAdjList(AdjList* M)
{
	printf("输入顶点数和边数:\n");
	scanf("%d%d",&(M->vexnum),&(M->edgenum));
	printf("输入顶点:\n");
	for(int i = 0; i<M->vexnum; i++)
	{
		scanf("%d",&(M->list[i].vex));
		M->list[i].firstedge = NULL;
		M->list[i].in = 0;
	}
	fflush(stdin);
	for(int i = 0; i<M->edgenum; i++)
	{
		printf("输入边(Vi,Vj)的下标i,j和权值w:");
		int l,r;
		EdgeType weight;
		scanf("%d%d%d",&l,&r,&weight);

		EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));
		edge->next = M->list[l].firstedge;
		M->list[l].firstedge = edge;
		edge->index = r;
		edge->weight = weight;
		M->list[r].in++;
	}
}

int TopologicalSort(AdjList *M,int *returnList,int *returnSize,int *etv)//拓扑排序 
{
	(*returnSize) = 0;//记录拓扑序列个数
	stack<int> Stack;
	memset(etv,0,M->vexnum*sizeof(int));
	for(int i = 0; i<M->vexnum; i++)
	{
		if(M->list[i].in == 0)
		{
			Stack.push(i);
		}
	}
	while(!Stack.empty())
	{
		int gettop = Stack.top();
		Stack.pop();
		returnList[(*returnSize)++] = gettop;
		for(EdgeNode* p = M->list[gettop].firstedge; p; p=p->next)
		{
			if(--(M->list[p->index].in) == 0)
			{
				Stack.push(p->index);
			}
			if(etv[p->index] < etv[gettop] + p->weight)//求最大
			{
				etv[p->index] = etv[gettop] + p->weight;
			}
		}
	}
	if((*returnSize) < M->vexnum)
	{
		(*returnSize) = 0;
		return ERROR;
	}
	else
	{
		return OK;
	}
}

void CriticalPath(AdjList *M)//求解关键路径
{
	int etv[MAXVEX];//事件最早开始时间
	int ltv[MAXVEX];//事件最晚开始时间
	int List[MAXVEX];//拓扑序列
	int ListSize = 0;//拓扑序列元素个数
	if(TopologicalSort(M,List,&ListSize,etv))//拓扑排序
	{
		for(int i = 0; i<ListSize; i++)
		{
			ltv[i] = etv[ListSize-1];//全部初始化为结束点的最早开始时间(最大)
		}
		for(int i = ListSize-1; i>=0; i--) //从后往前遍历拓扑序列
		{
			int gettop = List[i];
			for(EdgeNode* p = M->list[gettop].firstedge; p; p=p->next)
			{
				if(ltv[gettop] > ltv[p->index] - p->weight)//求最小
				{
					ltv[gettop] = ltv[p->index] - p->weight;
				}
			}
		}
		printf("最早事件发生时间"); 
		for(int i = 0;i<M->vexnum;i++)
		{
			printf("%d ",etv[i]);
		}
		printf("\n最晚事件发生时间"); 
		for(int i = 0;i<M->vexnum;i++)
		{
			printf("%d ",ltv[i]);
		}
		putchar('\n');
		for(int i = 0; i<ListSize; i++) //求关键活动的ete和lte 
		{
			int gettop = List[i];//拓扑序列
			for(EdgeNode* p = M->list[gettop].firstedge; p; p=p->next) //遍历边
			{
				int ete,lte;//最早活动时间和最晚活动时间
				ete = etv[gettop];//早头晚尾--最早活动时间看头事件的最早,最晚活动时间看尾事件的最晚
				lte = ltv[p->index] - p->weight;
				if(ete == lte)
				{
					printf("%d,%d length: %d\n",M->list[gettop].vex,M->list[p->index].vex,p->weight);
				}
			}
		}
	}
	else
	{
		printf("此图存在回路\n");
	}
}

int main()
{
	AdjList* M = (AdjList*)malloc(sizeof(AdjList));
	InitAdjList(M);
	CriticalPath(M);
	return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

样例:

10 13
0 1 2 3 4 5 6 7 8 9
0 1 3
0 2 4
1 3 5
1 4 6
2 3 8
2 5 7
3 4 3
4 6 9
4 7 4
5 7 6
6 9 2
7 8 5
8 9 3

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

在这里插入图片描述

效果图:
在这里插入图片描述

在这里插入图片描述

总结

这个是根据《大话数据结构》和《啊哈算法》进行总结的,这里很多图片以及数据都是出自这些书中,本人技术有限,如果您有更好的建议希望您能提出,我一定洗耳恭听

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