利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

这篇具有很好参考价值的文章主要介绍了利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

    --------------------------------------目录------------------------------------------

图的定义和术语

图的邻接矩阵构建法

  深度优先遍历算法(DFS)

  广度优先遍历算法 (BFS)

全部代码


图的定义和术语

        图:G = (V,E) V:顶点的有穷非空集合 E:边的有穷集合

        无向图:每条边都是无向的

        有向图:每条边都是有方向的

        邻接:有边相连的两个顶点之间的关系

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

图的邻接矩阵构建法

        想要构建图,则首先得知道图的存储结构,从上图可以看出,我们需要有个数组存储各个顶点的数据,如v1、v2、v3等等。。再者因为我们今天要用邻接矩阵来表示图,所以我们需要个二维数组,再为了方便,我们需要再设两个变量,表示现有的结点与边,可以不难看出是个结构体结构,如下图:

#define MVNUM 100					//最大顶点数

typedef struct
{
	char vexs[MVNUM];				//顶点数据数组
	int arr[MVNUM][MVNUM];			//邻接矩阵
	int vexnum, arcnum;				//现有顶点数与边数
}AMGraph;	

        假设我们现在顶点数为5个,边数为5,顶点数据为 a,b,c,d,e,矩阵元素都为无穷,并定义个结构体变量则结构表示出来为:

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

         存储结构知道后,我们就可以对它进行初始化操作啦,而我们的初始化操作,就是对照上图,其中数字,数据都是随机的,根据你的喜好,并且你还可以美化它,这里不多赘述,下面为思想:

        1、确定顶点数和边数,

        2、给顶点表赋值

        3、arr二维数组都初始化为极大值(这里的极大值一般为int的最大值32767,而上图为了美观写成∞)表示现在每个顶点之间都没有线(关系),我们接下来构造就是加线操作而已。

#define MAXINT 32767				//极大值相当于无穷大

int initGraph(AMGraph& G)
{
	cout << "please input some vexnum and arcnum!" << endl;
	cin >> G.vexnum >> G.arcnum;		//输入你想要的顶点数和边数
	cout << "please input data of vex!" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >>G.vexs[i];				//输入顶点数据
	}
	
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arr[i][j] = MAXINT;		//邻接矩阵的初值都为无穷大
		}	
	}
		
	return 1;
}

        初始化完成后,我们就可以,看看自己邻接矩阵长什么样啦,写一个遍历二维数组的算法(比较简单,这里就不写了),而后就是构造顶点之间的联系,思想就是:

        1、先输入两个点(这两个点是邻接的,就是有关系的),并赋予权值,

        2、用这两个点去顶点表里去找,找到了返回对应坐标

        3、找到坐标后就在矩阵(二维数组)对应下标赋值

        4、因为为无向图,则为对称的,所以行列坐标对换后再赋值一遍即可(如为有向图这步省略)

int locateVex(AMGraph G, char u)
{
	for (int i = 0; i < G.vexnum; i++)	
	{
		if (u == G.vexs[i])		//如果u的值和顶点数据匹配,就返回顶点在矩阵中的下标
			return i;
	}
	return -1;
}

int createGraph(AMGraph& G)
{
	int i = 0; int j = 0;int w = 0;		//i,j代表顶点下标,w代表权值
	char v1 = 0; char v2 = 0;			//v1,v2为顶点数据
	cout << "please input w of v1 to v2 in graph!" << endl;
	for (int k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2 >> w;			
		i = locateVex(G, v1);           //找到v1在顶点表的下标,并返回赋值给i
		j = locateVex(G, v2);           //找到v2在顶点表的下标,并返回赋值给j
		G.arr[i][j] = w;
		G.arr[j][i] = G.arr[i][j];		//无向图的矩阵是对称矩阵
	}

	cout << endl;
	return 1;
}

        假设我们现在按照 下面这个图来构建邻接矩阵,则结果为:

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

         深度优先遍历算法(DFS)

         深度优先算法就是一条路走到黑,走不下去就回来换条路的人性化算法,也是我这种路痴的常用探路的方法。

        1、即随机选个顶点,

        2、顺着与它有联系的点走下去,发现走不下去了,就回退一个顶点

        3、如此如此最后再回退到当初选的第一个点

       从步骤看出我们只是要去下一个顶点,然后用相同的方法再去下一个顶点,则我们可以用递归算法,可以用栈写出来(非递归),也可以用本来有的栈来做(递归)

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

        走不下去了,退一格,再去没访问过的顶点,访问过的点不访问。

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

         依次下去,直至最后一个点都访问了,然后顺着原路返回。

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

         实现代码则需要一个辅助数组,这个数组作用是表示这个顶点是否被访问过了没,这里我们用0代表没访问过1反之,既然是递归,我们要有个递归的结束条件,可以不难看出走不下去即为结束条件,这时会有两种情况,一是没有邻接的顶点了,或者是邻接的顶点已经访问过了,那我们根据这个特性就不难写出代码了。

        1、随机选个顶点

        2、打印这个顶点,并设置为访问过了

        3、如果还有邻接的顶点并且未访问过,递归函数

int visited[MVNUM] = { 0 };     //辅助数组

void dfsAM(AMGraph G, int i)
{//随机选一个顶点下标,这里为0
	cout << G.vexs[i]<<" ";		//输出0下标在顶点表的值	
	visited[i] = 1;				//辅助数组对应下标i的值置为1
	for (int j = 0; j < G.vexnum; j++)
	{
		if (G.arr[i][j] != MAXINT && (!visited[j]))	//只要是邻接的顶点并且没有访问过
		{											//不然就退回,也是递归结束条件
			dfsAM(G, j);							//递归使用函数
        }
	}
}

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)  

广度优先遍历算法 (BFS)

         广度优先遍历也是先随机选个点,先让这个点的所有邻接点都访问一遍,然后从第一个访问的点再去访问它所有的邻接点,依次下去,到最后一个点都访问过为至。

 利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

        那我们要怎么实现这个算法呢,从第二个图那个矩阵内部图结果可以看出,如果我们要使用广度优先遍历的话,救得一次性把第0行的所有邻接点都访问一遍,然后就是第1行,依次下去,那就是说我们就让这些行数排排队,只要每个行都能把邻接点都访问一遍就可以啦。

        顺着这个思想,我们就要去想那怎么知道这一行的邻接点呢,答案是我们应该写个函数,去获取第一个邻接点的坐标,然后再写个函数得到下一个邻接点的坐标,直到没有邻接点了,那我们就去访问下一行,那我们怎么去访问下一行呢,上面讲到了排队,所以我们就可以写一个队列,让现在访问的行入队,因为我们知道这个矩阵是个方阵所以行和列是对应的,就是顶点数据对应的行坐标就是顶点数据的列坐标。

        举个例子,现在是访问0行的1列那对应的就是顶点数据b这个元素,那我们就把b在矩阵中对应的列下标入列,虽然这是列下标,但是实际上也是数据b在矩阵中对应的行下标,所以我们出队的时候其实就是访问b在矩阵中对应的行下标。

        算法步骤:

        1、输出随机访问的顶点数据,并让其对应的辅助数组下标置为1

        2、让顶点下标入队

        3、 队不为空,出队,并把出队元素保存

        4、访问第一个邻接点,并打印其顶点数据,然后让其对应的辅助数组下标置为1

        5、入队,访问下一邻接点,如此反复直至队空

void bfsAM(AMGraph G, int i)
{//随机选一个顶点下标,这里为0
	cout << G.vexs[i] << " ";		//输出i下标在顶点表的值	
	visit[i] = 1;				//辅助数值对应下标i的值置为1
	sqQueue Q;					
	initQueue(Q);
	enQueue(Q, i);				//i为矩阵中顶点的行下标,让它入队(顶点表的下标和矩阵的列下标,行下标一致,本算法中说谁的下标都一样)
	while (Q.rear != Q.front)		//队不为空
	{
		int u = 0;			//接收矩阵中顶点的行下标,因为是邻接矩阵
		deQueue(Q,u);			//出队并让u接收矩阵中顶点的行下标
		for (int w = firstVEX(G, u); w != MAXINT; w = nextVEX(G, w, u))
		{//注意在一次循环中u不变
			if (!visit[w])
			{
				cout << G.vexs[w] << " ";
				visit[w] = 1;
				enQueue(Q, w);
			}
		}
	}
	
}

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#define MVNUM 100				//最大顶点数
#define MAXINT 32767				//极大值相当于无穷大

int visited[MVNUM] = { 0 };			//辅助数组,判断遍历过了没
int visit[MVNUM] = { 0 };			//同理
typedef struct
{
	char vexs[MVNUM];			//顶点数据数组
	int arr[MVNUM][MVNUM];			//邻接矩阵
	int vexnum, arcnum;			//现有顶点数与边数
}AMGraph;							
typedef struct
{
	int* base;				//队列数组
	int front;				//队头的下标
	int rear;				//队尾的下标
}sqQueue;

int initGraph(AMGraph& G);			//初始化邻接矩阵
void showGraph(AMGraph G);			//打印邻接矩阵
int locatVex(AMGraph G, char u);		//定位顶点在邻接矩阵的下标
int createGraph(AMGraph& G);			//建立邻接矩阵
void dfsAM(AMGraph G,int i);			//深度优先搜索遍历
void bfsAM(AMGraph G, int i);			//广度优先搜索遍历
int initQueue(sqQueue& Q);			//初始化队列
int enQueue(sqQueue& Q, int i);			//入队
int firstVEX(AMGraph G, int u);			//第一个邻接顶点		
int nextVEX(AMGraph G,int w ,int u);	//下一个邻接顶点

int main()
{
	AMGraph G;							
	initGraph(G);
	createGraph(G);
	showGraph(G);
	cout << "the result of dfs is:";
	dfsAM(G,0);
	cout << endl;
	cout << "the result of bfs is:";
	bfsAM(G,0);
}
int initGraph(AMGraph& G)
{
	cout << "please input some vexnum and arcnum!" << endl;
	cin >> G.vexnum >> G.arcnum;			//输入你想要的顶点数和边数
	cout << "please input data of vex!" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >>G.vexs[i];			//输入顶点数据
	}
	
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arr[i][j] = MAXINT;		//邻接矩阵的初值都为无穷大
		}	
	}
		
	return 1;
}
void showGraph(AMGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.arr[i][j] == MAXINT)	//无穷大弄得更好看点
				cout << "∞" << " ";
			else
				cout << " " << G.arr[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int locateVex(AMGraph G, char u)
{
	for (int i = 0; i < G.vexnum; i++)	
	{
		if (u == G.vexs[i])			//如果u的值和顶点数据匹配,就返回顶点在矩阵中的下标
			return i;
	}
	return -1;
}

int createGraph(AMGraph& G)
{
	int i = 0; int j = 0;int w = 0;			//i,j代表顶点下标,w代表权值
	char v1 = 0; char v2 = 0;			//v1,v2为顶点数据
	cout << "please input w of v1 to v2 in graph!" << endl;
	for (int k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2 >> w;			
		i = locateVex(G, v1);			//找到v1在顶点表的下标,并返回赋值给i
		j = locateVex(G, v2);
		G.arr[i][j] = w;
		G.arr[j][i] = G.arr[i][j];		//无向图的矩阵是对称矩阵
	}

	cout << endl;
	return 1;
}

void dfsAM(AMGraph G, int i)
{//随机选一个顶点下标,这里为0
	cout << G.vexs[i]<<" ";			//输出0下标在顶点表的值	
	visited[i] = 1;				//辅助数组对应下标i的值置为1
	for (int j = 0; j < G.vexnum; j++)
	{
		if (G.arr[i][j] != MAXINT && (!visited[j]))	//只要是邻接的顶点并且没有访问过
		{						//不然就退回,也是递归结束条件
			dfsAM(G, j);				//递归使用函数
		}
	}
}
int initQueue(sqQueue& Q)
{
	Q.base = (int *)malloc(sizeof(int) * MVNUM);	
	//给base动态分配一个int*类型MVNUM个int大小的一维数组空间
	Q.front = Q.rear = 0;	//队头和对尾下标都置为0
	return 1;
}
int enQueue(sqQueue& Q, int i)
{
	if ((Q.rear + 1) % MVNUM == Q.front)			//队满
		return 0;
	Q.base[Q.rear] = i;					//先赋值再加
	Q.rear = (Q.rear + 1) % MVNUM;
	return 1;
}

int deQueue(sqQueue& Q, int &u)
{
	if (Q.rear == Q.front)					//队空
		return 0;
	u = Q.base[Q.front];					//要删的值给u然后再加
	Q.front = (Q.front + 1) % MVNUM;
	return 1;
}

int firstVEX(AMGraph G, int u)
{//在邻接矩阵u行0列开始遍历,如果找到不等于无穷的,
//并且没有访问过的就返回列的下标,否则就返回无穷
	for (int i = 0; i < G.vexnum; i++)		
	{
		if (G.arr[u][i] != MAXINT && visit[i] == 0) 
		{
			return i;
		}
	}
	return MAXINT;
}

int nextVEX(AMGraph G, int w, int u)
{//在邻接矩阵u行w+1列开始遍历,如果找到不等于无穷的,
//并且没有访问过的就返回列的下标,否则就返回无穷
	for (int i = w + 1; i < G.vexnum; i++)
	{
		if (G.arr[u][i] != MAXINT && visit[i] == 0)
		{
			return i;
		}	
	}
	return MAXINT;
}

void bfsAM(AMGraph G, int i)
{//随机选一个顶点下标,这里为0
	cout << G.vexs[i] << " ";		//输出i下标在顶点表的值	
	visit[i] = 1;				//辅助数值对应下标i的值置为1
	sqQueue Q;					
	initQueue(Q);
	enQueue(Q, i);				//i为矩阵中顶点的行下标,让它入队(顶点表的下标和矩阵的列下标,行下标一致,本算法中说谁的下标都一样)
	while (Q.rear != Q.front)		//队不为空
	{
		int u = 0;			//接收矩阵中顶点的行下标,因为是邻接矩阵
		deQueue(Q,u);			//出队并让u接收矩阵中顶点的行下标
		for (int w = firstVEX(G, u); w != MAXINT; w = nextVEX(G, w, u))
		{//注意在一次循环中u不变
			if (!visit[w])
			{
				cout << G.vexs[w] << " ";
				visit[w] = 1;
				enQueue(Q, w);
			}
		}
	}
	
}

利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

       发这个也是为了理清自己的思路,顺带一起学习下,继续学习咯,加油陌生人!!

学自严老师的教材---------------------------------------------------------------------------------------------------------文章来源地址https://www.toymoban.com/news/detail-446607.html

到了这里,关于利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法

    概念: 广度优先遍历算法是图的另一种基本遍历算法,其基本思想是尽最大程度辐射能够覆盖的节点,并对其进行访问。 以迷宫为例,广度优先搜索则可以想象成一组人一起朝不同的方向走迷宫,当出现新的未走过的路的时候,可以理解成一个人有分身术,继续从不同的方

    2024年02月06日
    浏览(63)
  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(67)
  • 广度优先遍历(邻接表,邻接矩阵)

        广度优先遍历又称为广度优先搜索,简称BFS     如果说图的深度优先遍历(图的深度优先遍历相关内容:图的深度优先遍历)类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历。     具体遍历过程如下图所示:     就如上面的第三个图上所编写的序号进

    2024年02月10日
    浏览(41)
  • 邻接表按深度优先遍历和按广度优先遍历的序列

    求此邻接表的深度优先遍历序列和广度优先遍历序列。   深度优先:按深度优先遍历时会有类似\\\"跳转\\\"的操作,比如例1中顶点v1→边v2后,会直接跳转到顶点v2去,再重新从顶点v2→边v1,由于v1访问过,所以变为v2→边v5,再跳转到顶点v5去,直到每个顶点都被访问过。抽象理解

    2024年02月04日
    浏览(45)
  • C++实现图—邻接矩阵,邻接表,深度遍历,广度遍历

    目录 1.图的基本概念 2.图的存储结构 2.1邻接矩阵 2.2 邻接表 3.图的遍历 3.1广度优先遍历 3.2图的深度遍历  总结: 图是由顶点集合以及顶点之间的关系组成的一种数据结构:G = (V,E),其中顶点集合V={x|x属于某个对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Pa

    2024年02月06日
    浏览(55)
  • 数据结构——图篇(邻接矩阵、邻接表、深度优先搜索、广度优先搜索)

    描述 图比树更为复杂,展现的是一种多对多的关系,图的结构是任意两个数据对象之间都可能存在某种特定的关系的数据结构 概念 顶点 : 基本介绍 顶点集合表示为V集合,要求图中顶点至少要有一个,即V集合不能为空集。通常使用|V|来表示顶点的个数,通常使用E(V)来表示

    2024年02月04日
    浏览(41)
  • 图、邻接矩阵、广度与深度优先、生成树

    最近突然被问到这个问题,于是复习一下,用最通俗的语言解释。 无向图 :如下左图各个顶点之间用不带箭头的边连接的图;相应的右图就是 有向图                 可以理解为表示上述图中顶点与顶点之间是否有直接相连的边(有则是1,无则是0),描述这种关系的二维

    2024年02月04日
    浏览(37)
  • 深度优先遍历(邻接矩阵,邻接表)

        深度优先遍历也称为深度优先搜索,简称为DFS。     深度优先遍历的思路是从图中某个顶点V出发,访问此顶点,然后从V的未被访问过的邻接点出发深度优先遍历图,直到图中所有与V路径相通的顶点都被访问到     该遍历过程用到递归。     深度优先遍历用到了一个辅

    2024年02月08日
    浏览(43)
  • 【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中: 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫 做边的集合。 完全图:在有n个顶点的无向图中,若有n * (n-1)/2条边,

    2024年02月04日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包