搜尋
首頁常見問題圖的廣度優先遍歷類似二元樹的什麼？

圖的廣度優先遍歷類似二元樹的什麼？

青灯夜游
青灯夜游
Aug 29, 2020 pm 04:44 PM
二元樹

圖的廣度優先遍歷即橫向優先遍歷，類似二元樹的按層遍歷。廣度優先遍歷是從根結點開始沿著樹的寬度搜尋遍歷，即按層次的去遍歷；從上往下對每一層依次訪問，在每層中，從左往右（或右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

圖的廣度優先遍歷類似二元樹的什麼？

1.前言

和樹的遍歷類似，圖的遍歷也是從圖中某點出發，然後按照某種方法對圖中所有頂點進行訪問，且僅訪問一次。

但是圖的遍歷相對樹而言要更為複雜。因為圖中的任一頂點都可能與其他頂點相鄰，所以在圖的遍歷中必須記錄已被造訪的頂點，避免重複造訪。

根據搜尋路徑的不同，我們可以將遍歷圖的方法分為兩種：廣度優先搜尋和深度優先搜尋。

2.圖的基本概念

2.1.無向圖和無向圖

頂點對(u，v)是無序的，即（u，v ）和（v，u）是同一條邊。常用一對圓括號表示。


圖2-1-1 無向圖範例

頂點對有序的，它是指從頂點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数组，记录已被访问的顶点</char>
/*邻接矩阵存储表示*/
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 <pre class="brush:php;toolbar:false">/*采用邻接矩阵表示法，创建无向图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 <pre class="brush:php;toolbar:false">/*采用邻接矩阵表示图的广度优先遍历*/
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 <h6 id="用鄰接表表示圖的廣度優先搜尋">3.3.2用鄰接表表示圖的廣度優先搜尋</h6><pre class="brush:php;toolbar:false">/*找到顶点对应的下标*/
int LocateVex(ALGraph &G, char v)
{
	int i;
	for (i = 0; i <pre class="brush:php;toolbar:false">/*邻接表存储表示*/
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 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 <h3 id="深度優先搜尋">4.深度優先搜尋</h3><h4 id="演算法的基本想法">4.1演算法的基本想法</h4><p>深度優先搜尋類似於樹的先序遍歷，具體流程如下：</p><p>準備工作：建立一個visited數組，用來記錄所有被造訪過的頂點。 </p><p>1.從圖中v0出發，訪問v0。 </p><p>2.找出v0的第一個未被訪問的鄰接點，訪問該頂點。以此頂點為新頂點，重複此步驟，直到剛造訪過的頂點沒有未被造訪的鄰接點為止。 </p><p>3.返回前一個訪問過的仍有未被訪問鄰接點的頂點，繼續訪問該頂點的下一個未被訪問領接點。 </p><p>4.重複2,3步驟，直至所有頂點均被訪問，搜尋結束。 </p><h4 id="演算法的實作過程">4.2演算法的實作過程</h4><p>1.初始時所有頂點均未被訪問，visited陣列為空。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/28a5de9c91ea6a7f97d856a9f9c91ddd-21.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-1</span><br></p><p>#2.即將造訪v0。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/3925515129f521c1a514d91400d8127f-22.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-2</span><br></p><p>#3.存取v0，並將visited[0]的值置為1。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/3925515129f521c1a514d91400d8127f-23.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-3</span><br></p><p>#4.訪問v0的鄰接點v2，判斷visited [2]，因其值為0，訪問v2。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/3925515129f521c1a514d91400d8127f-24.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-4</span><br></p><p>#5.將visited[2]設為1。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/56cafcda422ea49a70fe640a822651b7-25.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-5</span><br></p><p>#6.訪問v2的鄰接點v0，判斷visited [0]，其值為1，不訪問。 </p><p>繼續訪問v2的鄰接點v4，判斷visited[4]，其值為0，訪問v4。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/56cafcda422ea49a70fe640a822651b7-26.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-6</span><br></p><p>#7.將visited[4]設為1。 </p><h6><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/56cafcda422ea49a70fe640a822651b7-27.png?x-oss-process=image/resize,p_40" class="lazy" alt=""></h6><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-7</span></p><p>#8.訪問v4的鄰接點v1，判斷visited[1]，其值為0，訪問v1。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/9c1b301e46789ef738f131512ef63029-28.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-8</span><br></p><p>#9.將visited[1]設為1。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/9c1b301e46789ef738f131512ef63029-29.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-9</span><br></p><p>#10.訪問v1的鄰接點v0，判斷visited [0]，其值為1，不訪問。 </p><p>繼續訪問v1的鄰接點v4，判斷visited[4]，其值為1，不訪問。 </p><p>繼續存取v1的鄰接點v5，判讀visited[5]，其值為0，存取v5。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/9c1b301e46789ef738f131512ef63029-30.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-10</span><br></p><p>#11.將visited[5]置為1。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/85a3191dbb1e1eaf27680d0a4ede40e3-31.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">圖4-2-11</span><br></p><p>#12.訪問v5的鄰接點v1，判斷visited [1]，其值為1，不訪問。 </p><p>繼續訪問v5的鄰接點v3，判斷visited[3]，其值為0，訪問v3。 </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/85a3191dbb1e1eaf27680d0a4ede40e3-32.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">图4-2-12</span><br></p><p>13.将visited[1]置为1。</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/03d57dba05ac30f4589d4c4fac4ad1d7-33.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">图4-2-13</span><br></p><p>14.访问v3的邻接点v0，判断visited[0]，其值为1，不访问。</p><p>继续访问v3的邻接点v5，判断visited[5]，其值为1，不访问。</p><p>v3所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5所有邻接点。</p><p>访问v5的邻接点v6，判断visited[6]，其值为0，访问v6。</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/03d57dba05ac30f4589d4c4fac4ad1d7-34.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">图4-2-14</span><br></p><p>15.将visited[6]置为1。</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/03d57dba05ac30f4589d4c4fac4ad1d7-35.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">图4-2-15</span><br></p><p>16.访问v6的邻接点v4，判断visited[4]，其值为1，不访问。</p><p>访问v6的邻接点v5，判断visited[5]，其值为1，不访问。</p><p>v6所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5剩余邻接点。<br></p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/aed9cf7d8caea6933340f104e72ac21c-36.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">图4-2-16</span><br></p><p>17.v5所有邻接点均已被访问，回溯到其上一个顶点v1。</p><p>v1所有邻接点均已被访问，回溯到其上一个顶点v4，遍历v4剩余邻接点v6。</p><p>v4所有邻接点均已被访问，回溯到其上一个顶点v2。<br></p><p>v2所有邻接点均已被访问，回溯到其上一个顶点v1，遍历v1剩余邻接点v3。<br></p><p>v1所有邻接点均已被访问，搜索结束。<br></p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/aed9cf7d8caea6933340f104e72ac21c-37.png?x-oss-process=image/resize,p_40" class="lazy" alt=""><br></p><p   style="max-width:90%"><span style="color:rgb(51,102,255);text-align:center;">图4-2-17</span><br></p><h4 id="具体代码实现">4.3具体代码实现</h4><h5 id="用邻接矩阵表示图的深度优先搜索">4.3.1用邻接矩阵表示图的深度优先搜索</h5><p>邻接矩阵的创建在上述已描述过，这里不再赘述</p><pre class="brush:php;toolbar:false">void DFS_AM(AMGraph &G, int v)
{
	int w;
	printf("%c ", G.vexs[v]);
	visited[v] = 1;
	for (w = 0; w <h5 id="用邻接表表示图的深度优先搜素">4.3.2用邻接表表示图的深度优先搜素</h5><p>邻接表的创建在上述已描述过，这里不再赘述。</p><pre class="brush:php;toolbar:false">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;
	}
}

更多相关知识，请访问：PHP中文网！

以上是圖的廣度優先遍歷類似二元樹的什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

顯示更多

熱門文章

刺客信條陰影：貝殼謎語解決方案
3 週前ByDDD
Windows 11 KB5054979中的新功能以及如何解決更新問題
2 週前ByDDD
在哪裡可以找到原子中的起重機控制鑰匙卡
3 週前ByDDD
節省R.E.P.O.解釋（並保存文件）
1 個月前By尊渡假赌尊渡假赌尊渡假赌
刺客信條陰影 - 如何找到鐵匠，解鎖武器和裝甲定制
3 週前ByDDD
顯示更多

熱工具

SublimeText3漢化版

SublimeText3漢化版

中文版，非常好用

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中，你可以繼續在那裡關注我們。 MinGW：GNU編譯器集合（GCC）的本機Windows移植版本，可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔；包括對MSVC執行時間的擴展，以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

mPDF

mPDF

mPDF是一個PHP庫，可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件，並處理不同的語言。與原始腳本如HTML2FPDF相比，它的速度較慢，並且在使用Unicode字體時產生的檔案較大，但支援CSS樣式等，並進行了大量增強。支援幾乎所有語言，包括RTL（阿拉伯語和希伯來語）和CJK（中日韓）。支援嵌套的區塊級元素（如P、DIV），

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

顯示更多

熱門話題

gmail信箱登陸入口在哪裡
7563
15
CakePHP 教程
1384
52
steam的賬戶名稱是什麼格式
84
11
win11激活密鑰永久
60
19
NYT連接提示和答案
28
99
顯示更多