BFSandDFS

Posted on
Words count in article: 4k | Reading time ≈ 18

BFSandDFS

DFS

深度优先搜索（Depth First Search，DFS），是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退回退到刚刚访问的结点，似不撞南墙不回头，不到黄河不死心。深度优先遍历是按照深度优先搜索的方式对图进行遍历。

时刻牢记： 后被访问的顶点，其邻接点先被访问。根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。

1.初始化图中所有顶点未被访问。

2.从图中的某个顶点v出发，访问v并标记已访问；

3.依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复2—3步）。

代码一览

基于邻接表的深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
using namespace std;

const int MaxVnum=100;//顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;//顶点的数据类型为字符型

typedef struct AdjNode{ //定义邻接点类型
	int v; //邻接点下标
	struct AdjNode *next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode{ //定义顶点类型
   VexType data; // VexType为顶点的数据类型，根据需要定义
   AdjNode *first; //指向第一个邻接点
}VexNode;

typedef struct{//定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum,edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G,VexType x)
{
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
		if(x==G.Vex[i].data)
        	return i;
    return -1;//没找到
}

void insertedge(ALGragh &G,int i,int j)//插入一条边
{
    AdjNode *s;
    s=new AdjNode;
    s->v=j;
    s->next=G.Vex[i].first;
    G.Vex[i].first=s;
}

void printg(ALGragh G)//输出邻接表
{
   cout<<"----------邻接表如下：----------"<<endl;
   for(int i=0;i<G.vexnum;i++)
   {
       AdjNode *t=G.Vex[i].first;
       cout<<G.Vex[i].data<<"：  ";
       while(t!=NULL)
       {
           cout<<"["<<t->v<<"]  ";
           t=t->next;
       }
       cout<<endl;
   }
}

void CreateALGraph(ALGragh &G)//创建无向图邻接表
{
    int i,j;
    VexType u,v;
    cout<<"请输入顶点数和边数:"<<endl;
    cin>>G.vexnum>>G.edgenum;
    cout<<"请输入顶点信息:"<<endl;
    for(i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
		cin>>G.Vex[i].data;
    for(i=0;i<G.vexnum;i++)
        G.Vex[i].first=NULL;
    cout<<"请依次输入每条边的两个顶点u,v"<<endl;
    while(G.edgenum--)
    {
        cin>>u>>v;
        i=locatevex(G,u);//查找顶点u的存储下标
        j=locatevex(G,v);//查找顶点v的存储下标
        if(i!=-1&&j!=-1)
        {
            insertedge(G,i,j);
            insertedge(G,j,i);//无向图多插入一条边
        }
        else
        {
			cout << "输入顶点信息错！请重新输入！"<<endl;
			G.edgenum++;//本次输入不算
        }
    }
}

void DFS_AL(ALGragh G,int v)//基于邻接表的深度优先遍历
{
    int w;
    AdjNode *p;
    cout<<G.Vex[v].data<<"\t";
    visited[v]=true;
    p=G.Vex[v].first;
    while(p)//依次检查v的所有邻接点
    {
		w=p->v;//w为v的邻接点
		if(!visited[w])//w未被访问
       		DFS_AL(G,w);//从w出发，递归深度优先遍历
		p=p->next;
    }
}

void DFS_AL(ALGragh G)//非连通图，基于邻接表的深度优先遍历
{
    for(int i=0;i<G.vexnum;i++)//非连通图需要查漏点，检查未被访问的顶点
    	if(!visited[i])//i未被访问,以i为起点再次深度优先遍历
       		DFS_AL(G,i);
}

int main()
{
    ALGragh G;
    int v;
    VexType c;
    CreateALGraph(G);//创建有向图邻接表
    printg(G);//输出邻接表
    cout << "请输入遍历连通图的起始点：";
	cin>>c;
	v=locatevex(G,c);//查找顶点u的存储下标
    if(v!=-1)
    {
        cout << "深度优先搜索遍历连通图结果：" <<endl;
        DFS_AL(G,v);
    }
    else
        cout << "输入顶点信息错！请重新输入！"<<endl;
    return 0;
}

基于邻接矩阵的深度优先遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
using namespace std;

#define MaxVnum 100  //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct{
  VexType Vex[MaxVnum];
  EdgeType Edge[MaxVnum][MaxVnum];
  int vexnum,edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G,VexType x)
{
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
       if(x==G.Vex[i])
        return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh &G)//创建无向图的邻接矩阵
{
    int i,j;
    VexType u,v;
    cout << "请输入顶点数："<<endl;
    cin>>G.vexnum;
    cout << "请输入边数:"<<endl;
    cin>>G.edgenum;
    cout << "请输入顶点信息:"<<endl;
    for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
        cin>>G.Vex[i];
    for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
      for(int j=0;j<G.vexnum;j++)
         G.Edge[i][j]=0;
    cout << "请输入每条边依附的两个顶点："<<endl;
    while(G.edgenum--)
    {
       cin>>u>>v;
       i=locatevex(G,u);//查找顶点u的存储下标
       j=locatevex(G,v);//查找顶点v的存储下标
       if(i!=-1&&j!=-1)
         G.Edge[i][j]=G.Edge[j][i]=1; //邻接矩阵储置1，若有向图G.Edge[i][j]=1
       else
       {
           cout << "输入顶点信息错！请重新输入！"<<endl;
           G.edgenum++;//本次输入不算
       }
    }
}

void print(AMGragh G)//输出邻接矩阵
{
    cout<<"图的邻接矩阵为："<<endl;
    for(int i=0;i<G.vexnum;i++)
    {
        for(int j=0;j<G.vexnum;j++)
        	cout<<G.Edge[i][j]<<"\t";
        cout<<endl;
    }
}

void DFS_AM(AMGragh G,int v)//基于邻接矩阵的深度优先遍历
{
    int w;
    cout<<G.Vex[v]<<"\t";
    visited[v]=true;
    for(w=0;w<G.vexnum;w++)//依次检查v的所有邻接点
       if(G.Edge[v][w]&&!visited[w])//v、w邻接(G.Edge[v][w]为1)而且w未被访问
          DFS_AM(G,w);//从w顶点开始递归深度优先遍历
}

int main()
{
    int v;
    VexType c;
    AMGragh G;
    CreateAMGraph(G);
    print(G);
    cout << "请输入遍历连通图的起始点：";
	cin>>c;
	v=locatevex(G,c);//查找顶点u的存储下标
    if(v!=-1)
    {
        cout << "深度优先搜索遍历连通图结果：" <<endl;
        DFS_AM(G,v);
    }
    else
        cout << "输入顶点信息错！请重新输入！"<<endl;
    return 0;
}

算法分析

1.基于邻接矩阵的DFS算法

查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为$O(n^2)$，使用了一个递归工作栈，空间复杂度为O(n)。

2.基于邻接表的DFS算法

查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为$O(e)$，加上初始化时间$O(n)$，总的时间复杂度为$O(n+e)$，使用了一个递归工作栈，空间复杂度为$O(n)$。

BFS

广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过邻接点出发，…，似水中涟漪，似声音传播，一层层地传播开来。广度优先遍历是按照广度优先搜索的方式对图进行遍历。

记住： 先被访问的顶点，其邻接点先被访问。

根据广度优先遍历秘籍，先来先服务，可以借助于队列实现。每个结点访问一次且只访问一次，因此可以设置一个辅助数组：

visited[i]=false，表示第i个顶点未访问；

visited[i]=true，表示第i个顶点已访问。

1.初始化图中所有顶点未被访问，初始化一个空队列。

2.从图中的某个顶点v出发，访问v并标记已访问，将v入队；

3.如果队列非空，则继续执行，否则算法结束；

4.队头元素v出队，依次访问v的所有未被访问邻接点，标记已访问并入队。转向步骤3；

代码一览

基于邻接表的广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

const int MaxVnum=100;//顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;//顶点的数据类型为字符型

typedef struct AdjNode{ //定义邻接点类型
	int v; //邻接点下标
	struct AdjNode *next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode{ //定义顶点类型
	VexType data; // VexType为顶点的数据类型，根据需要定义
	AdjNode *first; //指向第一个邻接点
}VexNode;

typedef struct{//定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum,edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G,VexType x)
{
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
		if(x==G.Vex[i].data)
			return i;
    return -1;//没找到
}

void insertedge(ALGragh &G,int i,int j)//插入一条边
{
    AdjNode *s;
    s=new AdjNode;
    s->v=j;
    s->next=G.Vex[i].first;
    G.Vex[i].first=s;
}

void printg(ALGragh G)//输出邻接表
{
   cout<<"----------邻接表如下：----------"<<endl;
   for(int i=0;i<G.vexnum;i++)
   {
       AdjNode *t=G.Vex[i].first;
       cout<<G.Vex[i].data<<"：  ";
       while(t!=NULL)
       {
           cout<<"["<<t->v<<"]  ";
           t=t->next;
       }
       cout<<endl;
   }
}

void CreateALGraph(ALGragh &G)//创建有向图邻接表
{
    int i,j;
    VexType u,v;
    cout<<"请输入顶点数和边数:"<<endl;
    cin>>G.vexnum>>G.edgenum;
    cout << "请输入顶点信息:"<<endl;
    for(i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
        cin>>G.Vex[i].data;
    for(i=0;i<G.vexnum;i++)
        G.Vex[i].first=NULL;
    cout<<"请依次输入每条边的两个顶点u,v"<<endl;
    while(G.edgenum--)
    {
        cin>>u>>v;
        i=locatevex(G,u);//查找顶点u的存储下标
        j=locatevex(G,v);//查找顶点v的存储下标
        if(i!=-1&&j!=-1)
            insertedge(G,i,j);
        else
        {
			cout << "输入顶点信息错！请重新输入！"<<endl;
			G.edgenum++;//本次输入不算
        }
    }
}

void BFS_AL(ALGragh G,int v)//基于邻接表的广度优先遍历
{
    int u,w;
    AdjNode *p;
    queue<int>Q; //创建一个普通队列(先进先出)，里面存放int类型
    cout<<G.Vex[v].data<<"\t";
    visited[v]=true;
    Q.push(v); //源点v入队
    while(!Q.empty()) //如果队列不空
    {
        u=Q.front();//取出队头元素赋值给u
        Q.pop(); //队头元素出队
        p=G.Vex[u].first;
        while(p)//依次检查u的所有邻接点
        {
            w=p->v;//w为u的邻接点
            if(!visited[w])//w未被访问
            {
            	cout<<G.Vex[w].data<<"\t";
            	visited[w]=true;
            	Q.push(w);
            }
            p=p->next;
        }
    }
}

void BFS_AL(ALGragh G)//非连通图，基于邻接表的广度优先遍历
{
    for(int i=0;i<G.vexnum;i++)//非连通图需要查漏点，检查未被访问的顶点
    	if(!visited[i])//i未被访问,以i为起点再次广度优先遍历
       		BFS_AL(G,i);
}

int main()
{
    ALGragh G;
    int v;
    VexType c;
    CreateALGraph(G);//创建有向图邻接表
    printg(G);//输出邻接表
    cout<<"请输入遍历连通图的起始点：";
	cin>>c;
	v=locatevex(G,c);//查找顶点u的存储下标
    if(v!=-1)
    {
        cout <<"广度优先搜索遍历连通图结果："<<endl;
        BFS_AL(G,v);
    }
    else
        cout<<"输入顶点信息错！请重新输入！"<<endl;
    return 0;
}

基于邻接矩阵的广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

#define MaxVnum 100  //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct{
	VexType Vex[MaxVnum];
	EdgeType Edge[MaxVnum][MaxVnum];
	int vexnum,edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G,VexType x)
{
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
		if(x==G.Vex[i])
       		return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh &G)//创建有向图的邻接矩阵
{
    int i,j;
    VexType u,v;
    cout << "请输入顶点数："<<endl;
    cin>>G.vexnum;
    cout << "请输入边数:"<<endl;
    cin>>G.edgenum;
    cout << "请输入顶点信息:"<<endl;
    for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
		cin>>G.Vex[i];
    for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
		for(int j=0;j<G.vexnum;j++)
			G.Edge[i][j]=0;
    cout << "请输入每条边依附的两个顶点："<<endl;
    while(G.edgenum--)
    {
       cin>>u>>v;
       i=locatevex(G,u);//查找顶点u的存储下标
       j=locatevex(G,v);//查找顶点v的存储下标
		if(i!=-1&&j!=-1)
			G.Edge[i][j]=1; //邻接矩阵储置1，若无向图G.Edge[i][j]=G.Edge[j][i]=1
		else
		{
			cout << "输入顶点信息错！请重新输入！"<<endl;
			G.edgenum++;//本次输入不算
		}
    }
}

void print(AMGragh G)//输出邻接矩阵
{
    cout<<"图的邻接矩阵为："<<endl;
    for(int i=0;i<G.vexnum;i++)
    {
        for(int j=0;j<G.vexnum;j++)
			cout<<G.Edge[i][j]<<"\t";
        cout<<endl;
    }
}

void BFS_AM(AMGragh G,int v)//基于邻接矩阵的广度优先遍历
{
    int u,w;
    queue<int>Q; //创建一个普通队列(先进先出)，里面存放int类型
    cout<<G.Vex[v]<<"\t";
    visited[v]=true;
    Q.push(v); //源点v入队
    while(!Q.empty()) //如果队列不空
    {
        u=Q.front();//取出队头元素赋值给u
        Q.pop(); //队头元素出队
        for(w=0;w<G.vexnum;w++)//依次检查u的所有邻接点
        {
            if(G.Edge[u][w]&&!visited[w])//u、w邻接而且w未被访问
            {
               cout<<G.Vex[w]<<"\t";
               visited[w]=true;
               Q.push(w);
            }
        }
    }
}

int main()
{
    int v;
    VexType c;
    AMGragh G;
    CreateAMGraph(G);
    print(G);
    cout << "请输入遍历连通图的起始点：";
	cin>>c;
	v=locatevex(G,c);//查找顶点u的存储下标
    if(v!=-1)
    {
        cout << "广度优先搜索遍历连通图结果：" <<endl;
        BFS_AM(G,v);
    }
    else
        cout << "输入顶点信息错！请重新输入！"<<endl;
    return 0;
}

算法分析

1.基于邻接矩阵的BFS算法

查找每个顶点的邻接点需要$O(n)$时间，一共$n$个顶点，总的时间复杂度为$O(n^2)$，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为$O(n)$。

2.基于邻接表的BFS算法

查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为$v_i$的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间$O(n)$，总的时间复杂度为$O(n+e)$，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为$O(n)$。

总而言之，只要是邻接矩阵，BFS、DFS都是 $O(n^2)$ ； 只要是邻接表，BFS、DFS 时间复杂度都是 $O(n)$

-------------本文结束，感谢您的阅读-------------