《数据结构教程(李春葆主编 第五版)》第八章源代码—图(Part I)

图的基本运算算法(graph.cpp)

#include <stdio.h>
#include <malloc.h>
//图的两种存储结构
#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;				//顶点其他信息
	int count;					//存放顶点入度,仅仅用于拓扑排序
	ArcNode *firstarc;			//指向第一条边
} VNode;						//邻接表头结点类型
typedef struct 
{	VNode adjlist[MAXV];		//邻接表头结点数组
	int n,e;					//图中顶点数n和边数e
} AdjGraph;						//完整的图邻接表类型

//----邻接矩阵的基本运算算法----------------------------------
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);						//释放头结点数组
}

广度优先遍历算法

//广度优先遍历算法
#include "graph.cpp"
#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)  
{
	int w,i;
	ArcNode *p;
	SqQueue *qu;							//定义环形队列指针
	InitQueue(qu);							//初始化队列
	int visited[MAXV];            			//定义顶点访问标志数组
	for (i=0;i<G->n;i++) visited[i]=0;		//访问标志数组初始化
	printf("%2d",v); 						//输出被访问顶点的编号
	visited[v]=1;              				//置已访问标记
	enQueue(qu,v);
	while (!QueueEmpty(qu))       			//队不空循环
	{	
		deQueue(qu,w);						//出队一个顶点w
		p=G->adjlist[w].firstarc; 			//指向w的第一个邻接点
		while (p!=NULL)						//查找w的所有邻接点
		{	
			if (visited[p->adjvex]==0) 		//若当前邻接点未被访问
			{
				printf("%2d",p->adjvex);  	//访问该邻接点
				visited[p->adjvex]=1;		//置已访问标记
				enQueue(qu,p->adjvex);		//该顶点进队
           	}
           	p=p->nextarc;              		//找下一个邻接点
		}
	}
	printf("\n");
}

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;
}

深度优先遍历算法

#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);			//建立《教程》中图8.1(a)的邻接表
	printf("图G的邻接表:\n");
	DispAdj(G);					//输出邻接表G
	printf("深度优先序列(递归):");DFS(G,2);printf("\n");
	DestroyAdj(G);				//销毁邻接表
	return 1;
}

判断从顶点v出发能否找到环

#include "graph.cpp"
int visited[MAXV];					//全局变量
void hasCycle(AdjGraph *G,int v,bool &has)
//判断从顶点v出发能否找到环
{
	ArcNode *p;
	int w;
	visited[v]=1;				//置已访问标记
	p=G->adjlist[v].firstarc;	//p指向顶点v的第一个邻接点
	while (p!=NULL)
	{	w=p->adjvex;
		if (visited[w]==0)		//若顶点w未访问,递归访问它
			hasCycle(G,w,has);
		else					//又找到了已访问过的顶点说明有回路
			has=true;
		p=p->nextarc;			//找下一个邻接点
	}
	visited[v]=0;
}

bool Cycle(AdjGraph *G)         //判断有向图G中是否存在环
{
	bool has=false;
	for (int i=0;i<G->n;i++)
	{
		hasCycle(G,i,has);
		if (has) return true;
	}
	return false;
}

int main()
{ 
/*	int n=7, e=12;
	int A[MAXV][MAXV]={
		{0,  2,  5,  3,  INF,INF,INF},
		{INF,0,  2,  INF,INF,8,  INF},
		{INF,INF,0,  1,  3,  5,  INF},
		{INF,INF,INF,0,  5,  INF,INF},
		{INF,INF,INF,INF,0,  3,  9},
		{INF,INF,INF,INF,INF,0,  5},
		{INF,INF,INF,INF,INF,INF,0}
	};	
*/

	int n=4, e=4;
	int A[MAXV][MAXV]={
		{0,  1,  1,INF},
		{INF, 0, INF,INF},
		{INF,1,    0,1},
		{INF,INF,INF,0}

	};	

	AdjGraph *G;
	CreateAdj(G,A,n,e);			建立图8.19的邻接表
	for (int i=0;i<n;i++) 		//visited数组置初值
		visited[i]=0;
	printf("图G:\n");DispAdj(G);//输出邻接表
	bool has=false;
	printf("has=%d\n",Cycle(G));
	DestroyAdj(G);				//销毁邻接表
	return 1;
}

Prim(普利姆)算法

#include "graph.cpp"
void Prim(MatGraph g,int v)
{
	int lowcost[MAXV];			//顶点i是否在U中
	int min;
	int closest[MAXV],i,j,k;
	for (i=0;i<g.n;i++)          //给lowcost[]和closest[]置初值
	{	
		lowcost[i]=g.edges[v][i];
		closest[i]=v;
	}
	for (i=1;i<g.n;i++)          //找出n-1个顶点
	{
		min=INF;
		for (j=0;j<g.n;j++)       //在(V-U)中找出离U最近的顶点k
			if (lowcost[j]!=0 && lowcost[j]<min) 
			{
				min=lowcost[j];
				k=j;			//k记录最近顶点的编号
			}
		printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
		lowcost[k]=0;         	//标记k已经加入U
		for (j=0;j<g.n;j++)   	//修改数组lowcost和closest
			if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j]) 
			{
				lowcost[j]=g.edges[k][j];
				closest[j]=k; 
			}
	}
}

int main()
{
	MatGraph g;
	int A[MAXV][MAXV]={
		{0,28,INF,INF,INF,10,INF},
		{28,0,16,INF,INF,INF,14},
		{INF,16,0,12,INF,INF,INF},
		{INF,INF,12,0,22,INF,18},
		{INF,INF,INF,22,0,25,24},
		{10,INF,INF,INF,25,0,INF},
		{INF,14,INF,18,24,INF,0}};
	int n=7, e=9;
	CreateMat(g,A,n,e);			//建立《教程》中图8.27的邻接矩阵
	printf("图G的邻接矩阵:\n");
	DispMat(g);					//输出邻接矩阵
	int v=0;
	printf("Prim算法结果(起始点为%d)\n",v);
	Prim(g,v);
	return 1;
}

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;
}

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数&#xff1a; gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点&#xff1a; 完后运行&#xff0c;r gdb 中的有用命令 下面是一个有用的 gdb 命令子集&#xff0c;按可能需要的顺序大致列出。 第一列给出了命令&#xff0c;可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布&#xff1a; 一元高斯分布&#xff1a;(将多元高斯分布中的D取值1&#xff09; 其中代表的是平均值&#xff0c;是方差的平方&#xff0c;也可以用来表示&#xff0c;是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要&#xff0c;需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容&#xff0c;经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch &#xff0c;简称ES 。是一个全文搜索服务器&#xff0c;也可以作为NoSQL 数据库&#xff0c;存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项&#xff1a; (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候&#xff0c;访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议&#xff1a;以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么&#xff1f; 在java规范中是这样描述的&#xff1a;Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联&#xff0c;线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统&#xff0c;该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口&#xff0c;远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能&#xff0c;出了大概一年了。 程序员们在编程时遇到不会的问题&#xff0c;又没有老师可以提问&#xff0c;就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法&#xff0c;但是不一定得到回复&#xff0c;…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎&#xff0c;题目很狗&#xff0c;第一次踩这个坑&#xff0c;单拉出来写个题解记录一下 题意&#xff1a;给一个数字矩阵&#xff0c;一次操作&#xff1a;对于每一行&#xff0c;可以去掉左端或者右端的数&#xff0c;得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1&#xff09;全特化2&#xff09;偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类&#xff1a; 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…