快捷導(dǎo)航

C語言數(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)中常見的有深度優(yōu)先搜索和廣度優(yōu)先搜索。為什么叫深度和廣度呢？其實(shí)是針對(duì)圖的遍歷而言的，請(qǐng)看下面這個(gè)圖：

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

例如上圖就是由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)開始遍歷這個(gè)圖，遍歷就是把圖的每一個(gè)頂點(diǎn)都訪問一次。使用深度優(yōu)先搜索將會(huì)得到如下的結(jié)果。

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

深度優(yōu)先搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

void dfs(int cur)				//cur是當(dāng)前所在的頂點(diǎn)編號(hào)
{
	printf("%d", cur);
	sum++;						//每訪問一個(gè)點(diǎn)就sum++
	if (sum == n) return;		//所有的頂點(diǎn)都訪問過了
	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是否已被訪問過
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//標(biāo)記頂點(diǎn)i已經(jīng)訪問過
				dfs(i);			//從頂點(diǎn)i出發(fā)繼續(xù)遍歷
			}
		}
	}
	return;
}

在上面的代碼中變量 cur 存儲(chǔ)的是當(dāng)前正在遍歷的點(diǎn)，二維數(shù)組e存儲(chǔ)的就是圖的邊（鄰接矩陣），數(shù)組book用來標(biāo)記哪些頂點(diǎn)已經(jīng)訪問過，變量sum用來記錄已經(jīng)訪問多少個(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++;						//每訪問一個(gè)點(diǎn)就sum++
	if (sum == n) return;		//所有的頂點(diǎn)都訪問過了
	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是否已被訪問過
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//標(biāo)記頂點(diǎn)i已經(jīng)訪問過
				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為無向圖
	}
 
	//從1號(hào)頂點(diǎn)出發(fā)
	book[1] = 1;  //標(biāo)記1號(hào)頂點(diǎn)已經(jīng)訪問
	dfs(1);		  //從1號(hào)頂點(diǎn)開始遍歷
 
	return 0;
}

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

您可能感興趣的文章: