国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<th id="cj4pb"></th>

數(shù)據(jù)結(jié)構(gòu) 第六章圖——圖的遍歷

2年前作者：0202ohh分類：Toy博客閱讀(23)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 第六章圖——圖的遍歷。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

6.5 圖的遍歷

在前面我們知道，樹(shù)是一種非線性結(jié)構(gòu)，為了方便它在計(jì)算機(jī)中的存儲(chǔ)，對(duì)樹(shù)進(jìn)行遍歷使它線性化。
而圖同樣也是一種非線性結(jié)構(gòu)，但是圖又是一種不同于樹(shù)的多對(duì)多結(jié)構(gòu)，所以在前面我們將其轉(zhuǎn)換為了多個(gè)一對(duì)多的結(jié)構(gòu)來(lái)描述它的存儲(chǔ)結(jié)構(gòu)。

圖的遍歷同樹(shù)類似，也是從某一個(gè)頂點(diǎn)出發(fā)，按照某種方法對(duì)圖中所有頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次。圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝完P(guān)鍵路徑等算法的基礎(chǔ)。

因?yàn)閳D的任一頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接，為了避免同一頂點(diǎn)被訪問(wèn)多次，在遍歷圖的過(guò)程中，必須記下每個(gè)已訪問(wèn)過(guò)的頂點(diǎn)。

通常有兩條遍歷的圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。

6.5.1 深度優(yōu)先搜索

1. 深度優(yōu)先搜索遍歷的過(guò)程

深度優(yōu)先搜索（Depth First Search，DFS）遍歷類似于樹(shù)的先序遍歷。我們也可以理解一下深度的概念，也就是樹(shù)中深度的概念，但這需要圖要有跟樹(shù)相似的形狀。何謂深度優(yōu)先？就是從某個(gè)頂點(diǎn)一直往下，先不管與它處于同一層次的其它頂點(diǎn)。

對(duì)于一個(gè)連通圖，深度優(yōu)先搜索遍歷的過(guò)程如下：

從圖中某個(gè)頂點(diǎn) $v$ 出發(fā)，訪問(wèn)頂點(diǎn) $v$
找到剛訪問(wèn)過(guò)的頂點(diǎn)的第一個(gè)未被訪問(wèn)的鄰接點(diǎn)，接著訪問(wèn)該鄰接點(diǎn)；然后以該鄰接點(diǎn)為新的頂點(diǎn)，重復(fù)上述步驟，直到剛訪問(wèn)過(guò)的頂點(diǎn)沒(méi)有未被訪問(wèn)的鄰接點(diǎn)。
經(jīng)過(guò)了第二步后，由 $v$ 的第一個(gè)未被訪問(wèn)的鄰接點(diǎn)延伸的后面的頂點(diǎn)都被訪問(wèn)了（但不確定這條延伸鏈上每個(gè)頂點(diǎn)的其它鄰接點(diǎn)是否被訪問(wèn)），此時(shí)還停留在“最下面”的那個(gè)頂點(diǎn)，這時(shí)我們需要返回到前一個(gè)訪問(wèn)過(guò)的且仍有未被訪問(wèn)的鄰接點(diǎn)的頂點(diǎn)。若停留頂點(diǎn)的前面一個(gè)頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)過(guò)，則繼續(xù)“向上”回溯。
重復(fù)步驟（2）和（3），直至圖中所有頂點(diǎn)都被訪問(wèn)過(guò)，搜索結(jié)束。

下面舉一個(gè)例子，來(lái)說(shuō)明該搜索方法，如下圖：數(shù)據(jù)結(jié)構(gòu) 第六章圖——圖的遍歷
如果我們要遍歷該圖，按照上述的步驟進(jìn)行，那么即：

從頂點(diǎn) $v_{1}$ 出發(fā)，訪問(wèn) $v_{1}$ （也可從其它任一頂點(diǎn)出發(fā)）
選擇 $v_{1}$ 未被訪問(wèn)的第一個(gè)鄰接點(diǎn) $v_{2}$ （也可以是 $v_{3}$ ），訪問(wèn) $v_{2}$ 。又以 $v_{2}$ 為新頂點(diǎn)，那么這條延伸鏈則為： $v_{1}\rightarrow v_{2}\rightarrow v_{4}\rightarrow v_{8}\rightarrow v_{5}$ ，因?yàn)?span id="n5n3t3z" class="katex--inline"> $v_{5}$ 的鄰接點(diǎn)都已被訪問(wèn)過(guò)，最后停留在 $v_{5}$ 。
此時(shí)我們需要回溯，找到前面頂點(diǎn)的未被訪問(wèn)過(guò)的鄰接點(diǎn)。 $v_5\rightarrow v_{8}$ , $v_{8}\rightarrow v_{4}$ , $v_{4}\rightarrow v_{2}$ ，都沒(méi)有找到未被訪問(wèn)的鄰接點(diǎn)，最后 $v_{2}\rightarrow v_{1}$ ， $v_{1}$ 有未被訪問(wèn)的鄰接點(diǎn)，搜索又從 $v_{1}\rightarrow v_{3}$ ，繼續(xù)進(jìn)行下去。
最后，我們得到的訪問(wèn)序列為： $v_{1}\rightarrow v_{2}\rightarrow v_{4}\rightarrow v_{8}\rightarrow v_{5}\rightarrow v_{3}\rightarrow v_{6}\rightarrow v_{7}$ 。

因?yàn)槲覀儽闅v是求解圖的連通性問(wèn)題，若訪問(wèn)結(jié)束沒(méi)有未被訪問(wèn)的結(jié)點(diǎn)，則是連通圖；若有，則是非連通圖。

對(duì)于上述深度優(yōu)先搜索的結(jié)果，我們可以構(gòu)造一棵以 $v_{1}$ 為根的樹(shù)，稱為深度優(yōu)先生成樹(shù)，如下圖：數(shù)據(jù)結(jié)構(gòu) 第六章圖——圖的遍歷

2. 深度優(yōu)先搜索遍歷的算法實(shí)現(xiàn)

由于遍歷的過(guò)程需要判斷搜索的頂點(diǎn)是否已被訪問(wèn)，所以我們應(yīng)該想辦法在搜索的時(shí)候判斷每個(gè)是否已被訪問(wèn)。已知，每個(gè)頂點(diǎn)只有兩種狀態(tài)：已被訪問(wèn)和未被訪問(wèn)。所以如果該頂點(diǎn)未被訪問(wèn)，只需將其狀態(tài)改為已被訪問(wèn)就行。而該判斷方法比較簡(jiǎn)單，所以我們可以考慮用一維數(shù)組visited來(lái)存儲(chǔ)每個(gè)頂點(diǎn)的狀態(tài)。若未被訪問(wèn)，則其值為false；若已訪問(wèn)，則其值為true。在這里可以使用布爾類型來(lái)實(shí)現(xiàn)。 $\rightarrow$ 布爾數(shù)據(jù)類型

算法——深度優(yōu)先搜索遍歷連通圖

算法分析：

首先我們將數(shù)組visited初始化，將每個(gè)頂點(diǎn)的狀態(tài)值都賦為false
再?gòu)脑擁旤c(diǎn)延伸往下，都是訪問(wèn)的該延伸鏈中每個(gè)頂點(diǎn)的第一個(gè)鄰接點(diǎn)，最后再?gòu)脑撗由戽溩詈笠粋€(gè)頂點(diǎn)回溯。從這里我們可以看到，要訪問(wèn)一個(gè)頂點(diǎn)的全部鄰接點(diǎn)，是從最下面的那個(gè)頂點(diǎn)開(kāi)始，逐層向上。而這，不就是一個(gè)遞歸的過(guò)程嗎。而每個(gè)頂點(diǎn)要訪問(wèn)所有鄰接點(diǎn)，肯定也是一個(gè)循環(huán)結(jié)構(gòu)。
然后我們需要注意的是循環(huán)和遞歸結(jié)束的條件。循環(huán)結(jié)束的條件不用說(shuō)，肯定是鄰接點(diǎn)訪問(wèn)完后。而遞歸結(jié)束的條件就是循環(huán)結(jié)束，循環(huán)結(jié)束后向上回溯，直至第一個(gè)頂點(diǎn) $v$ 的循環(huán)結(jié)束
至此，該連通圖的所有頂點(diǎn)全部都被訪問(wèn)過(guò)

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

bool visited[MVNum];
void DFS(Graph G,int v)
{
	printf("%d",&v);    				//打印出每個(gè)頂點(diǎn)，方便最后檢查是否全部頂點(diǎn)已被訪問(wèn)
	visited[v]=ture;
	for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
		if(!visited[w])				    //如果該鄰接點(diǎn)未被訪問(wèn)
			DFS(G,w);
}

其中FirstAdjVex和NextAdjVex函數(shù)要根據(jù)具體的圖的存儲(chǔ)結(jié)構(gòu)來(lái)設(shè)計(jì)。

算法——深度優(yōu)先搜索遍歷非連通圖

算法分析：

非連通圖我們可以理解為是由兩個(gè)及兩個(gè)以上的圖構(gòu)成的
由此，該算法不能向遍歷連通圖那樣，從任一一個(gè)頂點(diǎn)出發(fā)就可遍歷所有頂點(diǎn)。在此算法中，若采用上述算法，則只能遍歷“一個(gè)圖”，其它圖就不能遍歷
于是，我們只有對(duì)所有頂點(diǎn)做一個(gè)循環(huán)，只要有未被訪問(wèn)的頂點(diǎn)，就從該頂點(diǎn)出發(fā)調(diào)用上述算法

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

void DFSTraverse(Graph G)
{
	for(int v=0;v<G.vexnum;v++)
		visited[v]=false;
	for(int v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);

下面分別采用兩種不同的圖結(jié)構(gòu)來(lái)實(shí)現(xiàn)深度優(yōu)先搜索。有了上述過(guò)程的理解，我們直接給出代碼實(shí)現(xiàn)。

算法——采用鄰接矩陣表示圖的深度優(yōu)先搜索遍歷

void DFS_AM(AMGraph G,int v)
{
	for(int i=0;i<vexnum;i++)
		visited[i]=false;
	printf("%d ",&v);
	visited[v]=true;
	for(w=0;w<G.vexnum;w++)
		if((G.arcs[v][w]!=0)&&!visited[w])
			DFS_AM(G,w);
}

算法——采用鄰接表表示圖的深度優(yōu)先搜索遍歷

void DFS_AL(ALGraph G,int v)
{
	ArcNode *p;
	for(int i=0;i<G.vexnum;i++)
		visited[i]=false;
	printf("%d ",&v);
	visited[v]=true;
	p=G.vertices[v].firstarc;
	while(p!=NUll)
	{
		w=p->adjvex;
		if(!visited[w])
			DFS_AL(G,w);
		p=p->nextarc;
	}
}

3. 對(duì)深度優(yōu)先搜索算法的分析

在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用依次DFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問(wèn)，就不再?gòu)乃霭l(fā)進(jìn)行搜索。因此，遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程，其耗費(fèi)時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。

若用鄰接矩陣：時(shí)間復(fù)雜度為 $O(n^2)$ ，n為頂點(diǎn)數(shù)
若用鄰接表：時(shí)間復(fù)雜度為 $O (e)$ ，e為邊數(shù)

6.5.2 廣度優(yōu)先搜索

廣度優(yōu)先搜索和深度優(yōu)先搜索正好相反，如果說(shuō)深度優(yōu)先搜索是“豎”著來(lái)，那么廣度優(yōu)先搜索就是“橫”著來(lái)。

1. 廣度優(yōu)先搜索遍歷的過(guò)程

該過(guò)程類似于樹(shù)的按層次遍歷

依舊是從圖中的某個(gè)頂點(diǎn) $v$ 出發(fā)，并訪問(wèn) $v$
依次訪問(wèn) $v$ 的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)
再?gòu)泥徑狱c(diǎn)出發(fā)，依次訪問(wèn)它們的鄰接點(diǎn)，并使先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)先于后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)。重復(fù)該步驟，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到

下圖為對(duì)無(wú)向圖G4廣度優(yōu)先搜索遍歷的一個(gè)示例過(guò)程：數(shù)據(jù)結(jié)構(gòu) 第六章圖——圖的遍歷

由此我們得到的訪問(wèn)序列為： $v_{1}\rightarrow v_{2}\rightarrow v_{3}\rightarrow v_{4}\rightarrow v_{5}\rightarrow v_{6}\rightarrow v_{7}\rightarrow v_{8}$

而上述圖也可作為廣度優(yōu)先搜索的一棵廣度優(yōu)先生成樹(shù)。

2. 廣度優(yōu)先搜索遍歷的算法實(shí)現(xiàn)

算法分析：

在前面我們說(shuō)到，在廣度優(yōu)先搜索中要使先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)先于后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)被訪問(wèn)，但前提是先訪問(wèn)了這兩個(gè)頂點(diǎn)，再去按照一定次序分別訪問(wèn)它們的鄰接點(diǎn)
如果我們把它想象成樹(shù)的結(jié)構(gòu)那么就好理解了，上一條的意思就是在每一層一定要以從左到右的次序訪問(wèn)頂點(diǎn)
在這里是一層一層從上到下訪問(wèn)的，所以遞歸是行不通的，而對(duì)訪問(wèn)的次序又有一定的要求。我們?cè)賮?lái)捋一捋思路：假如從 $v_{1}$ 出發(fā)，再訪問(wèn)它的鄰接點(diǎn) $v_{2},v_{3}$ （先訪問(wèn)的是 $v_{2}$ ），然后再訪問(wèn) $v_{2},v_{3}$ 的鄰接點(diǎn)（先訪問(wèn)的是 $v_{2}$ 的鄰接點(diǎn)，也就是 $v_{4},v_{5}$ ，再訪問(wèn) $v_{3}$ 的鄰接點(diǎn)也就是， $v_{6},v_{7}$ ）。由于它們?cè)L問(wèn)有一定的次序，因此按照前面深度優(yōu)先搜索的算法中某些步驟是很麻煩的
我們?cè)賹⑺囊?guī)則總結(jié)以下，也就是先“到”先訪問(wèn)，看到這里是否覺(jué)得很熟悉？沒(méi)錯(cuò)，這就是隊(duì)列的特點(diǎn)，根據(jù)這個(gè)規(guī)則，我們就可以引入隊(duì)列，那么就十分方便了，如果隊(duì)列有點(diǎn)忘了，那么可以復(fù)習(xí)一下: $\rightarrow$ 隊(duì)列
于是，我們可以利用出隊(duì)和進(jìn)隊(duì)的方式來(lái)進(jìn)行有先后次序的訪問(wèn)

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

typedef struct
{
	QElemType *base;
	int front;
	int rear;
}SqQueue;

void InitQueue(SqQueue &q)
{
	base=(QElemType*)malloc(MVNum*sizeof(QElemType));
	q.front=q.rear=0;
}

void EnQueue(SqQueue &q,QElemType e)
{
	if(q.rear+1)%MVNum=q.front;
		return;
	q.base[q.rear]=e;
	q.rear=(q.rear+1)%MVNum;
}

void DeQueue(SqQueue &q,QElemType &e)
{
	if(q.front==q.rear)
		return;
	e=q.base[q.front];
	q.front=(q.front+1)%MVNum;
}




bool visited[MVNum];
void BFS(Graph G,int v)
{
	for(int i=0;i<G.vexnum;i++)
		visited[i]=false;
	printf("%d ",&v);
	visited[v]=true;
	Initiate(Q);
	Enqueue(Q,v);
	while(!QueueEmpty(Q))			//隊(duì)列非空
	{
		Dequeue(Q,u);				//隊(duì)頭元素置為u
		for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex)
			if(!visited[w])
			{
				printf("%d ",&w);
				visited[w]=true;
				Enqueue(Q,w);		
			}
	}
}

根據(jù)上述算法，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊找鄰接點(diǎn)的過(guò)程，因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同。

總結(jié)

圖的遍歷其實(shí)并不難，關(guān)鍵是我們知道為什么要去遍歷圖：是求解圖的連通性問(wèn)題、拓?fù)渑判蚝完P(guān)鍵路徑等算法的基礎(chǔ)。

遍歷圖可以從兩個(gè)方向去遍歷，即深度和廣度。顧名思義，深度就是從上到下，廣度就是從左到右。但深度又不是單純的從上到下，它是從某個(gè)頂點(diǎn)出發(fā)，延該頂點(diǎn)的第一個(gè)鄰接點(diǎn)及該鄰接點(diǎn)的第一個(gè)鄰接點(diǎn)等等繼續(xù)往下延伸，形成了一條延伸鏈，直到該延伸鏈最下面的那個(gè)頂點(diǎn)沒(méi)有未被訪問(wèn)的鄰接點(diǎn)，最后再由該延伸鏈向上回溯。而廣度，是要把圖看成樹(shù)狀的，一層一層從左到右地去遍歷。

對(duì)于不同的圖的結(jié)構(gòu)，遍歷的算法又不同，因此因根據(jù)實(shí)際情況來(lái)操作。

這兩個(gè)遍歷方法并沒(méi)有好壞之分，只是對(duì)于頂點(diǎn)訪問(wèn)的順序不同。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-473802.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) 第六章圖——圖的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

數(shù)據(jù)結(jié)構(gòu)與算法分析第六章圖作業(yè)講解
?參考教材：《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版第2版）》嚴(yán)蔚敏，李冬梅，吳偉民編著，人民郵電出版社，2022年版。截圖未標(biāo)明出處均為原創(chuàng)或取自《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版第2版）》~ ? 本文對(duì)應(yīng)的作業(yè)題講解視頻： ? 數(shù)據(jù)結(jié)構(gòu)與算法分析作業(yè)講解視頻合集 https://www.bilibili.com/video/BV1N
2024年02月03日
瀏覽(23)
數(shù)據(jù)結(jié)構(gòu) | 圖的遍歷
使用鄰接矩陣法存儲(chǔ)圖的信息，其中一維矩陣 Vexs[] 存儲(chǔ)節(jié)點(diǎn)信息二維矩陣?Edges[][] 存儲(chǔ)邊的信息一維矩陣 visited[] 記錄當(dāng)前節(jié)點(diǎn)是否被訪問(wèn)過(guò)，用于后面的遍歷本文所使用的圖的結(jié)構(gòu)如下：對(duì)應(yīng)的 Vexs[] 為：A,B,C,D,E,F（對(duì)應(yīng)的數(shù)組下標(biāo)從0到5）對(duì)應(yīng)的?Edges[][] 如下：圖的
2024年02月04日
瀏覽(28)
數(shù)據(jù)結(jié)構(gòu)--5.3圖的遍歷（廣度優(yōu)先遍歷）
廣度優(yōu)先遍歷： ? ? ? ? 廣度優(yōu)先遍歷（BreadthFirstSearch），又稱為廣度優(yōu)先搜索，簡(jiǎn)稱BFS。要實(shí)現(xiàn)對(duì)圖的廣度遍歷，我們可以利用隊(duì)列來(lái)實(shí)現(xiàn)。 ?（參考隊(duì)列）（上述為結(jié)構(gòu)）
2024年02月10日
瀏覽(21)
【數(shù)據(jù)結(jié)構(gòu)】圖的廣度優(yōu)先遍歷
廣度優(yōu)先遍歷，類似于樹(shù)的層次遍歷，又是熟悉的隊(duì)列實(shí)現(xiàn)。首先將第一個(gè)頂點(diǎn)添加到隊(duì)列中，然后講該頂點(diǎn)的所有鄰接頂點(diǎn)都加入隊(duì)列中，再將該頂點(diǎn)輸出。如此重復(fù)直到遍歷完整個(gè)圖。 Q:隊(duì)列，用于存放頂點(diǎn)。 front,rear:隊(duì)頭和隊(duì)尾指針，用于入隊(duì)和出隊(duì)。 p:工作指針，用
2024年02月05日
瀏覽(19)
【數(shù)據(jù)結(jié)構(gòu)】圖的存儲(chǔ)與遍歷
圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E) 在有向圖中，頂點(diǎn)對(duì)x, y是有序的，頂點(diǎn)對(duì)x，y稱為頂點(diǎn)x到頂點(diǎn)y的一條邊(弧)，x, y和y, x是兩條不同的邊。在無(wú)向圖中，頂點(diǎn)對(duì)(x, y)是無(wú)序的，頂點(diǎn)對(duì)(x,y)稱為頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊，這條邊沒(méi)有特定方向，
2024年02月22日
瀏覽(19)
【數(shù)據(jù)結(jié)構(gòu)】圖的定義，存儲(chǔ)，遍歷
??專欄【數(shù)據(jù)結(jié)構(gòu)】 ??喜歡的詩(shī)句：更喜岷山千里雪三軍過(guò)后盡開(kāi)顏。 ??音樂(lè)分享【Dream It Possible】大一同學(xué)小吉，歡迎并且感謝大家指出我的問(wèn)題?? 目錄 ??前言 ??圖的定義? ???????有向完全圖 ??????無(wú)向完全圖 ??存儲(chǔ)結(jié)構(gòu) ??????鄰接矩陣? ??代碼
2024年02月06日
瀏覽(18)
【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建與遍歷
圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。線性表：線性關(guān)系，由直接前驅(qū)和直接后繼組成。樹(shù) ：層次關(guān)系，由父結(jié)點(diǎn)和孩子結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)最多有一個(gè)父結(jié)點(diǎn)（根
2023年04月22日
瀏覽(22)
王道計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言復(fù)現(xiàn)-第六章-隊(duì)列
?這篇文章收錄了王道考研課程中涉及的數(shù)據(jù)結(jié)構(gòu)的所有代碼。此外，本博客可能會(huì)添加一些額外的代碼（不僅限于王道考研），因?yàn)?08考試中會(huì)頻繁考察一些冷門(mén)的知識(shí)點(diǎn)，所以這篇博客會(huì)涵蓋所有相關(guān)的代碼。這也是我數(shù)據(jù)結(jié)構(gòu)的第一輪復(fù)習(xí)，希望能與大家共同進(jìn)步。由
2024年01月21日
瀏覽(25)
大話數(shù)據(jù)結(jié)構(gòu)-圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷
??圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。 ??深度優(yōu)先遍歷（Depth First Search），也稱為深度優(yōu)先搜索，簡(jiǎn)稱DFS，深度優(yōu)先遍歷，是指從某一個(gè)頂點(diǎn)開(kāi)始，按照一定的規(guī)則，訪問(wèn)并記錄下一個(gè)未訪問(wèn)頂點(diǎn)。對(duì)于非連通圖，則是按連通分量，采用同一規(guī)則進(jìn)行深度優(yōu)
2024年02月04日
瀏覽(24)
(超詳細(xì))C++圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷（數(shù)據(jù)結(jié)構(gòu)）
? ? ? ? 根據(jù)下圖，編寫(xiě)代碼實(shí)現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。 ?? ??????按照英文字母順序，以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先遍歷。遍歷的順序從頂點(diǎn)a開(kāi)始。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列。 ? （1）從頂點(diǎn)a，
2024年02月08日
瀏覽(28)