快捷導(dǎo)航

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(一)

更新時(shí)間：2021年12月13日 11:36:47 作者：玄澈_

這篇文章主要是介紹了利用深度優(yōu)先算法實(shí)現(xiàn)圖的遍歷，文中利用圖文詳細(xì)的介紹了實(shí)現(xiàn)步驟，對(duì)我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法有一定的幫助，需要的朋友可以參考一下

引入?

在數(shù)據(jù)結(jié)構(gòu)中常見(jiàn)的有深度優(yōu)先搜索和廣度優(yōu)先搜索。為什么叫深度和廣度呢？其實(shí)是針對(duì)圖的遍歷而言的，請(qǐng)看下面這個(gè)圖：

圖是由一些小圓點(diǎn)（稱(chēng)為頂點(diǎn)）和連接這些點(diǎn)的直線(xiàn) （稱(chēng)為邊）組成的。

例如上圖就是由5個(gè)頂點(diǎn)（編號(hào)為 1,2,3,4,5）和5條邊（1-2,1-3,1-4,2-4）組成。

現(xiàn)在我們從1號(hào)頂點(diǎn)開(kāi)始遍歷這個(gè)圖，遍歷就是把圖的每一個(gè)頂點(diǎn)都訪(fǎng)問(wèn)一次。使用深度優(yōu)先搜索將會(huì)得到如下的結(jié)果。

圖中每個(gè)頂點(diǎn)旁邊的數(shù)表示這個(gè)頂點(diǎn)是第幾個(gè)被訪(fǎng)問(wèn)到的，我們稱(chēng)之為 —— 時(shí)間戳?

深度優(yōu)先搜索

使用深度優(yōu)先搜索來(lái)遍歷這個(gè)圖的過(guò)程：

首先從一個(gè)未走過(guò)的頂點(diǎn)作為起始頂點(diǎn)，比如以1號(hào)頂點(diǎn)作為起點(diǎn)。沿1號(hào)頂點(diǎn)的邊去嘗試其他它未走過(guò)的頂點(diǎn)，首先發(fā)現(xiàn)的是2號(hào)頂點(diǎn)還沒(méi)被走過(guò)，于是來(lái)到了2號(hào)頂點(diǎn)。

再以2號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)嘗試訪(fǎng)問(wèn)其他未走到過(guò)的頂點(diǎn)，這樣又來(lái)到了4號(hào)頂點(diǎn)。

再以4號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)嘗試訪(fǎng)問(wèn)其他未走過(guò)的頂點(diǎn)。但是，此時(shí)在4號(hào)頂點(diǎn)的周?chē)呀?jīng)沒(méi)有其他的頂點(diǎn)了，所以需要返回到2號(hào)頂點(diǎn)。返回到2號(hào)頂點(diǎn)后，發(fā)現(xiàn)沿2號(hào)頂點(diǎn)也不能在訪(fǎng)問(wèn)到其他未走到的點(diǎn)了，此時(shí)又需要返回到1號(hào)頂點(diǎn)。

繼續(xù)以1號(hào)頂點(diǎn)嘗試訪(fǎng)問(wèn)其他頂點(diǎn)，我們來(lái)到了3號(hào)點(diǎn)。以此類(lèi)推，我們最后來(lái)到了5號(hào)點(diǎn)。到此，所以的頂點(diǎn)都走過(guò)了，遍歷結(jié)束

深度優(yōu)先搜索的主要思想是：

首先以一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起始頂點(diǎn)，沿當(dāng)前頂點(diǎn)的邊走到未被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)

當(dāng)沒(méi)有未訪(fǎng)問(wèn)過(guò)的頂點(diǎn)時(shí)，則回到上一個(gè)頂點(diǎn)，繼續(xù)試探訪(fǎng)問(wèn)別的頂點(diǎn)，直到所有的頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)。

顯然，深度優(yōu)先搜索是沿著圖的某一條分支遍歷直至末端，然后回溯，再沿另一條實(shí)現(xiàn)相同的遍歷，直到所以的頂點(diǎn)都被訪(fǎng)問(wèn)完為止。

代碼實(shí)現(xiàn)?

上面的二維數(shù)組中第i行第j列就是表示頂點(diǎn)i到頂點(diǎn)j是否有邊。

1表示有邊，x表示沒(méi)有邊，0表示頂點(diǎn)自己到自己。

我們將這種方法稱(chēng)為 ——? 圖的鄰接矩陣儲(chǔ)存法。?

細(xì)心的朋友可能會(huì)發(fā)現(xiàn)這張圖沿著對(duì)角線(xiàn)全部是0，因?yàn)樯厦孢@張圖是無(wú)向圖。?

所謂無(wú)向圖就是指圖的邊沒(méi)有方向。例如邊 1 - 5 表示 1號(hào)頂點(diǎn)可以到 5號(hào)頂點(diǎn)，5號(hào)頂點(diǎn)也可以到1號(hào)頂點(diǎn)。

接下來(lái)就是解決怎么用深度優(yōu)先搜索來(lái)實(shí)現(xiàn)遍歷了：

void dfs(int cur)				//cur是當(dāng)前所在的頂點(diǎn)編號(hào)
{
	printf("%d", cur);
	sum++;						//每訪(fǎng)問(wèn)一個(gè)點(diǎn)就sum++
	if (sum == n) return;		//所有的頂點(diǎn)都訪(fǎng)問(wèn)過(guò)了
	for (i = 1; i <= n; i++)	//從1到n的頂點(diǎn)依次嘗試，看看有哪些頂點(diǎn)與當(dāng)前頂點(diǎn)cur有邊相連
	{
		//判斷當(dāng)前頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已被訪(fǎng)問(wèn)過(guò)
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//標(biāo)記頂點(diǎn)i已經(jīng)訪(fǎng)問(wèn)過(guò)
				dfs(i);			//從頂點(diǎn)i出發(fā)繼續(xù)遍歷
			}
		}
	}
	return;
}

在上面的代碼中變量 cur 存儲(chǔ)的是當(dāng)前正在遍歷的點(diǎn)，二維數(shù)組e存儲(chǔ)的就是圖的邊（鄰接矩陣），數(shù)組book用來(lái)標(biāo)記哪些頂點(diǎn)已經(jīng)訪(fǎng)問(wèn)過(guò)，變量sum用來(lái)記錄已經(jīng)訪(fǎng)問(wèn)多少個(gè)頂點(diǎn)，變量你存儲(chǔ)的是圖的頂點(diǎn)總個(gè)數(shù)。

完整代碼??

#include <stdio.h>
int book[101], sum, n, e[101][101];
void dfs(int cur)				//cur是當(dāng)前所在的頂點(diǎn)編號(hào)
{
	printf("%d", cur);
	sum++;						//每訪(fǎng)問(wèn)一個(gè)點(diǎn)就sum++
	if (sum == n) return;		//所有的頂點(diǎn)都訪(fǎng)問(wèn)過(guò)了
	for (i = 1; i <= n; i++)	//從1到n的頂點(diǎn)依次嘗試，看看有哪些頂點(diǎn)與當(dāng)前頂點(diǎn)cur有邊相連
	{
		//判斷當(dāng)前頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已被訪(fǎng)問(wèn)過(guò)
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//標(biāo)記頂點(diǎn)i已經(jīng)訪(fǎng)問(wèn)過(guò)
				dfs(i);			//從頂點(diǎn)i出發(fā)繼續(xù)遍歷
			}
		}
	}
	return;
}
 
int main()
{
	int i, j, m, a, b;
	scanf("%d %d", &n, &m);
	//初始化二維矩陣
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j) e[i][j] = 0;
			else e[i][j] = 99999999;	//我們假設(shè)99999999為x
 
	//讀入頂點(diǎn)之間的邊
	for (i = 1; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;	//因?yàn)樵搱D為無(wú)向圖
	}
 
	//從1號(hào)頂點(diǎn)出發(fā)
	book[1] = 1;  //標(biāo)記1號(hào)頂點(diǎn)已經(jīng)訪(fǎng)問(wèn)
	dfs(1);		  //從1號(hào)頂點(diǎn)開(kāi)始遍歷
 
	return 0;
}

到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(一)的文章就介紹到這了,更多相關(guān)C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 圖的遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: