站長資訊網圖的廣度優先遍歷即橫向優先遍歷，類似于二叉樹的按層遍歷。廣度優先遍歷是從根結點開始沿著樹的寬度搜索遍歷，即按層次的去遍歷；從上往下對每一層依次訪問，在每層中，從左往右（或右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。
1.前言
和樹的遍歷類似，圖的遍歷也是從圖中某點出發，然后按照某種方法對圖中所有頂點進行訪問，且僅訪問一次。
但是圖的遍歷相對樹而言要更為復雜。因為圖中的任意頂點都可能與其他頂點相鄰，所以在圖的遍歷中必須記錄已被訪問的頂點，避免重復訪問。
根據搜索路徑的不同，我們可以將遍歷圖的方法分為兩種：廣度優先搜索和深度優先搜索。
2.圖的基本概念
2.1.無向圖和無向圖
頂點對(u，v)是無序的，即（u，v）和（v，u）是同一條邊。常用一對圓括號表示。
圖2-1-1 無向圖示例
頂點對<u,v>是有序的，它是指從頂點u到頂點 v的一條有向邊。其中u是有向邊的始點，v是有向邊的終點。常用一對尖括號表示。
圖2-1-2 有向圖示例
2.2.權和網
圖的每條邊上可能存在具有某種含義的數值，稱該數值為該邊上的權。而這種帶權的圖被稱為網。
2.3.連通圖與非連通圖
連通圖：在無向圖G中，從頂點v到頂點v'有路徑，則稱v和v'是聯通的。若圖中任意兩頂點v、v'∈V，v和v'之間均聯通，則稱G是連通圖。上述兩圖均為連通圖。
非連通圖：若無向圖G中，存在v和v'之間不連通，則稱G是非連通圖。
圖2-3 非連通圖示例
3.廣度優先搜索
3.1.算法的基本思路
廣度優先搜索類似于樹的層次遍歷過程。它需要借助一個隊列來實現。如圖2-1-1所示，要想遍歷從v0到v6的每一個頂點，我們可以設v0為第一層，v1、v2、v3為第二層，v4、v5為第三層，v6為第四層，再逐個遍歷每一層的每個頂點。
具體過程如下：
1.準備工作：創建一個visited數組，用來記錄已被訪問過的頂點；創建一個隊列，用來存放每一層的頂點；初始化圖G。
2.從圖中的v0開始訪問，將的visited[v0]數組的值設置為true，同時將v0入隊。
3.只要隊列不空，則重復如下操作：
(1)隊頭頂點u出隊。
(2)依次檢查u的所有鄰接頂點w，若visited[w]的值為false，則訪問w，并將visited[w]置為true，同時將w入隊。
3.2.算法的實現過程
白色表示未被訪問，灰色表示即將訪問，黑色表示已訪問。
visited數組：0表示未訪問，1表示以訪問。
隊列：隊頭出元素，隊尾進元素。
1.初始時全部頂點均未被訪問，visited數組初始化為0，隊列中沒有元素。
圖3-2-1
2.即將訪問頂點v0。
圖3-2-2
3.訪問頂點v0，并置visited[0]的值為1，同時將v0入隊。
圖3-2-3
4.將v0出隊，訪問v0的鄰接點v2。判斷visited[2]，因為visited[2]的值為0，訪問v2。
圖3-2-4
5.將visited[2]置為1，并將v2入隊。
圖3-2-5
6.訪問v0鄰接點v1。判斷visited[1],因為visited[1]的值為0，訪問v1。
圖3-2-6
7.將visited[1]置為0，并將v1入隊。
圖3-2-7
8.判斷visited[3],因為它的值為0，訪問v3。將visited[3]置為0，并將v3入隊。
圖3-2-8
9.v0的全部鄰接點均已被訪問完畢。將隊頭元素v2出隊，開始訪問v2的所有鄰接點。
開始訪問v2鄰接點v0，判斷visited[0]，因為其值為1，不進行訪問。
繼續訪問v2鄰接點v4，判斷visited[4]，因為其值為0，訪問v4，如下圖：
圖3-2-9
10.將visited[4]置為1，并將v4入隊。
圖3-2-10
11.v2的全部鄰接點均已被訪問完畢。將隊頭元素v1出隊，開始訪問v1的所有鄰接點。
開始訪問v1鄰接點v0，因為visited[0]值為1，不進行訪問。
繼續訪問v1鄰接點v4，因為visited[4]的值為1，不進行訪問。
繼續訪問v1鄰接點v5，因為visited[5]值為0，訪問v5，如下圖：
圖3-2-11
12.將visited[5]置為1，并將v5入隊。
圖3-2-12
13.v1的全部鄰接點均已被訪問完畢，將隊頭元素v3出隊，開始訪問v3的所有鄰接點。
開始訪問v3鄰接點v0，因為visited[0]值為1，不進行訪問。
繼續訪問v3鄰接點v5，因為visited[5]值為1，不進行訪問。
圖3-2-13
14.v3的全部鄰接點均已被訪問完畢，將隊頭元素v4出隊，開始訪問v4的所有鄰接點。
開始訪問v4的鄰接點v2，因為visited[2]的值為1，不進行訪問。
繼續訪問v4的鄰接點v6，因為visited[6]的值為0，訪問v6，如下圖：
圖3-2-14
15.將visited[6]值為1，并將v6入隊。
圖3-2-15
16.v4的全部鄰接點均已被訪問完畢，將隊頭元素v5出隊，開始訪問v5的所有鄰接點。
開始訪問v5鄰接點v3，因為visited[3]的值為1，不進行訪問。
繼續訪問v5鄰接點v6，因為visited[6]的值為1，不進行訪問。
圖3-2-16
17.v5的全部鄰接點均已被訪問完畢，將隊頭元素v6出隊，開始訪問v6的所有鄰接點。
開始訪問v6鄰接點v4，因為visited[4]的值為1，不進行訪問。
繼續訪問v6鄰接點v5，因為visited[5]的值文1，不進行訪問。
圖3-2-17
18.隊列為空，退出循環，全部頂點均訪問完畢。
圖3-2-18
3.3具體代碼的實現
3.3.1用鄰接矩陣表示圖的廣度優先搜索
/*一些量的定義*/ queue<char> q; //定義一個隊列，使用庫函數queue #define MVNum 100 //表示最大頂點個數 bool visited[MVNum]; //定義一個visited數組，記錄已被訪問的頂點
/*鄰接矩陣存儲表示*/ typedef struct AMGraph { char vexs[MVNum]; //頂點表 int arcs[MVNum][MVNum]; //鄰接矩陣 int vexnum, arcnum; //當前的頂點數和邊數 } AMGraph;
/*找到頂點v的對應下標*/ int LocateVex(AMGraph &G, char v) { int i; for (i = 0; i < G.vexnum; i++) if (G.vexs[i] == v) return i; }
/*采用鄰接矩陣表示法，創建無向圖G*/ int CreateUDG_1(AMGraph &G) { int i, j, k; char v1, v2; scanf("%d%d", &G.vexnum, &G.arcnum); //輸入總頂點數，總邊數 getchar(); //獲取'n’，防止其對之后的字符輸入造成影響 for (i = 0; i < G.vexnum; i++) scanf("%c", &G.vexs[i]); //依次輸入點的信息 for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = 0; //初始化鄰接矩陣邊，0表示頂點i和j之間無邊 for (k = 0; k < G.arcnum; k++) { getchar(); scanf("%c%c", &v1, &v2); //輸入一條邊依附的頂點 i = LocateVex(G, v1); //找到頂點i的下標 j = LocateVex(G, v2); //找到頂點j的下標 G.arcs[i][j] = G.arcs[j][i] = 1; //1表示頂點i和j之間有邊，無向圖不區分方向 } return 1; }
/*采用鄰接矩陣表示圖的廣度優先遍歷*/ void BFS_AM(AMGraph &G,char v0) { /*從v0元素開始訪問圖*/ int u,i,v,w; v = LocateVex(G,v0); //找到v0對應的下標 printf("%c ", v0); //打印v0 visited[v] = 1; //頂點v0已被訪問 q.push(v0); //將v0入隊 while (!q.empty()) { u = q.front(); //將隊頭元素u出隊，開始訪問u的所有鄰接點 v = LocateVex(G, u); //得到頂點u的對應下標 q.pop(); //將頂點u出隊 for (i = 0; i < G.vexnum; i++) { w = G.vexs[i]; if (G.arcs[v][i] && !visited[i])//頂點u和w間有邊，且頂點w未被訪問 { printf("%c ", w); //打印頂點w q.push(w); //將頂點w入隊 visited[i] = 1; //頂點w已被訪問 } } } }
3.3.2用鄰接表表示圖的廣度優先搜索
/*找到頂點對應的下標*/ int LocateVex(ALGraph &G, char v) { int i; for (i = 0; i < G.vexnum; i++) if (v == G.vertices[i].data) return i; }
/*鄰接表存儲表示*/ typedef struct ArcNode //邊結點 { int adjvex; //該邊所指向的頂點的位置 ArcNode *nextarc; //指向下一條邊的指針 int info; //和邊相關的信息，如權值 }ArcNode; typedef struct VexNode //表頭結點 { char data; ArcNode *firstarc; //指向第一條依附該頂點的邊的指針 }VexNode,AdjList[MVNum]; //AbjList表示一個表頭結點表 typedef struct ALGraph { AdjList vertices; int vexnum, arcnum; }ALGraph;
/*采用鄰接表表示法，創建無向圖G*/ int CreateUDG_2(ALGraph &G) { int i, j, k; char v1, v2; scanf("%d%d", &G.vexnum, &G.arcnum); //輸入總頂點數，總邊數 getchar(); for (i = 0; i < G.vexnum; i++) //輸入各頂點，構造表頭結點表 { scanf("%c", &G.vertices[i].data); //輸入頂點值 G.vertices[i].firstarc = NULL; //初始化每個表頭結點的指針域為NULL } for (k = 0; k < G.arcnum; k++) //輸入各邊，構造鄰接表 { getchar(); scanf("%c%c", &v1, &v2); //輸入一條邊依附的兩個頂點 i = LocateVex(G, v1); //找到頂點i的下標 j = LocateVex(G, v2); //找到頂點j的下標 ArcNode *p1 = new ArcNode; //創建一個邊結點*p1 p1->adjvex = j; //其鄰接點域為j p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; // 將新結點*p插入到頂點v1的邊表頭部 ArcNode *p2 = new ArcNode; //生成另一個對稱的新的表結點*p2 p2->adjvex = i; p2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p1; } return 1; }
/*采用鄰接表表示圖的廣度優先遍歷*/ void BFS_AL(ALGraph &G, char v0) { int u,w,v; ArcNode *p; printf("%c ", v0); //打印頂點v0 v = LocateVex(G, v0); //找到v0對應的下標 visited[v] = 1; //頂點v0已被訪問 q.push(v0); //將頂點v0入隊 while (!q.empty()) { u = q.front(); //將頂點元素u出隊，開始訪問u的所有鄰接點 v = LocateVex(G, u); //得到頂點u的對應下標 q.pop(); //將頂點u出隊 for (p = G.vertices[v].firstarc; p; p = p->nextarc) //遍歷頂點u的鄰接點 { w = p->adjvex; if (!visited[w]) //頂點p未被訪問 { printf("%c ", G.vertices[w].data); //打印頂點p visited[w] = 1; //頂點p已被訪問 q.push(G.vertices[w].data); //將頂點p入隊 } } } }
3.4.非聯通圖的廣度優先遍歷的實現方法
/*廣度優先搜索非連通圖*/ void BFSTraverse(AMGraph G) { int v; for (v = 0; v < G.vexnum; v++) visited[v] = 0; //將visited數組初始化 for (v = 0; v < G.vexnum; v++) if (!visited[v]) BFS_AM(G, G.vexs[v]); //對尚未訪問的頂點調用BFS }
4.深度優先搜索
4.1算法的基本思路
深度優先搜索類似于樹的先序遍歷，具體過程如下：
準備工作：創建一個visited數組，用于記錄所有被訪問過的頂點。
1.從圖中v0出發，訪問v0。
2.找出v0的第一個未被訪問的鄰接點，訪問該頂點。以該頂點為新頂點，重復此步驟，直至剛訪問過的頂點沒有未被訪問的鄰接點為止。
3.返回前一個訪問過的仍有未被訪問鄰接點的頂點，繼續訪問該頂點的下一個未被訪問領接點。
4.重復2,3步驟，直至所有頂點均被訪問，搜索結束。
4.2算法的實現過程
1.初始時所有頂點均未被訪問，visited數組為空。
圖4-2-1
2.即將訪問v0。
圖4-2-2
3.訪問v0，并將visited[0]的值置為1。
圖4-2-3
4.訪問v0的鄰接點v2，判斷visited[2]，因其值為0，訪問v2。
圖4-2-4
5.將visited[2]置為1。
圖4-2-5
6.訪問v2的鄰接點v0，判斷visited[0]，其值為1，不訪問。
繼續訪問v2的鄰接點v4，判斷visited[4]，其值為0，訪問v4。
圖4-2-6
7.將visited[4]置為1。
圖4-2-7
8.訪問v4的鄰接點v1，判斷visited[1]，其值為0，訪問v1。
圖4-2-8
9.將visited[1]置為1。
圖4-2-9
10.訪問v1的鄰接點v0，判斷visited[0]，其值為1，不訪問。
繼續訪問v1的鄰接點v4，判斷visited[4]，其值為1，不訪問。
繼續訪問v1的鄰接點v5，判讀visited[5]，其值為0，訪問v5。
圖4-2-10
11.將visited[5]置為1。
圖4-2-11
12.訪問v5的鄰接點v1，判斷visited[1]，其值為1，不訪問。
繼續訪問v5的鄰接點v3，判斷visited[3]，其值為0，訪問v3。
圖4-2-12
13.將visited[1]置為1。
圖4-2-13
14.訪問v3的鄰接點v0，判斷visited[0]，其值為1，不訪問。
繼續訪問v3的鄰接點v5，判斷visited[5]，其值為1，不訪問。
v3所有鄰接點均已被訪問，回溯到其上一個頂點v5，遍歷v5所有鄰接點。
訪問v5的鄰接點v6，判斷visited[6]，其值為0，訪問v6。
圖4-2-14
15.將visited[6]置為1。
圖4-2-15
16.訪問v6的鄰接點v4，判斷visited[4]，其值為1，不訪問。
訪問v6的鄰接點v5，判斷visited[5]，其值為1，不訪問。
v6所有鄰接點均已被訪問，回溯到其上一個頂點v5，遍歷v5剩余鄰接點。
圖4-2-16
17.v5所有鄰接點均已被訪問，回溯到其上一個頂點v1。
v1所有鄰接點均已被訪問，回溯到其上一個頂點v4，遍歷v4剩余鄰接點v6。
v4所有鄰接點均已被訪問，回溯到其上一個頂點v2。
v2所有鄰接點均已被訪問，回溯到其上一個頂點v1，遍歷v1剩余鄰接點v3。
v1所有鄰接點均已被訪問，搜索結束。
圖4-2-17
4.3具體代碼實現
4.3.1用鄰接矩陣表示圖的深度優先搜索
鄰接矩陣的創建在上述已描述過，這里不再贅述
void DFS_AM(AMGraph &G, int v) { int w; printf("%c ", G.vexs[v]); visited[v] = 1; for (w = 0; w < G.vexnum; w++) if (G.arcs[v][w]&&!visited[w]) //遞歸調用 DFS_AM(G,w); }
4.3.2用鄰接表表示圖的深度優先搜素
鄰接表的創建在上述已描述過，這里不再贅述。
void DFS_AL(ALGraph &G, int v) { int w; printf("%c ", G.vertices[v].data); visited[v] = 1; ArcNode *p = new ArcNode; p = G.vertices[v].firstarc; while (p) { w = p->adjvex; if (!visited[w]) DFS_AL(G, w); p = p->nextarc; } }
