图论里的DFS&BFS

版权声明:本文为奥维原创文章,未经允许不得转载.

前言: 学艺不精,简单剖析

概述

跟所有数据结构类似,图也需要有自己的遍历方法吧.

图的遍历和树的遍历有点像,都是从某一顶点出发,按照某种遍历方法最终对所有顶点都访问一遍.

而深度优先搜索(Deep First Search)和广度优先搜索(Breadth First Search)就是其中两种常用的搜索方式

实现思路

简单谈一下两种搜索方式的实现思路

  • 深度优先搜索:

    (1)从某一顶点(无所谓哪个顶点,标记为已访问过)开始遍历这个顶点的邻接点

    (2)如果遍历到某个点且该点还未被访问,那么我们就以这个点为新的顶点,重复(1)的动作

    (3)最后所有与最初那个开始点相连通的点都会被访问一遍

    我个人脑海中的画面DFS就是从某一个点开始不断往下挖,一直往下,先不管同一层的顶点,只是单纯的一直往他的下面去深挖,跟她的名字深度优先确实是不谋而合.在使用深度优先搜索的描述中我们可以发现使用递归是一种符合情况的解决方法

  • 广度优先搜索:

    广度优先搜索需要借助队列这种数据结构

    (1)从某一顶点开始入队(Queue),只要队列没空,我们就把队首的出队,然后开始遍历刚才出队的那个点的的所有邻接点,并把所有邻接点入队

    (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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUMBER 100
//邻接矩阵

#define MAXQUEUESIZE 100
typedef struct queue
{
int *base;
int front;
int rear;
}*LoopQueue;
LoopQueue initQueue(int size);
void enQueue(LoopQueue lq, int element);
int deQueue(LoopQueue lq);
int queueEmpty(LoopQueue lq);

typedef struct graphic
{
char vertexes[MAX_NUMBER];
int metrix[MAX_NUMBER][MAX_NUMBER];
int vertexNum, arcNum;
}*graphic;
int visited[MAX_NUMBER];
int visitedBreadthFirstSearch[MAX_NUMBER];
int locate(char v, graphic g);
void deepFirstSearch(graphic g, int site);
void breadthFirstSearch(graphic g, int v);
void initlaize(graphic g)
{
printf("please enter the number of the vertexes and the number of the arcNum\n");
scanf("%d %d", &g->vertexNum, &g->arcNum);
getchar();
//initialize the metrix
for (int i = 0; i < g->vertexNum; i++)
{
for (int j = 0; j < g->vertexNum; j++)
{
g->metrix[i][j] = 0;
}
}
printf("please enter all the values of the vertexes\n");
for (int i = 0; i < g->vertexNum; i++)
{
scanf("%c", &g->vertexes[i]);
getchar();
}
printf("please enter the vertexes which have the arcs\n");
for (int i = 0; i < g->arcNum; i++)
{
char v1, v2;
scanf("%c", &v1);
getchar();
scanf("%c", &v2);
getchar();
int site1, site2;

site1 = locate(v1, g);
site2 = locate(v2, g);
g->metrix[site1][site2] = g->metrix[site2][site1] = 1;
}
}
int locate(char v, graphic g)
{
for (int i = 0; i < g->vertexNum; i++)
{
if (g->vertexes[i] == v)
{
return i;
}
}
return -1;
}

//深度优先
void deepFirstSearch(graphic g, int site)
{
visited[site] = 1;
if (g != NULL)
{
for (int i = 0; i < g->vertexNum; i++)
{
if (g->metrix[site][i] == 1 && visited[i] == 0)
{
deepFirstSearch(g, i);
}
}
} else
{
printf("the graphic is null\n");
exit(0);
}
}
//广度优先
void breadthFirstSearch(graphic g, int v)
{
if (g != NULL)
{
visitedBreadthFirstSearch[v] = 1;
LoopQueue queue = initQueue(MAXQUEUESIZE);
enQueue(queue, v);
while(!queueEmpty(queue))
{
int w = deQueue(queue);
for (int i = 0; i < g->vertexNum; i++)
{
if (g->metrix[w][i] == 1 && !visitedBreadthFirstSearch[i])
{
visitedBreadthFirstSearch[i] = 1;
enQueue(queue, i);
}
}
}
} else
{
printf("the graphic is null\n");
exit(0);
}

}
LoopQueue initQueue(int size)
{
LoopQueue loopQueue = malloc(sizeof(struct queue));
loopQueue->base = malloc(sizeof(int) * (size + 1));
loopQueue->front = loopQueue->rear = 0;
return loopQueue;
}
void enQueue(LoopQueue lq, int element)
{
if ((lq->rear + 1) % MAXQUEUESIZE == lq->front)
{
printf("队满了\n");
exit(0);
} else
{
lq->base[lq->rear] = element;
lq->rear = (lq->rear + 1) % MAXQUEUESIZE;
}
}
int deQueue(LoopQueue lq)
{
int element;
if (lq->rear == lq->front)
{
printf("empty queue\n");
exit(0);
} else
{
element = lq->base[lq->front];
lq->front = (lq->front + 1) % MAXQUEUESIZE;
}
return element;

}
int queueEmpty(LoopQueue lq)
{
if (lq->rear == lq->front)
{
return 1;
}
return 0;
}
啦啦啦啦啦啦