章节总目录点击→数据结构C代码汇总目录

五、图

1、图的两种存储结构

//图的两种存储结构
#define INF 32767				//定义∞
#define	MAXV 100				//最大顶点个数
typedef char InfoType;

//以下定义邻接矩阵类型
typedef struct
{	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型

typedef struct
{	int edges[MAXV][MAXV];		//邻接矩阵数组
	int n,e;					//顶点数，边数
	VertexType vexs[MAXV];		//存放顶点信息
} MatGraph;						//完整的图邻接矩阵类型

//以下定义邻接表类型
typedef struct ANode
{	int adjvex;					//该边的邻接点编号
	struct ANode *nextarc;		//指向下一条边的指针
	int weight;					//该边的相关信息，如权值（用整型表示）
} ArcNode;						//边结点类型

typedef struct Vnode
{	InfoType info;				//顶点其他信息
	ArcNode *firstarc;			//指向第一条边
} VNode;						//邻接表头结点类型

typedef struct 
{	VNode adjlist[MAXV];		//邻接表头结点数组
	int n,e;					//图中顶点数n和边数e
} AdjGraph;						//完整的图邻接表类型

2、图的基本运算算法

//图的基本运算算法
#include <stdio.h>
#include <malloc.h>
#include "graph.h"

//----邻接矩阵的基本运算算法----------------------------------

void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) //创建图的邻接矩阵
{
	int i,j;
	g.n=n; g.e=e;
	for (i=0;i<g.n;i++)
		for (j=0;j<g.n;j++)
			g.edges[i][j]=A[i][j];
}

void DispMat(MatGraph g)	//输出邻接矩阵g
{
	int i,j;
	for (i=0;i<g.n;i++)
	{
		for (j=0;j<g.n;j++)
			if (g.edges[i][j]!=INF)
				printf("%4d",g.edges[i][j]);
			else
				printf("%4s","∞");
		printf("\n");
	}
}

//----邻接表的基本运算算法------------------------------------

void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph *)malloc(sizeof(AdjGraph));
	for (i=0;i<n;i++)								//给邻接表中所有头结点的指针域置初值
		G->adjlist[i].firstarc=NULL;
	for (i=0;i<n;i++)								//检查邻接矩阵中每个元素
		for (j=n-1;j>=0;j--)
			if (A[i][j]!=0 && A[i][j]!=INF)			//存在一条边
			{	p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个结点p
				p->adjvex=j;
				p->weight=A[i][j];
				p->nextarc=G->adjlist[i].firstarc;	//采用头插法插入结点p
				G->adjlist[i].firstarc=p;
			}
	G->n=n; G->e=n;
}

void DispAdj(AdjGraph *G)	//输出邻接表G
{
	int i;
	ArcNode *p;
	for (i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("%3d: ",i);
		while (p!=NULL)
		{
			printf("%3d[%d]→",p->adjvex,p->weight);
			p=p->nextarc;
		}
		printf("∧\n");
	}
}

void DestroyAdj(AdjGraph *&G)		//销毁图的邻接表
{	int i;
	ArcNode *pre,*p;
	for (i=0;i<G->n;i++)			//扫描所有的单链表
	{	pre=G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
		if (pre!=NULL)
		{	p=pre->nextarc;
			while (p!=NULL)			//释放第i个单链表的所有边结点
			{	free(pre);
				pre=p; p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);						//释放头结点数组
}

3、图的遍历算法 

【1】广度优先遍历算法（BFS）

//广度优先遍历算法
#include "graph.cpp"
#include<string.h>
#define MaxSize 100

//--广度优先遍历中使用队列的基本运算算法-------------------

typedef int ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;		//队首和队尾指针
} SqQueue;

void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}

void DestroyQueue(SqQueue *&q)
{
	free(q);
}

bool QueueEmpty(SqQueue *q)
{
	return(q->front==q->rear);
}

bool enQueue(SqQueue *&q,ElemType e)
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
		return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}

bool deQueue(SqQueue *&q,ElemType &e)
{	if (q->front==q->rear)				//队空下溢出
		return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}

void BFS(AdjGraph *G,int v)  				//基本BFS 
{
	int w,i;
	ArcNode *p;
	SqQueue *qu;							//定义环形队列指针
	InitQueue(qu);							//初始化队列
	int visited[MAXV];            			//定义顶点访问标志数组
	memset(visited,0,sizeof(visited));		//访问标志数组初始化
	printf("%2d",v); 						//输出被访问顶点的编号
	visited[v]=1;              				//置已访问标记
	enQueue(qu,v);
	while (!QueueEmpty(qu))       			//队不空循环
	{	
		deQueue(qu,v);						//出队一个顶点v
		p=G->adjlist[v].firstarc; 			//指向v的第一个邻接点
		while (p!=NULL)						//找顶点v的所有邻接点w
		{
			int w=p->adjvex;	
			if (visited[w]==0) 				//若顶点w未访问过 
			{
				printf("%2d",w);  			//访问顶点w
				visited[w]=1;				//置已访问标记
				enQueue(qu,w);				//顶点w进队
           	}
           	p=p->nextarc;              		//找下一个邻接点
		}
	}
	printf("\n");
	DestroyQueue(qu);						//销毁队列 
}

int main()
{
	AdjGraph *G;
	int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
			{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
	int n=5, e=8;
	CreateAdj(G,A,n,e);			//建立《教程》中图8.1(a)的邻接表
	printf("图G的邻接表:\n");
	DispAdj(G);					//输出邻接表G
	printf("广度优先序列:");BFS(G,2);printf("\n");
	DestroyAdj(G);				//销毁邻接表
	return 1;
}

【2】深度优先遍历算法（DFS）

//深度优先遍历算法
#include "graph.cpp"
int visited[MAXV]={0};

void DFS(AdjGraph *G,int v)  
{
	ArcNode *p;
	visited[v]=1;                   //置已访问标记
	printf("%d  ",v); 				//输出被访问顶点的编号
	p=G->adjlist[v].firstarc;      	//p指向顶点v的第一条弧的弧头结点
	while (p!=NULL) 
	{
		if (visited[p->adjvex]==0)	//若p->adjvex顶点未访问,递归访问它
			DFS(G,p->adjvex);    
		p=p->nextarc;              	//p指向顶点v的下一条弧的弧头结点
	}
}

int main()
{
	AdjGraph *G;
	int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
			{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
	int n=5, e=8;
	CreateAdj(G,A,n,e);			//建立邻接表
	printf("图G的邻接表:\n");
	DispAdj(G);					//输出邻接表G
	printf("深度优先序列(递归):");DFS(G,2);printf("\n");
	DestroyAdj(G);				//销毁邻接表
	return 1;
}

4、最短路径问题

【1】Dijkstra算法

//Dijkstra算法
#include "graph.cpp"
void Dispath(MatGraph g,int dist[],int path[],int S[],int v)
//输出从顶点v出发的所有最短路径
{	int i,j,k;
	int apath[MAXV],d;					//存放一条最短路径(逆向)及其顶点个数
	for (i=0;i<g.n;i++)					//循环输出从顶点v到i的路径
		if (S[i]==1 && i!=v)
		{	printf("  从顶点%d到顶点%d的路径长度为:%d\t路径为:",v,i,dist[i]);
			d=0; apath[d]=i;			//添加路径上的终点
			k=path[i];
			if (k==-1)					//没有路径的情况
				printf("无路径\n");
			else						//存在路径时输出该路径
			{	while (k!=v)
				{	d++; apath[d]=k;
					k=path[k];
				}
				d++; apath[d]=v;		//添加路径上的起点
				printf("%d",apath[d]);	//先输出起点
				for (j=d-1;j>=0;j--)	//再输出其他顶点
					printf(",%d",apath[j]);
				printf("\n");
			}
		}
}

void Dijkstra(MatGraph g,int v)	//Dijkstra算法
{	int dist[MAXV],path[MAXV];
	int S[MAXV];				//S[i]=1表示顶点i在S中, S[i]=0表示顶点i在U中
	int mindist,i,j,u;
	for (i=0;i<g.n;i++)
	{	dist[i]=g.edges[v][i];	//距离初始化
		S[i]=0;					//S[]置空
		if (g.edges[v][i]<INF)	//路径初始化
			path[i]=v;			//顶点v到顶点i有边时，置顶点i的前一个顶点为v
		else
			path[i]=-1;			//顶点v到顶点i没边时，置顶点i的前一个顶点为-1
	}
	S[v]=1;path[v]=0;			//源点编号v放入S中
	for (i=0;i<g.n-1;i++)		//循环直到所有顶点的最短路径都求出
	{	mindist=INF;				//mindist置最大长度初值
		for (j=0;j<g.n;j++)		//选取不在S中（即U中）且具有最小最短路径长度的顶点u
			if (S[j]==0 && dist[j]<mindist) 
			{	u=j;
				mindist=dist[j];
			}
		S[u]=1;					//顶点u加入S中
		for (j=0;j<g.n;j++)		//修改不在S中（即U中）的顶点的最短路径
			if (S[j]==0)
				if (g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
				{	dist[j]=dist[u]+g.edges[u][j];
					path[j]=u;
				}
	}
	Dispath(g,dist,path,S,v);	//输出最短路径
}

int main()
{
	MatGraph g;
	int A[MAXV][MAXV]={
		{0,4,6,6,INF,INF,INF},
		{INF,0,1,INF,7,INF,INF},
		{INF,INF,0,INF,6,4,INF},
		{INF,INF,2,0,INF,5,INF},
		{INF,INF,INF,INF,0,INF,6},
		{INF,INF,INF,INF,1,0,8},
		{INF,INF,INF,INF,INF,INF,0}};
	int n=7, e=12;
	CreateMat(g,A,n,e);			//建立《教程》中图8.35的邻接矩阵
	printf("图G的邻接矩阵:\n");
	DispMat(g);					//输出邻接矩阵
	int v=0;
	printf("从%d顶点出发的最短路径如下:\n",v);
	Dijkstra(g,v);
	return 1;
}

【2】Floyd算法

//Floyd算法
#include "graph.cpp"

void Dispath(MatGraph g,int A[][MAXV],int path[][MAXV])
{	int i,j,k,s;
	int apath[MAXV],d;		//存放一条最短路径中间顶点(反向)及其顶点个数
	for (i=0;i<g.n;i++)
		for (j=0;j<g.n;j++)
		{	if (A[i][j]!=INF && i!=j)			//若顶点i和j之间存在路径
			{	printf("  从%d到%d的路径为:",i,j);
				k=path[i][j];
				d=0; apath[d]=j;				//路径上添加终点
				while (k!=-1 && k!=i)			//路径上添加中间点
				{	d++; apath[d]=k;
					k=path[i][k];
				}
				d++; apath[d]=i;				//路径上添加起点
				printf("%d",apath[d]);			//输出起点
				for (s=d-1;s>=0;s--)			//输出路径上的中间顶点
					printf(",%d",apath[s]);
				printf("\t路径长度为:%d\n",A[i][j]);
			}
		}
}

void Floyd(MatGraph g)							//Floyd算法
{	int A[MAXV][MAXV],path[MAXV][MAXV];
	int i,j,k;
	for (i=0;i<g.n;i++)
		for (j=0;j<g.n;j++) 
		{	A[i][j]=g.edges[i][j];
			if (i!=j && g.edges[i][j]<INF)
				path[i][j]=i;					//顶点i到j有边时
			else
				path[i][j]=-1;				//顶点i到j没有边时
		}
	for (k=0;k<g.n;k++)						//依次考察所有顶点
	{	for (i=0;i<g.n;i++)
			for (j=0;j<g.n;j++)
				if (A[i][j]>A[i][k]+A[k][j])
				{	A[i][j]=A[i][k]+A[k][j];	//修改最短路径长度
					path[i][j]=path[k][j];		//修改最短路径
				}
	}
	Dispath(g,A,path);							//输出最短路径
}

/*
int main()
{
	MatGraph g;
	int A[MAXV][MAXV]={
		{0,  5,INF,7},
		{INF,0,  4,2},
		{3,  3,  0,2},
		{INF,INF,1,0}};
	int n=4, e=8;
	CreateMat(g,A,n,e);			//建立《教程》中图8.41的邻接矩阵
	printf("图G的邻接矩阵:\n");
	DispMat(g);					//输出邻接矩阵
	printf("各顶点对的最短路径:\n");
	Floyd(g);
	return 1;
}
*/

int main()
{
	MatGraph g;
	int A[MAXV][MAXV]={
		{0,  6, INF,INF,2},
		{INF,0, INF,INF,INF},
		{INF,1, 0,  3,  INF},
		{2,  INF,INF,0, INF},
		{INF,3,  1,  3, 0}
	};
	int n=5, e=8;
	CreateMat(g,A,n,e);			//建立图的邻接矩阵
	printf("图G的邻接矩阵:\n");
	DispMat(g);					//输出邻接矩阵
	printf("各顶点对的最短路径:\n");
	Floyd(g);
	return 1;
}

5、求关键路径

//求关键路径算法
#include "graph.cpp"
typedef struct
{	int ino;			//起点
	int eno;			//终点
} KeyNode;				//关键活动类型

bool TopSort(AdjGraph *G,int topseq[])
//产生含有n个顶点编号的拓扑序列topseq
{
	int i,j,n=0;
	int st[MAXV];						//定义一个顺序栈
	int top=-1;							//栈顶指针为top
	ArcNode *p;
	for (i=0;i<G->n;i++)				//所有顶点的入度置初值0
		G->adjlist[i].count=0;
	for (i=0;i<G->n;i++)				//求所有顶点的入度
	{	p=G->adjlist[i].firstarc;
		while (p!=NULL)
		{	G->adjlist[p->adjvex].count++;
			p=p->nextarc;
		}
	}
	for (i=0;i<G->n;i++)
		if (G->adjlist[i].count==0)		//入度为0的顶点进栈
		{	top++;
			st[top]=i;
		}
	while (top>-1)						//栈不为空时循环
	{	i=st[top];top--;				//出栈
		topseq[n]=i; n++;
		p=G->adjlist[i].firstarc;		//找第一个邻接点
		while (p!=NULL)
		{	j=p->adjvex;
			G->adjlist[j].count--;
			if (G->adjlist[j].count==0)	//入度为0的相邻顶点进栈
			{	top++;
				st[top]=j;
			}
			p=p->nextarc;				//找下一个邻接点
		}
	}
	if (n<G->n)					//拓扑序列中不含所有顶点时
		return false;
	else
	{
		printf("拓扑序列:");
		for (i=0;i<n;i++)
			printf("%c ",(char)(topseq[i]+'A')); 
		printf("\n");
		return true;
	}
}

bool KeyPath(AdjGraph *G,int &inode,int &enode,KeyNode keynode[],int &d)
//从图邻接表G中求出从源点inode到汇点enode的关键活动keynode[0..d]
{	int topseq[MAXV];						//topseq用于存放拓扑序列
	int i,w;
	ArcNode *p;
	if (!TopSort(G,topseq))
		return false;						//不能产生拓扑序列时返回false
	inode=topseq[0];						//求出源点
	enode=topseq[G->n-1];					//求出汇点
	int ve[MAXV];							//事件的最早开始时间
	int vl[MAXV];							//事件的最迟开始时间
	for (i=0;i<G->n;i++) ve[i]=0;			//先将所有事件的ve置初值为0
	for (i=0;i<G->n;i++)					//从左向右求所有事件的最早开始时间
	{	p=G->adjlist[i].firstarc;
		while (p!=NULL)						//遍历每一条边即活动
		{	w=p->adjvex;
			if (ve[i]+p->weight>ve[w])		//求最大者
				ve[w]=ve[i]+p->weight;
			p=p->nextarc;
		}
	 }
	for (i=0;i<G->n;i++)					//先将所有事件的vl值置为最大值
		vl[i]=ve[enode];
	for (i=G->n-2;i>=0;i--)					//从右向左求所有事件的最迟开始时间
	{	p=G->adjlist[i].firstarc;
		while (p!=NULL)
		{	w=p->adjvex;
			if (vl[w]-p->weight<vl[i])		//求最小者
				vl[i]=vl[w]-p->weight; 
			p=p->nextarc;
		}
	}
	d=-1;									//d存放keynode中的关键活动下标,置初置为-1
	for (i=0;i<G->n;i++)					//求关键活动
	{	p=G->adjlist[i].firstarc;
		while (p!=NULL)
		{	w=p->adjvex;
			if (ve[i]==vl[w]-p->weight)		//(i→w)是一个关键活动
			{
				d++; keynode[d].ino=i; keynode[d].eno=w;
			}
			p=p->nextarc;
		}
	}
	return true;
}

void DispKeynode(AdjGraph *G)
{
	int inode,enode,d,i;
	KeyNode keynode[MAXV];
	if (KeyPath(G,inode,enode,keynode,d))
	{
		printf("从源点%c到汇点%c的关键活动:",char(inode='A'),char(enode+'A'));
		for (i=0;i<=d;i++)
			printf("(%c,%c)  ",char(keynode[i].ino+'A'),char(keynode[i].eno+'A'));
		printf("\n");
	}
	else printf("不能求关键活动\n");
}

int main()
{
	AdjGraph *G;
	int n=9,e=11;
	int A[MAXV][MAXV]={
		{ 0,  6,  4,  5 ,INF,INF,INF,INF,INF},
		{INF, 0, INF,INF, 1 ,INF,INF,INF,INF},
		{INF,INF, 0 ,INF, 1 ,INF,INF,INF,INF},
		{INF,INF,INF, 0 ,INF,INF,INF, 2 ,INF},
		{INF,INF,INF,INF, 0 , 9 , 7 ,INF,INF},
		{INF,INF,INF,INF,INF, 0 ,INF,INF, 2 },
		{INF,INF,INF,INF,INF,INF, 0 ,INF, 4 },
		{INF,INF,INF,INF,INF,INF,INF, 0 , 4 },
		{INF,INF,INF,INF,INF,INF,INF,INF, 0 }};
	printf("建立图的邻接表:\n");
	CreateAdj(G,A,n,e);							//创建图8.45的邻接表
	printf("图G的邻接表:\n"); DispAdj(G);
	DispKeynode(G);								//求构成关键路径的关键活动
	DestroyAdj(G);								//销毁图
	return 1;
}

本章结束，下一章是查找，点击→第六章 查找~

# 数据结构 # c语言 # 图论 # 考研 # 深度优先 # 算法
Logo
乐奇 Rokid 开放社区

更多推荐

cover

国庆文旅安保上新！AR智能眼镜守护景区，黑科技护航假期出游

avatar 乐奇 Rokid 开放社区
cover

2027中国深圳智能穿戴产业链展览会

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区