二者的時間複雜度和空間複雜度均相同,不同的是,廣度優先周遊更像是樹的層次周遊,而深度優先周遊更像是樹的前序周遊。
下面是實作的代碼:
// BFS.cpp : 此檔案包含 "main" 函數。程式執行将在此處開始并結束。
//
#include "pch.h"
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char c[4] = { 'A', 'B', 'C', 'D' };
class graph {
public:
vector<vector<int>> arr;
vector<bool> check;
graph(){
//預設生成所需要的圖供示範用
/*
圖的形狀大緻如下:
A--B--C
\ | /
C
*/
for (int i = 0; i < 4; i++)
{
vector<int> temp(4, 0);
arr.push_back(temp);
}
arr[0][1] = arr[1][0] = arr[0][3] = arr[3][0] = arr[1][2] = arr[2][1] = arr[1][3] = arr[3][1] = arr[2][3] = arr[3][2] = 1;
}
void printGraph()
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
cout << arr[i][j] << " ";
}
cout << endl;
}
}
int getNeighbor(int index)
{
bool flag = false;
for (int i = 0; i < 4 && !flag; i++)
{
if (!check[i] && arr[index][i])
{
index = i;
check[i] = true;
flag = true;
}
if (!flag&&i == 3)
index = -1;
}
return index;
}
};
void BFS(graph g)
{
//廣度優先周遊該圖
//周遊結果為A B D C
queue<int> q;
for (int i = 0; i < 4; i++) g.check.push_back(false);
q.push(0);
g.check[0] = true;
while (!q.empty())
{
//周遊每一個和該節點相連的節點,入隊
for (int i = 0; i < 4; i++)
{
if (g.arr[q.front()][i] && !g.check[i])
{
q.push(i);
g.check[i] = true;
}
}
cout << c[q.front()] << " ";
q.pop();
}
cout << endl;
}
int help(graph& g, int index)
{
//深度優先搜尋的輔助函數
cout << c[index] << " ";
g.check[index] = true;
int w = g.getNeighbor(index);
if (w == -1)
return w;
else
return help(g, w);
}
void DFS(graph g)
{
//深度優先搜尋
for (int i = 0; i < 4; i++) g.check.push_back(false);
help(g, 0);
}
int main()
{
graph g;
g.printGraph();
BFS(g);
DFS(g);
}