欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无向图的深度优先搜索和广度优先搜索

程序员文章站 2022-05-23 10:05:06
...

深度优先搜索

// 无向图的邻接矩阵表示法实现深搜
#include <vector>
#include <iostream>
using namespace std;
#define MAX 5 //节点数量
char node[MAX]; //存储节点的容器
int node_edge[MAX][MAX]; //邻接矩阵
vector<char> dfs; //算法实现的辅助栈
bool visited[MAX]; //记录已经访问过的节点

void InPut() //输入邻接矩阵
{
	//依次输入节点
	cout << "Input nodes :" << endl;
	for (int i = 0; i < MAX; i++)
	{
		cin >> node[i];
	}
	// 1代表有边,0代表无边
	cout << "Input edges:" << endl;
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			cin >> node_edge[i][j];
		}
	}
	//将访问标记数组初始化
	memset(visited, false, MAX);
}
void DFS()
{
	//先取出第一个顶点
	char n = node[0];
	//入栈
	dfs.push_back(n); 
	while (!dfs.empty())
	{
		//获取栈顶元素
		char ch = dfs.back();
		//获取栈顶元素坐标
		int index;
		for (index = 0; index < MAX; index++)
		{
			if (node[index] == ch)
			{
				break;
			}
		}
		//判断是否已经被访问过
   		if (visited[index] == true)
		{
			//将这个节点的最近的一个没有被访问过的节点入栈
			int i;
			for (i = 0; i < MAX; i++)
			{
				if (node_edge[index][i] == 1 && visited[i] == false)
				{
					//入栈
					dfs.push_back(node[i]);
					break;
				}
			}
			if (i == MAX)
			{
				//所有邻接点都访问过了,出栈
				dfs.pop_back();
			}
			continue;
		}
		//访问栈顶元素
		cout << ch << " ";
		//标记已经被访问
		visited[index] = true;
	}
}
int main()
{
	InPut();
	DFS();
	return 0;
}

广度优先搜索

// 无向图的邻接矩阵表示法实现广搜
#include <queue>
#include <iostream>
using namespace std;
#define MAX 5 //节点数量
char node[MAX]; //存储节点的容器
int node_edge[MAX][MAX]; //邻接矩阵
queue<char> bfs; //算法实现的辅助队列
bool visited[MAX]; //记录已经访问过的节点

void InPut() //输入邻接矩阵
{
	//依次输入节点
	cout << "Input nodes :" << endl;
	for (int i = 0; i < MAX; i++)
	{
		cin >> node[i];
	}
	// 1代表有边,0代表无边
	cout << "Input edges:" << endl;
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			cin >> node_edge[i][j];
		}
	}
	//将访问标记数组初始化
	memset(visited, false, MAX);
}
void BFS()
{
	//先取出第一个顶点
	char n = node[0];
	bfs.push(n); //入队列
	while (!bfs.empty())
	{
		//出队列
		char ch = bfs.front();
		bfs.pop();
		//查找这个点的坐标
		int index;
		for (index = 0; index < MAX; index++)
		{
			if (node[index] == ch)
			{
				break;
			}
		}
		//查看这个点是否被访问过
		if (visited[index] == true)
		{
			continue;
		}
		//如果被访问过就访问这个点
		cout << ch << " ";
		//将这个点标记为已经访问过
		visited[index] = true;
		//将这个点的没有被访问过的邻居节点入队列
		for (int i = 0; i < MAX; i++)
		{
			if (node_edge[index][i] == 1 && visited[i] == false)
			{
				bfs.push(node[i]);
			}
		}
	}
}
int main()
{
	InPut();
	BFS();
	return 0;
}