BFS和DFS代码实现

BFS DFS实现图的遍历
以以下图数据为例:

%title插图%num

首先BFS是广度优先遍历算法,从图的某一个节点出发,然后遍历完这个节点相邻的节点。这个算法的核心就是,先把周围的找完,再去找更深的地方。通俗易懂的说法:DFS就是一条路走到底,发现没路了,返回来,走另一条路。BFS就是每条路都走一点,走一点点后就走另一条路了。
在BFS遍历的时候,需要用队列将遍历的这个节点的相邻节点添加到队列中去,然后取队首,将这个节点相邻的节点加到队列中(未在队列中的),重复上述步骤。
以上面的图为例,假定我们先将A节点加入队列中,然后A节点出队列,与A节点相邻的B、C节点依次入队列,然后B节点出队列,与B节点相邻的C、D节点依次入队列…
*终我们得到的出队列的顺序为:A B C D E F,此答案不唯一,比如在A出队列后,可以先将B加入队列,然后是C,那么结果可能是A C B D E F,注意:*对不可能是A B C E D F,因为B和E不相邻。
根据以上思路,我们用Python代码实现BFS如下:

def DFS(graph, s):
queue = []
queue.append(s) # 向list添加元素,用append()
seen = set() # 此处为set, python里set用的是hash table, 搜索时比数组要快。
seen.add(s) # 向set添加函数,用add()
while (len(queue) > 0):
vertex = queue.pop(0) # 弹出*后一个元素
nodes = graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
print(vertex)
graph = {
“A”:[“B”,”C”],
“B”:[“A”,”C”,”D”],
“C”:[“A”,”B”,”D”,”E”],
“D”:[“B”,”C”,”E”,”F”],
“E”:[“C”,”D”],
“F”:[“D”]
}
DFS(graph, ‘A’)

C++代码如下:

#include <bits/stdc++.h>
using namespace std;
queue<char> q;
bool a[200];
void BFS(vector<char> vi[],char root)
{
q.push(root);
while(!q.empty())
{
char c = q.front();
q.pop();
cout << c << ” “;
a[(int)c] = 1;
for(int i=0; i<vi[c].size(); i++)
{
if(a[(int)vi[c][i]]==0)
{
q.push(vi[c][i]);
a[(int)vi[c][i]] = 1;
}
}
}
}
int main(void)
{
vector<char> vi[100];
vi[‘A’].push_back(‘B’);
vi[‘A’].push_back(‘C’);
vi[‘B’].push_back(‘A’);
vi[‘B’].push_back(‘C’);
vi[‘B’].push_back(‘D’);
vi[‘C’].push_back(‘A’);
vi[‘C’].push_back(‘B’);
vi[‘C’].push_back(‘D’);
vi[‘C’].push_back(‘E’);
vi[‘D’].push_back(‘B’);
vi[‘D’].push_back(‘C’);
vi[‘D’].push_back(‘E’);
vi[‘D’].push_back(‘F’);
vi[‘E’].push_back(‘C’);
vi[‘E’].push_back(‘D’);
vi[‘F’].push_back(‘D’);
BFS(vi, ‘E’);
}

DFS和BFS的唯一不同就是把队列换成栈