[数据结构与算法]无向图的深度优先搜索和广度优先搜索

深度优先搜索

// 无向图的邻接矩阵表示法实现深搜
#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;
}