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

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

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数组，记录已被访问的顶点

/*邻接矩阵存储表示*/
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;
	}
}

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

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