首页 > 代码库 > 广度优先和深度优先搜索算法

广度优先和深度优先搜索算法

#include <iostream>#include <stdlib.h>#include <vector>#include <string>#include <queue>#include <stack>using namespace std;//邻接矩阵显示图void show_graph(vector<vector<int>> &graph){	for (int i = 0; i < graph.size(); i++)	{		for (int j = 0; j < graph[i].size(); j++)		{			cout << graph[i][j] << "    ";		}		cout << endl;	}}//邻接矩阵----深度优先遍历----递归void DFS_digui(vector<vector<int>> &graph,vector<bool> &visited,int v){	cout << v + 1 << "---->";	visited[v] = true;	for (int i = 0; i < graph.size(); i++)	{		if (graph[v][i] != 0 && visited[i] == false)			DFS_digui(graph, visited, i);	}}void BFS(vector<vector<int>> &graph, vector<bool> &visited, int v){	queue<int> myqeue;	myqeue.push(v);	cout << v + 1 << "---->";	visited[v] = true;	while (!myqeue.empty())	{		int mark = myqeue.front();		myqeue.pop();		for (int i = 0; i < graph[mark].size(); i++)		{			if (graph[mark][i] != 0 && visited[i] == false)			{				cout << i + 1 << "---->";				visited[i] = true;				myqeue.push(i);			}		}	}}int main(){	int n = 8;	vector<vector<int>>  graph(n, vector<int> (n));	vector<bool> visited(graph.size());	for (int i = 0; i < visited.size(); i++)	{		visited[i] = false;	}	graph[0] = { 0, 1, 1, 0, 0, 0, 0, 0};	graph[1] = { 1, 0, 0, 1, 1, 0, 0, 0 };		graph[2] = { 1, 0, 0, 0, 0, 1, 1, 0 };	graph[3] = { 0, 1, 0, 0, 0, 0, 0, 1 };	graph[4] = { 0, 1, 0, 0, 0, 0, 0, 1 };	graph[5] = { 0, 0, 1, 0, 0, 0, 1, 0 };	graph[6] = { 0, 0, 1, 0, 0, 1, 0, 0 };	graph[7] = { 0, 0, 0, 1, 1, 0, 0, 0 };	show_graph(graph);	cout << endl;	DFS_digui(graph, visited, 0);	cout << endl;	for (int i = 0; i < visited.size(); i++)	{		visited[i] = false;	}	BFS(graph, visited, 0);	system("pause");	return 0;}

  

广度优先和深度优先搜索算法