DFS和BFS学习总结
程序员文章站
2022-06-12 09:21:29
...
DFS深度优先遍历
深度遍历就是在图中从一个顶点开始,按照一个规则不重复地走下去。就是不撞南墙不回头一样。假如从A顶点开始,按照一个规则去走(假如我们按照一直字典顺序走)那么就从A走到B再从B走到了C,走到C后再按照字典顺序的时候,发现A已经走过,那么此时就退回到C点,选择另一个D走下去。就和树的前序遍历是一样的。
实现方式
1、递归实现(通过邻接矩阵来实现)
void DFS(MGrap G. int i)
{
int j = 0;
visited[i] = 1;
count++;
for(j=0; j<G.numVertexes; j++)
{
if(G.arc[i][j]==1 && !visited[j])//i和j有关系相邻,并且j顶点没有被访问过
{
DFS(G, j);
}
}
}
void dfs(MGrap G,int v)
{
init(&s);//使用自定义栈之前对栈进行初始化
push(&s,v); //入栈第一个元素
while(!isEmpty(&s))
{
pop(&s,&v); //取出栈顶元素
if(!visit[v]) //若没有访问过
{
cout<<v<<' '; //输出该顶点
visit[v]=true; //标记已经访问过
for(int k=0;k<M;k++) //查找与该顶点相关联的顶点
{
if(!visit[k]&&g[v][k]==1) //若果未被访问过,且有相连的边
{
/*入栈操作*/
push(&s,k);
}
}
}
}
}
BFS广度 优先搜索遍历
类似于树的层次搜索,主要是从图中的某个顶点出发,在访问此顶点后,依次访问未被访问的邻接顶点。
以A为开始节点,依次遍历B,C,再从B相邻的结点DFE开始遍历,最后遍历的结果就是:ABCDFEGHI(遵循先进先出规则)
实现(采用邻接矩阵)
1、采用队列的方式
void BFS(MGrap G)
{
int i,j;
Queue Q;
for(i=0; i<G.numVertexes; i++)/*初始化访问数组*/
{
visited[i] = -1;
}
InitQueue(&Q);
for(i=0; i<G.numVertexes; i++)
{
if(!visited[i])
{
visited[i] = 1;
printf("%c",G.vexs[i]);
EnQueue(&Q,i);/*入队操作*/
while(!QueueEmpty(Q))
{
DeQueue(&Q, &i);
for(j=0; j<G.numVertexes; j++)
{
/* 判断当前的节点与其他节点的关系 */
if(G.arc[i][j]==1 && !visited[j])
{
visited[j] = 1;
EnQueue(&Q,j);
}
}
}
}
}
}
总结:
两者的不同点是,BFS遍历的时候,按照深度去遍历,需要回退,所以需要用栈来记录原来顶点的位置;DFS是从相邻的结点开始依次遍历,所以先遍历到谁就先输出谁,所以采用队列的方式去实现。
下一篇: 哈希存储、哈希表原理
推荐阅读
-
JavaScript学习总结之正则的元字符和一些简单的应用
-
HTML学习记录和总结
-
jQuery学习和知识点总结归纳
-
DFS和BFS讲解及Leetcode刷题小结(1)(JAVA)
-
DFS和BFS的比较
-
java BigInteger大整数类 和 BigDecimal大浮点数类 解决大数问题 常用方法简单学习总结
-
Android系统学习总结3--Looper和Handler分析
-
11-S3C2440驱动学习(七)嵌入式linux-字符设备的另一种写法及RTC驱动程序分析和字符设备驱动框架总结
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
BFS(广度优先搜索算法)和DFS(深度优先搜索算法)