C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历

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

目录

定义无向图邻接矩阵

构造无向图

打印邻接矩阵

无向图邻接矩阵深度优先遍历(DFS)

无向图邻接矩阵广度优先遍历(BFS)

测试

 完整代码


定义无向图邻接矩阵

#define MVNum 100 //最大顶点数

//定义无向图邻接矩阵
struct AMGraph
{
	string vexs[MVNum]; //顶点表
	int arcs[MVNum][MVNum]; //邻接矩阵
	int vexnum, arcnum; //图的当前定点数和边数
};

构造无向图

1、输入总顶点数和总边数

2、依次输入顶点信息存入顶点表

3、初始化邻接矩阵,使每个权值初始化为极大值

4、构造邻接矩阵

//声明
int LocateVex(AMGraph G, string u);

//创建无向图
bool CreateUDN(AMGraph& G)
{
	//1.输入顶点数和边数
	cout << "请输入顶点数:" << endl;
	cin >> G.vexnum;
	cout << "请输入边数:" << endl;
	cin >> G.arcnum;

	//2.依次输入顶点信息存入顶点表
	cout << "请输入顶点:" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}

	//3.初始化邻接矩阵,使每个权值初始化为极大值
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0; //初始化邻接矩阵为0
		}
	}

	//4.构造邻接矩阵
	cout << "请输入一条边所依附的两个顶点及边的权值:" << endl;
	for (int k = 0; k < G.arcnum; k++)
	{
		string v1, v2;
		//int w;
		cin >> v1 >> v2; //输入一条边所依附的两个顶点及边的权值
		int i = LocateVex(G, v1); //确定v1,v2在G中的位置
		int j = LocateVex(G, v2);
		G.arcs[i][j] = 1; //边(v1,v2)的权值置为w
		G.arcs[j][i] = G.arcs[i][j]; //置边(v1,v2)的对称边(v2,v1)的权值为w
	}
	return true;
}

//在图中查找顶点u,存在返回顶点表中的下标,否则返回-1
int LocateVex(AMGraph G, string u)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (u == G.vexs[i])
		{
			return i;
		}
	}
	return -1;
}

打印邻接矩阵

//打印邻接矩阵
void PrintVex(AMGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
				cout << G.arcs[i][j] << "\t";
		}
		cout << endl;
	}
}

无向图邻接矩阵深度优先遍历(DFS)

1、在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;

2、再从w1出发,访问与w1邻接但还未被访问过的顶点w2;

3、然后再从w2出发,进行类似的访问,...

4、如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。

5、如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;

6、如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

bool visited[MVNum]; //深度优先访问标志数组, 其初值为 "false"

//无向图深度优先遍历
void DFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited[v] = true; //访问后标志数组中第v个顶点设为true(1)
	for (int w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在行
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w])) //表示w是v的邻接点, 如果w未访问, 则递归调用DFS
		{
			DFS(G, w);
		}
	}
}

无向图邻接矩阵广度优先遍历(BFS)

1、从图的一结点出发,首先依次访问该结点的所有邻接结点v1,v2......vn再按这些顶点被访问的先后次序依次访问与它们相邻的所有未被访问的顶点。

2、重复此过程,直至所有顶点均被访问为止。

bool visited1[MVNum]; //广度优先访问标志数组, 其初值为 "false"

//无向图广度优先遍历
void BFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited1[v] = true;//访问后标志数组中第v个顶点设为true(1)
	queue<int>Q;//创建队列Q
	Q.push(v); //v进队
	while (!Q.empty())//队列非空
	{
		int p = Q.front(); //取出队头元素赋给p
		for (int i = 0; i < G.vexnum; i++)
		{
			if ((G.arcs[p][i] != 0) && (!visited1[i]))//判断i是否是p未访问的邻接点
			{
				cout << G.vexs[i] << " ";//访问第i个顶点
				Q.push(i);//i进队
				visited1[i] = true;
			}
		}
		Q.pop();//删除队头元素
	}
}

测试

int main()
{
	AMGraph G;
	CreateUDN(G); //构造图
	cout << "图G的邻接矩阵为:" << endl;
	PrintVex(G); //打印
	int v = 0;
	cout << "广度优先遍历为:" << endl;
	BFS(G, v);
	cout << endl;
	cout << "深度优先遍历为:" << endl;
	DFS(G, v);
	cout << endl;

	system("pause");
	return 0;
}

C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历

 C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历文章来源地址https://www.toymoban.com/news/detail-456850.html

 完整代码

#include<iostream>
using namespace std;
#include<queue>

#define MVNum 100 //最大顶点数

//定义无向图邻接矩阵
struct AMGraph
{
	string vexs[MVNum]; //顶点表
	int arcs[MVNum][MVNum]; //邻接矩阵
	int vexnum, arcnum; //图的当前定点数和边数
};

bool visited[MVNum]; //深度优先访问标志数组, 其初值为 "false"

bool visited1[MVNum]; //广度优先访问标志数组, 其初值为 "false"


int LocateVex(AMGraph G, string u);

//创建无向图
bool CreateUDN(AMGraph& G)
{
	//1.输入顶点数和边数
	cout << "请输入顶点数:" << endl;
	cin >> G.vexnum;
	cout << "请输入边数:" << endl;
	cin >> G.arcnum;

	//2.依次输入顶点信息存入顶点表
	cout << "请输入顶点:" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}

	//3.初始化邻接矩阵,使每个权值初始化为极大值
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0; //初始化邻接矩阵为0
		}
	}

	//4.构造邻接矩阵
	cout << "请输入一条边所依附的两个顶点及边的权值:" << endl;
	for (int k = 0; k < G.arcnum; k++)
	{
		string v1, v2;
		//int w;
		cin >> v1 >> v2; //输入一条边所依附的两个顶点及边的权值
		int i = LocateVex(G, v1); //确定v1,v2在G中的位置
		int j = LocateVex(G, v2);
		G.arcs[i][j] = 1; //边(v1,v2)的权值置为w
		G.arcs[j][i] = G.arcs[i][j]; //置边(v1,v2)的对称边(v2,v1)的权值为w
	}
	return true;
}

//在图中查找顶点u,存在返回顶点表中的下标,否则返回-1
int LocateVex(AMGraph G, string u)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (u == G.vexs[i])
		{
			return i;
		}
	}
	return -1;
}

//打印邻接矩阵
void PrintVex(AMGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
				cout << G.arcs[i][j] << "\t";
		}
		cout << endl;
	}
}

//无向图深度优先遍历
void DFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited[v] = true; //访问后标志数组中第v个顶点设为true(1)
	for (int w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在行
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w])) //表示w是v的邻接点, 如果w未访问, 则递归调用DFS
		{
			DFS(G, w);
		}
	}
}

//无向图广度优先遍历
void BFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited1[v] = true;//访问后标志数组中第v个顶点设为true(1)
	queue<int>Q;//创建队列Q
	Q.push(v); //v进队
	while (!Q.empty())//队列非空
	{
		int p = Q.front(); //取出队头元素赋给p
		for (int i = 0; i < G.vexnum; i++)
		{
			if ((G.arcs[p][i] != 0) && (!visited1[i]))//判断i是否是p未访问的邻接点
			{
				cout << G.vexs[i] << " ";//访问第i个顶点
				Q.push(i);//i进队
				visited1[i] = true;
			}
		}
		Q.pop();//删除队头元素
	}
}

int main()
{
	AMGraph G;
	CreateUDN(G); //构造图
	cout << "图G的邻接矩阵为:" << endl;
	PrintVex(G); //打印
	int v = 0;
	cout << "广度优先遍历为:" << endl;
	BFS(G, v);
	cout << endl;
	cout << "深度优先遍历为:" << endl;
	DFS(G, v);
	cout << endl;

	system("pause");
	return 0;
}

到了这里,关于C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

    目录     --------------------------------------目录------------------------------------------ 图的定义和术语 图的邻接矩阵构建法   深度优先遍历算法(DFS)   广度优先遍历算法 (BFS) 全部代码          图 :G = (V,E) V:顶点的有穷非空集合 E:边的有穷集合          无向图 :每条

    2024年02月05日
    浏览(38)
  • 基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法

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

    2024年02月06日
    浏览(60)
  • 数据结构实验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日
    浏览(63)
  • 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日
    浏览(52)
  • 广度优先遍历(邻接表,邻接矩阵)

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

    2024年02月10日
    浏览(39)
  • 邻接矩阵储存图实现深度优先遍历(C++)

          目录 基本要求: 图的结构体: 图的构造: 图的深度优先(DFS): 图的打印输出: 完整代码: 测试数据:  运行结果:      通过给出的图的顶点和边的信息,构建无向图的邻接矩阵存储结构。在此基础上,从A顶点开始,对无向图进行深度优先遍历,输出遍历序列

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

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

    2024年02月04日
    浏览(42)
  • 数据结构上机实验——图的实现(以无向邻接表为例)、图的深度优先搜索(DFS)、图的广度优先搜索(BFS)

      图采用邻接表存储结构,编程实现图的深度优先搜索和广度优先搜索算法。              2.1创建图 2.1.1定义图的顶点、边及类定义   我们定义一个 邻接表类(ALGraph) 。这里实现一些基础的数据结构。要注意结构体的嵌套。    Edge: 用于表示图中的边

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

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

    2024年02月04日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包