备案控制台
探索云世界
开发者社区 人工智能 文章 正文

深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）（上）

2024-03-30 22
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）

深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）

深度优先搜索（简称“深搜”或DFS）

image.png

图 1 无向图


深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为：


  1. 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；
  2. 然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；
  3. 当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；
  4. 通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3  邻接点 V6 ，然后 V7 ；
  5. 由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；
  6. 最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。


根据上边的过程，可以得到图 1 通过深度优先搜索获得的顶点的遍历次序为：

V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7


所谓深度优先搜索，是从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。


深度优先搜索是一个不断回溯的过程。

采用深度优先搜索算法遍历图的实现代码为：

#include <stdio.h>
#define MAX_VERtEX_NUM 20 //顶点的最大个数
#define VRType int //表示顶点之间的关系的变量类型
#define InfoType char //存储弧或者边额外信息的指针变量类型
#define VertexType int //图中顶点的数据类型
typedef enum{false,true}bool; //定义bool型常量
bool visited[MAX_VERtEX_NUM]; //设置全局数组，记录标记顶点是否被访问过
typedef struct {
VRType adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
InfoType * info; //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
typedef struct {
VertexType vexs[MAX_VERtEX_NUM]; //存储图中顶点数据
AdjMatrix arcs; //二维数组，记录顶点之间的关系
int vexnum,arcnum; //记录图的顶点数和弧（边）数
}MGraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,VertexType v){
int i=0;
//遍历一维数组，找到变量v
for (; i<G->vexnum; i++) {
if (G->vexs[i]==v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i>G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无向图
void CreateDN(MGraph *G){
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
for (int i=0; i<G->vexnum; i++) {
scanf("%d",&(G->vexs[i]));
}
for (int i=0; i<G->vexnum; i++) {
for (int j=0; j<G->vexnum; j++) {
G->arcs[i][j].adj=0;
G->arcs[i][j].info=NULL;
}
}
for (int i=0; i<G->arcnum; i++) {
int v1,v2;
scanf("%d,%d",&v1,&v2);
int n=LocateVex(G, v1);
int m=LocateVex(G, v2);
if (m==-1 ||n==-1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj=1;
G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
}
}
int FirstAdjVex(MGraph G,int v)
{
//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
for(int i = 0; i<G.vexnum; i++){
if( G.arcs[v][i].adj ){
return i;
}
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
//从前一个访问位置w的下一个位置开始，查找之间有边的顶点
for(int i = w+1; i<G.vexnum; i++){
if(G.arcs[v][i].adj){
return i;
}
}
return -1;
}
void visitVex(MGraph G, int v){
printf("%d ",G.vexs[v]);
}
void DFS(MGraph G,int v){
visited[v] = true;//标记为true
visitVex( G, v); //访问第v 个顶点
//从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数
for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){
//如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数
if(!visited[w]){
DFS(G,w);
}
}
}
//深度优先搜索
void DFSTraverse(MGraph G){//
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G.vexnum; ++v){
visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
for( v = 0; v < G.vexnum; v++){
//如果该顶点的标记位为false，则调用深度优先搜索函数
if(!visited[v]){
DFS( G, v);
}
}
}
int main() {
MGraph G;//建立一个图的变量
CreateDN(&G);//初始化图
DFSTraverse(G);//深度优先搜索图
return 0;
}

以图 1 为例，运行结果为：

8,9

1

2

3

4

5

6

7

8

1,2

2,4

2,5

4,8

5,8

1,3

3,6

6,7

7,3

1 2 4 8 5 3 6 7


广度优先搜索


广度优先搜索类似于树的层次遍历。 从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。


最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。


还拿图 1 中的无向图为例，假设 V1 作为起始点，遍历其所有的邻接点 V2 和 V3 ，以 V2 为起始点，访问邻接点 V4 和 V5 ，以 V3 为起始点，访问邻接点 V6 、 V7 ，以 V4 为起始点访问 V8 ，以 V5 为起始点，由于 V5 所有的起始点已经全部被访问，所有直接略过， V6 和 V7 也是如此。

以 V1 为起始点的遍历过程结束后，判断图中是否还有未被访问的点，由于图 1 中没有了，所以整个图遍历结束。遍历顶点的顺序为：

V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8


广度优先搜索的实现需要借助队列这一特殊数据结构，实现代码为：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20 //顶点的最大个数
#define VRType int //表示顶点之间的关系的变量类型
#define InfoType char //存储弧或者边额外信息的指针变量类型
#define VertexType int //图中顶点的数据类型
typedef enum{false,true}bool; //定义bool型常量
bool visited[MAX_VERtEX_NUM]; //设置全局数组，记录标记顶点是否被访问过
typedef struct Queue{
VertexType data;
struct Queue * next;
}Queue;
typedef struct {
VRType adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
InfoType * info; //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
typedef struct {
VertexType vexs[MAX_VERtEX_NUM]; //存储图中顶点数据
AdjMatrix arcs; //二维数组，记录顶点之间的关系
int vexnum,arcnum; //记录图的顶点数和弧（边）数
}MGraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,VertexType v){
int i=0;
//遍历一维数组，找到变量v
for (; i<G->vexnum; i++) {
if (G->vexs[i]==v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i>G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无向图
void CreateDN(MGraph *G){
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
for (int i=0; i<G->vexnum; i++) {
scanf("%d",&(G->vexs[i]));
}
for (int i=0; i<G->vexnum; i++) {
for (int j=0; j<G->vexnum; j++) {
G->arcs[i][j].adj=0;
G->arcs[i][j].info=NULL;
}
}
for (int i=0; i<G->arcnum; i++) {
int v1,v2;
scanf("%d,%d",&v1,&v2);
int n=LocateVex(G, v1);
int m=LocateVex(G, v2);
if (m==-1 ||n==-1) {
printf("no this vertex\n");
return;
}
G->arcs[n][m].adj=1;
G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
}
}
int FirstAdjVex(MGraph G,int v)
{
//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
for(int i = 0; i<G.vexnum; i++){
if( G.arcs[v][i].adj ){
return i;
}
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
//从前一个访问位置w的下一个位置开始，查找之间有边的顶点
for(int i = w+1; i<G.vexnum; i++){
if(G.arcs[v][i].adj){
return i;
}
}
return -1;
}
//操作顶点的函数
void visitVex(MGraph G, int v){
printf("%d ",G.vexs[v]);
}
//初始化队列
void InitQueue(Queue ** Q){
(*Q)=(Queue*)malloc(sizeof(Queue));
(*Q)->next=NULL;
}
//顶点元素v进队列
void EnQueue(Queue **Q,VertexType v){
Queue * element=(Queue*)malloc(sizeof(Queue));
element->data=v;
element->next = NULL;
Queue * temp=(*Q);
while (temp->next!=NULL) {
temp=temp->next;
}
temp->next=element;
}
//队头元素出队列
void DeQueue(Queue **Q,int *u){
(*u)=(*Q)->next->data;
(*Q)->next=(*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(Queue *Q){
if (Q->next==NULL) {
return true;
}
return false;
}
//广度优先搜索
void BFSTraverse(MGraph G){//
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G.vexnum; ++v){
visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
Queue * Q;
InitQueue(&Q);
for( v = 0; v < G.vexnum; v++){
if(!visited[v]){
visited[v]=true;
visitVex(G, v);
EnQueue(&Q, G.vexs[v]);
while (!QueueEmpty(Q)) {
int u;
DeQueue(&Q, &u);
u=LocateVex(&G, u);
for (int w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G, u, w)) {
if (!visited[w]) {
visited[w]=true;
visitVex(G, w);
EnQueue(&Q, G.vexs[w]);
}
}
}
}
}
}
int main() {
MGraph G;//建立一个图的变量
CreateDN(&G);//初始化图
BFSTraverse(G);//广度优先搜索图
return 0;
}

例如，使用上述程序代码遍历图 1 中的无向图，运行结果为：

8,9

1

2

3

4

5

6

7

8

1,2

2,4

2,5

4,8

5,8

1,3

3,6

6,7

7,3

1 2 3 4 5 6 7 8


总结


本节介绍了两种遍历图的方式：深度优先搜索算法和广度优先搜索算法。深度优先搜索算法的实现运用的主要是回溯法，类似于树的先序遍历算法。广度优先搜索算法借助队列的先进先出的特点，类似于树的层次遍历。


深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）（中）：


文章标签：
算法
张继群
目录
相关文章
张继群
|
2月前
深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）（下）
深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）
张继群
11 0
张继群
|
2月前
|
存储 人工智能
深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）（中）
深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）
张继群
13 0
极客李华
|
4月前
八皇后问题与其深度优先搜索 (DFS) 解法
八皇后问题与其深度优先搜索 (DFS) 解法
极客李华
38 1
q3bzoidari2km
|
7月前
|
程序员 定位技术 C++
[蓝桥杯] 双指针、BFS和DFS与图论问题
本篇文章针对蓝桥杯比赛的考点，列出双指针、BFS和DFS与图论的相关习题以及知识点的解释。希望本篇文章会对你有所帮助。
q3bzoidari2km
51 0
程序员王天
|
8月前
|
存储 前端开发 算法
深度优先搜索（DFS）和广度优先搜索（BFS）
深度优先搜索（DFS）和广度优先搜索（BFS）
程序员王天
69 0
greework
|
11月前
|
算法 定位技术
算法 | 广度优先遍历BFS
算法 | 广度优先遍历BFS
greework
74 0
4km557m5ewrrm
|
12月前
DFS(深度优先搜索)和BFS(宽度优先搜索)
DFS(深度优先搜索)和BFS(宽度优先搜索)
4km557m5ewrrm
48 0
烽起黎明
|
算法 Java C++
力扣429 - N叉树的层序遍历【BFS+DFS】
详细绘图教学和动画制作，附有BFS和DFS的万能模板，来解决二叉树的层序遍历问题
烽起黎明
62 0
力扣429 - N叉树的层序遍历【BFS+DFS】
仙士可
|
算法 PHP
广度优先搜索(BFS)
广度优先搜索(BFS)
仙士可
117 0
广度优先搜索(BFS)
田埂、
|
算法 Java
java实现图的深度优先搜索(DFS)和广度优先搜索(BFS)
深度优先搜索、宽度优先搜索算法属于图算法的一种。
田埂、
558 0
java实现图的深度优先搜索(DFS)和广度优先搜索(BFS)

热门文章

最新文章

  • 1
    解决关于Windows Defender Antivirus Service自启造成运行python程序时，Windows的cpu和内存占用过高问题
  • 2
    订票系统不再瘫痪 阿里云确认与12306合作
  • 3
    iOS - 手动下架的应用后快速恢复上架
  • 4
    du 和 df以及lsof
  • 5
    库克：苹果不是只做富人生意，还一直坚持让世界变得更好
  • 6
    WiGig无线标准正式开始提供验证 最高可达8Gbps
  • 7
    IBM推出新的16位量子处理器
  • 8
    Android:随笔——对页面的View进行截图
  • 9
    shell MAC 地址 校验
  • 10
    【系统优化】数据库系统load飙高问题解决思路
  • 1
    DataWorks产品使用合集之DataWorks中，如果一个虚拟节点被设置为冻结状态，那么它的所有子节点也将被冻结如何解决
    23
  • 2
    DataWorks产品使用合集之DataWorks发布任务的方法如何解决
    25
  • 3
    DataWorks产品使用合集之DataWorks中，配置DataHub数据源如何解决
    23
  • 4
    Nacos 1.4.1核心功能组件及使用入门
    22
  • 5
    DataWorks产品使用合集之在 DataWorks 中，有一个 MySQL 数据表，数据量非常大且数据会不断更新将这些数据同步到 DataWorks如何解决
    14
  • 6
    基于直方图的图像阈值计算和分割算法FPGA实现,包含tb测试文件和MATLAB辅助验证
    13
  • 7
    DataWorks产品使用合集之在DataWorks中，要实现MySQL数据源的增量同步如何解决
    16

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考