溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細(xì)講解有關(guān)圖的廣度優(yōu)先遍歷算法類似于二叉樹的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
圖的廣度優(yōu)先遍歷即橫向優(yōu)先遍歷，類似于二叉樹的按層遍歷。廣度優(yōu)先遍歷是從根結(jié)點開始沿著樹的寬度搜索遍歷，即按層次的去遍歷；從上往下對每一層依次訪問，在每層中，從左往右（或右往左）訪問結(jié)點，訪問完一層就進(jìn)入下一層，直到?jīng)]有結(jié)點可以訪問為止。
1.前言
和樹的遍歷類似，圖的遍歷也是從圖中某點出發(fā)，然后按照某種方法對圖中所有頂點進(jìn)行訪問，且僅訪問一次。
但是圖的遍歷相對樹而言要更為復(fù)雜。因為圖中的任意頂點都可能與其他頂點相鄰，所以在圖的遍歷中必須記錄已被訪問的頂點，避免重復(fù)訪問。
根據(jù)搜索路徑的不同，我們可以將遍歷圖的方法分為兩種：廣度優(yōu)先搜索和深度優(yōu)先搜索。
頂點對(u，v)是無序的，即（u，v）和（v，u）是同一條邊。常用一對圓括號表示。
圖2-1-1 無向圖示例
頂點對<u,v>是有序的，它是指從頂點u到頂點 v的一條有向邊。其中u是有向邊的始點，v是有向邊的終點。常用一對尖括號表示。
圖2-1-2 有向圖示例
圖的每條邊上可能存在具有某種含義的數(shù)值，稱該數(shù)值為該邊上的權(quán)。而這種帶權(quán)的圖被稱為網(wǎng)。
連通圖：在無向圖G中，從頂點v到頂點v'有路徑，則稱v和v'是聯(lián)通的。若圖中任意兩頂點v、v'∈V，v和v'之間均聯(lián)通，則稱G是連通圖。上述兩圖均為連通圖。
非連通圖：若無向圖G中，存在v和v'之間不連通，則稱G是非連通圖。
圖2-3 非連通圖示例
廣度優(yōu)先搜索類似于樹的層次遍歷過程。它需要借助一個隊列來實現(xiàn)。如圖2-1-1所示，要想遍歷從v0到v6的每一個頂點，我們可以設(shè)v0為第一層，v1、v2、v3為第二層，v4、v5為第三層，v6為第四層，再逐個遍歷每一層的每個頂點。
具體過程如下：
1.準(zhǔn)備工作：創(chuàng)建一個visited數(shù)組，用來記錄已被訪問過的頂點；創(chuàng)建一個隊列，用來存放每一層的頂點；初始化圖G。
2.從圖中的v0開始訪問，將的visited[v0]數(shù)組的值設(shè)置為true，同時將v0入隊。
3.只要隊列不空，則重復(fù)如下操作：
(1)隊頭頂點u出隊。
(2)依次檢查u的所有鄰接頂點w，若visited[w]的值為false，則訪問w，并將visited[w]置為true，同時將w入隊。
白色表示未被訪問，灰色表示即將訪問，黑色表示已訪問。
visited數(shù)組：0表示未訪問，1表示以訪問。
隊列：隊頭出元素，隊尾進(jìn)元素。
1.初始時全部頂點均未被訪問，visited數(shù)組初始化為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，不進(jìn)行訪問。
繼續(xù)訪問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，不進(jìn)行訪問。
繼續(xù)訪問v1鄰接點v4，因為visited[4]的值為1，不進(jìn)行訪問。
繼續(xù)訪問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，不進(jìn)行訪問。
繼續(xù)訪問v3鄰接點v5，因為visited[5]值為1，不進(jìn)行訪問。
圖3-2-13
14.v3的全部鄰接點均已被訪問完畢，將隊頭元素v4出隊，開始訪問v4的所有鄰接點。
開始訪問v4的鄰接點v2，因為visited[2]的值為1，不進(jìn)行訪問。
繼續(xù)訪問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，不進(jìn)行訪問。
繼續(xù)訪問v5鄰接點v6，因為visited[6]的值為1，不進(jìn)行訪問。
圖3-2-16
17.v5的全部鄰接點均已被訪問完畢，將隊頭元素v6出隊，開始訪問v6的所有鄰接點。
開始訪問v6鄰接點v4，因為visited[4]的值為1，不進(jìn)行訪問。
繼續(xù)訪問v6鄰接點v5，因為visited[5]的值文1，不進(jìn)行訪問。
圖3-2-17
18.隊列為空，退出循環(huán)，全部頂點均訪問完畢。
圖3-2-18
/*一些量的定義*/ queue<char> q; //定義一個隊列，使用庫函數(shù)queue #define MVNum 100 //表示最大頂點個數(shù) bool visited[MVNum]; //定義一個visited數(shù)組，記錄已被訪問的頂點
/*鄰接矩陣存儲表示*/
typedef struct AMGraph
{
char vexs[MVNum]; //頂點表
int arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum, arcnum; //當(dāng)前的頂點數(shù)和邊數(shù)
}
AMGraph;/*找到頂點v的對應(yīng)下標(biāo)*/
int LocateVex(AMGraph &G, char v)
{
int i;
for (i = 0; i < G.vexnum; i++)
if (G.vexs[i] == v)
return i;
}/*采用鄰接矩陣表示法，創(chuàng)建無向圖G*/
int CreateUDG_1(AMGraph &G)
{
int i, j, k;
char v1, v2;
scanf("%d%d", &G.vexnum, &G.arcnum); //輸入總頂點數(shù)，總邊數(shù)
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的下標(biāo)
j = LocateVex(G, v2); //找到頂點j的下標(biāo)
G.arcs[i][j] = G.arcs[j][i] = 1; //1表示頂點i和j之間有邊，無向圖不區(qū)分方向
}
return 1;
}/*采用鄰接矩陣表示圖的廣度優(yōu)先遍歷*/
void BFS_AM(AMGraph &G,char v0)
{
/*從v0元素開始訪問圖*/
int u,i,v,w;
v = LocateVex(G,v0); //找到v0對應(yīng)的下標(biāo)
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的對應(yīng)下標(biāo)
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已被訪問
}
}
}
}/*找到頂點對應(yīng)的下標(biāo)*/
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 //邊結(jié)點
{
int adjvex; //該邊所指向的頂點的位置
ArcNode *nextarc; //指向下一條邊的指針
int info; //和邊相關(guān)的信息，如權(quán)值
}ArcNode;
typedef struct VexNode //表頭結(jié)點
{
char data;
ArcNode *firstarc; //指向第一條依附該頂點的邊的指針
}VexNode,AdjList[MVNum]; //AbjList表示一個表頭結(jié)點表
typedef struct ALGraph
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;/*采用鄰接表表示法，創(chuàng)建無向圖G*/
int CreateUDG_2(ALGraph &G)
{
int i, j, k;
char v1, v2;
scanf("%d%d", &G.vexnum, &G.arcnum); //輸入總頂點數(shù)，總邊數(shù)
getchar();
for (i = 0; i < G.vexnum; i++) //輸入各頂點，構(gòu)造表頭結(jié)點表
{
scanf("%c", &G.vertices[i].data); //輸入頂點值
G.vertices[i].firstarc = NULL; //初始化每個表頭結(jié)點的指針域為NULL
}
for (k = 0; k < G.arcnum; k++) //輸入各邊，構(gòu)造鄰接表
{
getchar();
scanf("%c%c", &v1, &v2); //輸入一條邊依附的兩個頂點
i = LocateVex(G, v1); //找到頂點i的下標(biāo)
j = LocateVex(G, v2); //找到頂點j的下標(biāo)
ArcNode *p1 = new ArcNode; //創(chuàng)建一個邊結(jié)點*p1
p1->adjvex = j; //其鄰接點域為j
p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; // 將新結(jié)點*p插入到頂點v1的邊表頭部
ArcNode *p2 = new ArcNode; //生成另一個對稱的新的表結(jié)點*p2
p2->adjvex = i;
p2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p1;
}
return 1;
}/*采用鄰接表表示圖的廣度優(yōu)先遍歷*/
void BFS_AL(ALGraph &G, char v0)
{
int u,w,v;
ArcNode *p;
printf("%c ", v0); //打印頂點v0
v = LocateVex(G, v0); //找到v0對應(yīng)的下標(biāo)
visited[v] = 1; //頂點v0已被訪問
q.push(v0); //將頂點v0入隊
while (!q.empty())
{
u = q.front(); //將頂點元素u出隊，開始訪問u的所有鄰接點
v = LocateVex(G, u); //得到頂點u的對應(yīng)下標(biāo)
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入隊
}
}
}
}/*廣度優(yōu)先搜索非連通圖*/
void BFSTraverse(AMGraph G)
{
int v;
for (v = 0; v < G.vexnum; v++)
visited[v] = 0; //將visited數(shù)組初始化
for (v = 0; v < G.vexnum; v++)
if (!visited[v]) BFS_AM(G, G.vexs[v]); //對尚未訪問的頂點調(diào)用BFS
}深度優(yōu)先搜索類似于樹的先序遍歷，具體過程如下：
準(zhǔn)備工作：創(chuàng)建一個visited數(shù)組，用于記錄所有被訪問過的頂點。
1.從圖中v0出發(fā)，訪問v0。
2.找出v0的第一個未被訪問的鄰接點，訪問該頂點。以該頂點為新頂點，重復(fù)此步驟，直至剛訪問過的頂點沒有未被訪問的鄰接點為止。
3.返回前一個訪問過的仍有未被訪問鄰接點的頂點，繼續(xù)訪問該頂點的下一個未被訪問領(lǐng)接點。
4.重復(fù)2,3步驟，直至所有頂點均被訪問，搜索結(jié)束。
1.初始時所有頂點均未被訪問，visited數(shù)組為空。
圖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，不訪問。
繼續(xù)訪問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，不訪問。
繼續(xù)訪問v1的鄰接點v4，判斷visited[4]，其值為1，不訪問。
繼續(xù)訪問v1的鄰接點v5，判讀visited[5]，其值為0，訪問v5。
圖4-2-10
11.將visited[5]置為1。
圖4-2-11
12.訪問v5的鄰接點v1，判斷visited[1]，其值為1，不訪問。
繼續(xù)訪問v5的鄰接點v3，判斷visited[3]，其值為0，訪問v3。
圖4-2-12
13.將visited[1]置為1。
圖4-2-13
14.訪問v3的鄰接點v0，判斷visited[0]，其值為1，不訪問。
繼續(xù)訪問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所有鄰接點均已被訪問，搜索結(jié)束。
圖4-2-17
鄰接矩陣的創(chuàng)建在上述已描述過，這里不再贅述
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]) //遞歸調(diào)用
DFS_AM(G,w);
}鄰接表的創(chuàng)建在上述已描述過，這里不再贅述。
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;
}
}關(guān)于“圖的廣度優(yōu)先遍歷算法類似于二叉樹的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼