BFS(Breadth_First_Search)

DFS(Depth_First_Search)

ACM__搜素之BFS与DFS-LMLPHP

拿图来说

BFS过程,以1为根节点,1与2,3相连,找到了2,3,继续搜2,2与4,相连,找到了4,2与3也相连,然而3已经被找到了,跳过;搜3,3与5相连,找到了5;搜4,4与5相连,5已经被找到了,跳过,4与6相连,找到了6;5,6没有连其他点,结束;

DFS过程:以1为根节点,1与2,3相连;搜2,2与3,4相连;搜3,3与5相连;搜5,5没有与其他边相连,返回到3,3没有与其他边相连,返回到2;2还与4相连;搜4,4与5,6相连,5已经被找到了;搜6,6没有与其他点相连,返回到4,4已经搜完了,返回到2,2已经被搜完了,返回到1;1还与3相连,3已经被搜过了,结束!

BFS是一层一层的搜,DFS是一直搜到底,直到不能搜为止,再一层一层的递归

存图方式:

1:可以用二维数组来存,当需要存的数据太大的话,就不能用了,不过有些题也是可以用的

int edge[][];
cin<<a<<b;
edge[a][b]=;

2:可以用邻接链表来写,一般用vector

vector<int>edge[];
cin<<a<<b;
edge[a].push_back(b);

3:  链式前向星(等复习到这的时候再来补充吧)

具体过程代码

BFS

 #include<queue>
#include<vector>
#include<cstdio>
using namespace std;
bool vis[]
void BFS()
{
queue<int>q;
memset(vis,,sizeof(vis));//先将所有节点初始化,还没有访问过
vis[root]=;//找一个根节点,标记为1
q.push(a);//把该元素压入队列
while(!q.empty())
{
u=q.front();//取队列的首元素
q.pop();//首元素出队
for(int i=;i<edge[u].size();i++)
{
if(vis[edge[u][i]]==)//如果该点没有被访问过
{
vis[edge[u][i]]=;//表示该点已经访问过
q.push(edge[u][i]);//入队
}
}
}
}
int main()
{
vector<int>edge[];
cin<<a<<b;
edge[a].push_back(b);//输入所有边
BFS();//进行搜索
}

感觉像是,先找到根节点,入队,出队,再让与之相连的点入队,再是出队,让与之相连的点出队,重复这个过程,直到队列为空

DFS

DFS用递归实现

 vis[];
void DFS(int u)
{
vis[i]=;
for(int i=;i<edge[u].size();i++)
{
if(vis[edge[u][i]]==)
{ DFS(edge[u][i]);
}
}
}
int main()
{
memset(vis,,sizeof(vis));
}
05-11 20:23