對(duì)于廣度優(yōu)先遍歷算法DFS可以參考前一篇文章【數(shù)據(jù)結(jié)構(gòu)】深度優(yōu)先搜索算法DFS
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷(Breadth_First_Search)，又稱為廣度優(yōu)先搜索，簡(jiǎn)稱BFS棒掠。
圖的BFS類似于樹的層序遍歷烟很。
廣度優(yōu)先遍歷
- 如圖將左邊的圖變形，得到右邊的圖芹橡，然后一層一層的遍歷林说。
- 這里借助一個(gè)隊(duì)列來實(shí)現(xiàn)一層一層的遍歷。
鄰接矩陣的BFS
核心代碼
/**
* 鄰接矩陣的廣度優(yōu)先遍歷算法
*/
void BFSTraverse(MGraph G){
int i,j;
Queue Q;
for (i = 0; i < G.numVertexes; i++) {
visited[i] = FALSE;
}
InitQueue(&Q); // 初始化輔助隊(duì)列
for (i = 0; i < G.numVertexes; i++) { // 對(duì)每個(gè)頂點(diǎn)做循環(huán)
if (!visited[i]) {
visited[i] = TRUE;
printf("%c", G.vexs[i]);
EnQueue(&Q, i); // 頂點(diǎn)入隊(duì)列
while (!QueueEmpty(Q)) { // 隊(duì)列不為空
DeQueue(&Q, &i); // 將隊(duì)列元素出隊(duì)列
for (j = 0; j < G.numVertexes; j++) {
if (G.arc[i][j] == 1 && !visited[j]) { // 判斷其他頂點(diǎn)若與當(dāng)前頂點(diǎn)存在邊且未訪問過
visited[j] = TRUE;
printf("%c", G.vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
附上隊(duì)列操作的代碼
#pragma 用到的隊(duì)列
//循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)
typedef struct {
int data[MAXSIZE];
int front; // 頭指針
int rear; // 尾指針屯伞，若隊(duì)列不為空，指向隊(duì)列尾元素的下一個(gè)位置
}Queue;
/**
* 初始化一個(gè)空隊(duì)列
*/
Status InitQueue(Queue *Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
/**
* 判斷隊(duì)列是否為空
*/
Status QueueEmpty(Queue Q){
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
/**
* 插入
*/
Status EnQueue(Queue * Q, int e){
if ((Q->rear + 1) % MAXSIZE == Q->front) // 隊(duì)列滿
return ERROR;
Q->data[Q->rear] = e; // 元素e賦值給對(duì)尾
Q->rear = (Q->rear + 1)% MAXSIZE; // rear指針后移一個(gè)位置
return OK;
}
/**
* 刪除隊(duì)列中的元素
*/
Status DeQueue(Queue * Q, int *e){
if (Q->front == Q->rear)
return ERROR;
*e = Q->data[Q->front]; // 將隊(duì)頭元素賦值給e
Q->front = (Q->front+1)%MAXSIZE; // front指針后移
return OK;
}
鄰接表的BFS
核心代碼
void BFSTraverse(GraphAdjList GL){
int i;
EdgeNode *p;
Queue Q;
for (i = 0; i < GL->numVertexes; i++)
visited[i] = FALSE;
InitQueue(&Q);
for (i = 0; i < GL->numVertexes; i++) {
if (!visited[i]) {
visited[i] = TRUE;
printf("%c", GL->adjList[i].data); // 打印頂點(diǎn)
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
p = GL->adjList[i].firstedge; // 找到當(dāng)前頂點(diǎn)的邊表鏈表頭指針
while (p) {
if (!visited[p->adjvex]) { // 若次頂點(diǎn)沒有被訪問過
visited[p->adjvex] = TRUE;
printf("%c", GL->adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex); // 將次頂點(diǎn)入隊(duì)列
}
p = p->next;
}
}
}
}
}
圖的DFS與BFS
- 圖的深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法在時(shí)間復(fù)雜度上是一樣的劣摇。
- 深度優(yōu)先更適合目標(biāo)比較明確度秘，以找到目標(biāo)為目的的情況。
- 廣度優(yōu)先更適合在不斷擴(kuò)大遍歷范圍時(shí)找到相對(duì)最優(yōu)解的情況饵撑。
