问题描述
对下图分别进行广度和深度优先遍历。期望的输出结果为:
BFS:s-1-2-3-4-t
DFS:s-1-3-t-4-2
基本思路
广度优先:借助标记数组+队列,将与当前节点关联的所有未访问过的节点加到队列里,按队列次序输出即可,输出一个,出队一个。
深度优先:借助标记数组,依次递归遍历与当前节点关联的所有未访问过的节点,每次输出当前节点。
算法实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(vector<int> V, vector<vector<int> > E);
void DFS(vector<int> V, vector<vector<int> > E, int cur, vector<bool> *visited);
void BFS(vector<int> V, vector<vector<int> > E){
int n = V.size();
vector<bool> visited(n); //创建并自动初始化vector,默认值为false
queue<int> q;
q.push(0);
visited[0] = true;
while(!q.empty()){
int cur = q.front();
for (int i=0; i<n; i++){
if (!visited[i] && E[cur][i]!=0){
q.push(i);
visited[i] = true;
}
}
cout << V[cur] << endl;
q.pop();
}
}
//注意visited需要引用传递
void DFS(vector<int> V, vector<vector<int> > E, int cur, vector<bool> *visited){
cout << V[cur] << endl;
(*visited)[cur] = true;
for (int i=0; i<V.size(); i++) {
if (!(*visited)[i] && E[cur][i]!=0) {
DFS(V, E, i, visited);
}
}
}
int main()
{
vector<int> V = {1, 2, 3, 4, 5, 6};
vector<vector<int> > E = {{0, 8, 12, 0, 0, 0},
{0, 0, 0, 6, 10, 0},
{0, 2, 0, 10, 0, 0},
{0, 0, 0, 0, 0, 8},
{0, 0, 0, 2, 0, 10},
{0, 0, 0, 0, 0, 0}};
cout << "BFS:" << endl;
BFS(V, E);
vector<bool> visited(V.size()); //创建并自动初始化vector,默认值为false
cout << "DFS:" << endl;
DFS(V, E, 0, &visited);
return 0;
}