图论 - 图的深度优先遍历c++实现

图的深度优先遍历c++实现

深度优先搜索

邻接矩阵的创建

	int i, j, m, a, b;

	cin >> n >> m;

	//初始化二维矩阵

	for (i = 1; i <= n; i++)

		for (j = 1; j <= n; j++)

			if (i == j)e[i][j] = 0;

			else e[i][j] = 0x3f;

	//读入顶点之间的边

	for (i = 1; i <= m; i++)

	{

		cin >> a >> b;

		e[a][b] = 1;

		e[b][a] = 1; //无向图需要将其对应的点的左边也赋值为1

	}

深度优先搜索算法实现

void dfs(int cur)

{

	int i;

	cout << cur << " ";

	sum++;//每访问一个节点sum就++

	if (sum == n)return;//所有的顶点已经访问过直接退出

	for (int i = 1; i <= n; i++)

	{

		//判断当前顶点cur到顶点i是否有边,并判断顶点i是否已经访问过

		if (e[cur][i] == 1 && book[i] == 0)

		{

			book[i] = 1;

			dfs(i);

		}

	}

	return;

}

整体代码

#include <iostream>

#include <cstdio>

using namespace std;

int book[101], sum, n, e[101][101];

void dfs(int cur)

{

	int i;

	cout << cur << " ";

	sum++;//没访问一个节点sum就++

	if (sum == n)return;//所有的顶点已经访问过直接退出

	for (int i = 1; i <= n; i++)

	{

		//判断当前顶点cur到顶点i是否有边,并判断顶点i是否已经访问过

		if (e[cur][i] == 1 && book[i] == 0)

		{

			book[i] = 1;

			dfs(i);

		}

	}

	return;

}

int main()

{

	int i, j, m, a, b;

	cin >> n >> m;

	//初始化二维矩阵

	for (i = 1; i <= n; i++)

		for (j = 1; j <= n; j++)

			if (i == j)e[i][j] = 0;

			else e[i][j] = 0x3f;

	//读入顶点之间的边

	for (i = 1; i <= m; i++)

	{

		cin >> a >> b;

		e[a][b] = 1;

		e[b][a] = 1; //无向图需要将其对应的点的左边也赋值为1

	}

	//从顶点1出发

	book[1] = 1;//标记一号顶点已经被访问

	dfs(1);//从1号顶点开始遍历

	system("pause");

	return 0;

}

巴特西

图论 - 图的深度优先遍历c++实现

图的深度优先遍历c++实现

邻接矩阵的创建

深度优先搜索算法实现

整体代码

最新文章

热门文章