目錄

一.深度優(yōu)先搜索遍歷

1.深度優(yōu)先遍歷的方法

2.采用鄰接矩陣表示圖的深度優(yōu)先搜索遍歷

3.非連通圖的遍歷

二.廣度優(yōu)先搜索遍歷

1.廣度優(yōu)先搜索遍歷的方法

2.非連通圖的廣度遍歷

3.廣度優(yōu)先搜索遍歷的實(shí)現(xiàn)

4.按廣度優(yōu)先非遞歸遍歷連通圖

---

一.深度優(yōu)先搜索遍歷

1.深度優(yōu)先遍歷的方法

從圖中一個(gè)未訪問的頂點(diǎn)V開始，沿著一條路一直走到底，如果到達(dá)這條路盡頭的節(jié)點(diǎn) ，則回退到上一個(gè)節(jié)點(diǎn)，再從另一條路開始走到底…，不斷遞歸重復(fù)此過程，直到所有的頂點(diǎn)都遍歷完成。

以下面無向圖為例，2為起點(diǎn)

(1)以2為起點(diǎn)訪問1

(2)以1為起點(diǎn)，因?yàn)椤?”和“2”之間的邊已經(jīng)走過，所以走3

(3) 同理，以3為起點(diǎn)訪問5

(4)到5后，沒有可訪問的點(diǎn)，返回3，3也沒有可訪問的點(diǎn)，到1后，可訪問之前沒有訪問過的4

(5)4訪問6，至此，遍歷完所有的點(diǎn)，DFS(深度優(yōu)先搜索遍歷)：2->1->3->5->4->6

?2.采用鄰接矩陣表示圖的深度優(yōu)先搜索遍歷

#define MAX_VERTEX_NUM 100typedef struct {// 定義圖的相關(guān)信息int vexnum;                    // 頂點(diǎn)數(shù)int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 鄰接矩陣// 其他成員...
} AMSGraph;bool visited[MAX_VERTEX_NUM];      // 記錄頂點(diǎn)是否被訪問過void DFS(AMSGraph G, int v)
{cout << v;visited[v] = true;for (int w = 0; w < G.vexnum; w++) {if (G.arcs[v][w] == 1 && !visited[w]) {DFS(G, w);}}
}

http://t.csdn.cn/HmcOt

之前的一篇文章已經(jīng)詳細(xì)說明了鄰接矩陣和鄰接表的區(qū)別，這里同理

1.用鄰接矩陣表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，時(shí)間復(fù)雜度O()

2.用鄰接表表示圖，雖然有2e個(gè)表結(jié)點(diǎn)，但只需掃描e個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問n個(gè)頭結(jié)點(diǎn)的時(shí)間，時(shí)間復(fù)雜度為O(n+e)

?稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；

?稀疏圖適于在鄰接表上進(jìn)行深度遍歷。

3.非連通圖的遍歷

左邊的連通分量進(jìn)行深度優(yōu)先搜索遍歷，再在b,g之中選擇一個(gè)點(diǎn)進(jìn)行深度優(yōu)先搜索遍歷

其中一種合理的頂點(diǎn)訪問次序?yàn)?#xff1a;

a,c,h,d,f,k,e,b,g

二.廣度優(yōu)先搜索遍歷

1.廣度優(yōu)先搜索遍歷的方法

從某個(gè)頂點(diǎn)V出發(fā)，訪問該頂點(diǎn)的所有鄰接點(diǎn)V1，V2..VN，從鄰接點(diǎn)V1，V2...VN出發(fā)，再訪問他們各自的所有鄰接點(diǎn)，重復(fù)上述步驟，直到所有的頂點(diǎn)都被訪問過

以如下圖為例，起點(diǎn)為V1

?一層一層進(jìn)行訪問，廣度優(yōu)先搜索遍歷的結(jié)果為：V1->C2->V3->V4->V5->V6->V7->V8

2.非連通圖的廣度遍歷

與連通圖類似，在b,g中任意選擇一個(gè)點(diǎn)開始?

合理的頂點(diǎn)訪問次序?yàn)?#xff1a;a->c->d->e->f->h->k->b->g

?

3.廣度優(yōu)先搜索遍歷的實(shí)現(xiàn)

廣度優(yōu)先搜索遍歷的實(shí)現(xiàn)，與樹的層次遍歷很像，可以用隊(duì)列進(jìn)行實(shí)現(xiàn)(出隊(duì)一個(gè)結(jié)點(diǎn)，將他的鄰接結(jié)點(diǎn)入隊(duì))

以下動(dòng)圖來自愛編程的西瓜，方便大家理解遍歷過程

4.按廣度優(yōu)先非遞歸遍歷連通圖

#include <iostream>
using namespace std;const int MAX_SIZE = 100;  // 隊(duì)列的最大容量
const int MAX_VERTICES = 100;  // 圖的最大頂點(diǎn)數(shù)struct Queue {int data[MAX_SIZE];int front;  // 隊(duì)頭指針int rear;  // 隊(duì)尾指針
};struct Graph {  // 定義圖bool edges[MAX_VERTICES][MAX_VERTICES];  // 鄰接矩陣int numVertices;  // 實(shí)際頂點(diǎn)數(shù)
};void InitQueue(Queue& Q) {Q.front = 0;Q.rear = -1;
}bool EnQueue(Queue& Q, int x) {if (Q.rear == MAX_SIZE - 1) {// 隊(duì)列已滿，無法插入return false;}Q.data[++Q.rear] = x;return true;
}bool DeQueue(Queue& Q, int& x) {if (Q.front > Q.rear) {// 隊(duì)列為空，無法出隊(duì)return false;}x = Q.data[Q.front++];return true;
}bool QueueEmpty(Queue& Q) {return Q.front > Q.rear;
}// 找到頂點(diǎn)u的第一個(gè)鄰接點(diǎn)并返回
int FirstAdjVex(Graph& G, int u) {for (int v = 0; v < G.numVertices; ++v) {if (G.edges[u][v]) {return v;}}return -1;  // 或者返回一個(gè)特殊的值表示找不到鄰接點(diǎn)
}// 找到圖 G 中頂點(diǎn) u 相對(duì)于頂點(diǎn) w 的下一個(gè)鄰接點(diǎn)并返回
int NextAdjVex(Graph& G, int u, int w) {for (int v = w + 1; v < G.numVertices; ++v) {if (G.edges[u][v]) {return v;}}return -1;  // 或者返回一個(gè)特殊的值表示找不到下一個(gè)鄰接點(diǎn)
}void BFS(Graph G, int v) {cout << v;bool visited[MAX_VERTICES] = { false };visited[v] = true;  // 訪問第v個(gè)頂點(diǎn)Queue Q;InitQueue(Q);EnQueue(Q, v);  // v進(jìn)隊(duì)while (!QueueEmpty(Q)) {int u;DeQueue(Q, u);  // 隊(duì)頭元素出隊(duì)并置為ufor (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) {if (!visited[w]) {  // w為u的尚未訪問的鄰接點(diǎn)cout << w;visited[w] = true;EnQueue(Q, w);  // w進(jìn)隊(duì)(將訪問的每一個(gè)鄰接點(diǎn)入隊(duì))}}}
}

廣度優(yōu)先搜索遍歷算法的效率

1.如果使用鄰接矩陣，則BFS對(duì)于每一個(gè)被訪問到的頂點(diǎn)，都要循環(huán)檢測(cè)矩陣中的整整一行，時(shí)間復(fù)雜度為O()

2.用鄰接表來表示圖，雖然有2e個(gè)表結(jié)點(diǎn)，但只需掃描e個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問n個(gè)頭結(jié)點(diǎn)的實(shí)踐，時(shí)間復(fù)雜度為O(n+e)
?

?深度優(yōu)先搜索遍歷(DFS)與廣度優(yōu)先搜索遍歷(BFS)算法的效率

1.空間復(fù)雜度相同，都是O(n)（借用了堆?；蜿?duì)列）

2.時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)(鄰接矩陣【O()】或鄰接表【O(n+e)】)有關(guān)，而與搜索路徑無關(guān)