BFS(Breadth First Search)广度优先搜素,正在调试... wang

#include <iostream>
#include
<vector>
#include
<list>
#include
<queue>
#include
<set>
#include
<cstdlib>
#include
<stack>
usingnamespace std;
void bfs(vector< list<int>>& adj_lists,int start_node)
{
queue
<int> not_yet_explored;
set<int> discovered;
//标记起始点为已发现,并将其放入队列开始搜索
not_yet_explored.push(start_node);
discovered.insert(start_node);
while(!not_yet_explored.empty())
{
//获取一个新的结点并依次作为基点进行探索
int node_to_explore=not_yet_explored.front();

not_yet_explored.pop();

//检测该点所有的边
list<int>::iterator edges = adj_lists[node_to_explore].begin();
for( ; edges != adj_lists[node_to_explore].end() ;edges++ );
{
if(discovered.count(*edges) ==0)
{
//发现新的结点将其加入队列
discovered.insert(*edges);
not_yet_explored.push(
*edges);
cout
<<"Found"<<*edges <<" from "<<node_to_explore<<endl;

}
}
}
}

//DFS
void dfs_helper(vector< list <int>>& adj_lists , set<int>& discovered , int node)
{
//检查该点所有的边
list<int>::iterator edges = adj_lists[node].begin();
for (;edges!=adj_lists[node].end();edges++)
{
//检查某条边是否含有未发现的顶点
if(discovered.count(*edges)==0)
{
discovered.insert(
*edges);
cout
<<"Found "<<*edges<<" from "<< node<<endl;
dfs_helper(adj_lists,discovered ,
*edges);
}
}
}

void dfs(vector< list<int>>& adj_lists ,int start_node)
{
//标记顶点为已被发现
set<int> discovered;
discovered.insert(start_node);
dfs_helper(adj_lists,discovered ,start_node);
}


void main()
{
//初始化图的信息

vector
< list<int>> g(7, list<int>());


g[
0].push_back(2);
g[
0].push_back(1);

g[
1].push_back(0);
g[
1].push_back(2);

g[
2].push_back(0);
g[
2].push_back(1);
g[
2].push_back(3);
g[
2].push_back(4);

g[
3].push_back(2);
g[
3].push_back(4);
g[
3].push_back(5);

g[
4].push_back(2);
g[
4].push_back(3);
g[
4].push_back(5);
g[
4].push_back(6);

g[
5].push_back(3);
g[
5].push_back(4);

g[
6].push_back(4);

cout
<<"BFS"<<endl;
bfs(g,
0);
cout
<< endl<<"DFS"<<endl;
//dfs(g,0);

}

  

  

原文地址:https://www.cnblogs.com/Turtle/p/2177904.html