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

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

深度优先搜索（DFS）和广度优先搜索（BFS）是图论中两种基本的遍历算法。本文将详细介绍这两种算法的基本原理、实现方法以及它们在生成树和生成森林中的应用。

深度优先搜索（DFS）

深度优先搜索类似于树的先序遍历，从图中的一个顶点出发，沿着一条路径尽可能深地进行遍历，直到无法继续为止，然后回溯到上一个节点，继续遍历其他路径。以下是深度优先搜索的具体步骤：

1. 从任意一个未被访问过的顶点开始，标记该顶点为已访问。
2. 遍历该顶点的所有邻接点，对每个未被访问的邻接点递归地进行深度优先搜索。
3. 当所有邻接点都被访问过时，回溯到上一个节点，继续遍历其他路径。
4. 重复上述过程，直到所有顶点都被访问过。

DFS算法实现

以下是深度优先搜索的C语言实现代码：

#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);
void CreateDN(MGraph *G);
int FirstAdjVex(MGraph G,int v);
int NextAdjVex(MGraph G,int v,int w);
void visitVex(MGraph G, int v);
void DFS(MGraph G,int v);
void DFSTraverse(MGraph G);

int main() {
MGraph G;
CreateDN(&G);
DFSTraverse(G);
return 0;
}

int LocateVex(MGraph * G,VertexType v) {
int i=0;
for (; i<G->vexnum; i++) {
if (G->vexs[i]==v) {
break;
}
}
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) {
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) {
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;
visitVex( G, v);
for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){
if(!visited[w]){
DFS(G,w);
}
}
}

void DFSTraverse(MGraph G) {
int v;
for( v = 0; v < G.vexnum; ++v){
visited[v] = false;
}
for( v = 0; v < G.vexnum; v++){
if(!visited[v]){
DFS( G, v);
}
}
}

广度优先搜索（BFS）

广度优先搜索类似于树的层次遍历，从图中的一个顶点出发，依次访问其所有邻接点，然后再从这些邻接点出发，依次访问它们的邻接点，直到所有顶点都被访问过。以下是广度优先搜索的具体步骤：

1. 从任意一个未被访问过的顶点开始，标记该顶点为已访问。
2. 将该顶点的所有未被访问的邻接点加入队列。
3. 从队列中取出一个顶点，标记为已访问，然后将其所有未被访问的邻接点加入队列。
4. 重复上述过程，直到队列为空。

BFS算法实现

以下是广度优先搜索的C语言实现代码：

#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);
void CreateDN(MGraph *G);
int FirstAdjVex(MGraph G,int v);
int NextAdjVex(MGraph G,int v,int w);
void visitVex(MGraph G, int v);
void InitQueue(Queue ** Q);
void EnQueue(Queue **Q,VertexType v);
void DeQueue(Queue **Q,int *u);
bool QueueEmpty(Queue *Q);
void BFSTraverse(MGraph G);

int main() {
MGraph G;
CreateDN(&G);
BFSTraverse(G);
return 0;
}

int LocateVex(MGraph * G,VertexType v) {
int i=0;
for (; i<G->vexnum; i++) {
if (G->vexs[i]==v) {
break;
}
}
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) {
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) {
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;
}

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;
for( v = 0; v < G.vexnum; ++v){
visited[v] = 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]);
}
}
}
}
}
}

生成树与生成森林

在遍历图的过程中，所经历的顶点和边的组合可以构成图的生成树或生成森林。

深度优先生成树与广度优先生成树

深度优先生成树是通过深度优先搜索得到的树，而广度优先生成树是通过广度优先搜索得到的树。以下是深度优先生成树和广度优先生成树的示例：

图 2 深度优先生成树

图 3 广度优先生成树

非连通图的生成森林

非连通图的生成森林由多个连通分量的生成树组成。以下是深度优先生成森林和广度优先生成森林的示例：

图 4 深度优先生成森林

图 5 孩子兄弟表示法表示深度优先生成森林

图 6 广度优先生成森林（孩子兄弟表示法）

总结

本文详细介绍了深度优先搜索和广度优先搜索的基本原理、实现方法以及它们在生成树和生成森林中的应用。这两种算法是图论中非常重要的基础算法，广泛应用于各种图的遍历和搜索场景。