圖（二）——圖的遍歷-創(chuàng)新互聯(lián)

目錄

成都創(chuàng)新互聯(lián)是一家專注于網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),柳江網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:柳江等地區(qū)。柳江做網(wǎng)站價(jià)格咨詢:028-86922220

→?圖的遍歷

→?深度優(yōu)先搜索遍歷

↓?基本思想：

↓ →?遞歸深度優(yōu)先搜索遍歷

↓? ? 算法思想：

↓ →非遞歸深度優(yōu)先搜索遍歷

↓? 算法思想：

→??廣度優(yōu)先搜索遍歷

↓??基本思想：

→??算法實(shí)現(xiàn)的綜合應(yīng)用：（無向圖為例）? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?

↓?運(yùn)行結(jié)果：

↓?算法實(shí)現(xiàn)：

↓? →?算法實(shí)現(xiàn)過程中的注意點(diǎn)及解決方法：

↓? 注意點(diǎn)一：

↓? 解決方法：

↓? 注意點(diǎn)二：

↓? 解決方法：

圖的遍歷

??圖的遍歷是從圖中某個(gè)頂點(diǎn)出發(fā)，訪遍圖中其余頂點(diǎn)，且都訪問一次的過程。

? 圖與樹類似，不同的是圖的每個(gè)頂點(diǎn)都有可能與其余所有頂點(diǎn)鄰接，為避免重復(fù)訪問同一個(gè)頂點(diǎn)，在遍歷的過程中應(yīng)標(biāo)記該頂點(diǎn)訪問過。

思考：

對(duì)于圖中有回路，對(duì)于連通圖，如何實(shí)現(xiàn)遍歷只訪問每個(gè)頂點(diǎn)一次，也就是遇到回退的情況或圖中頂點(diǎn)都已完成訪問時(shí)如何確保不會(huì)再次訪問頂點(diǎn)？

設(shè)置一個(gè)標(biāo)志數(shù)組 Visited【】實(shí)現(xiàn)，此數(shù)組用于標(biāo)記所有頂點(diǎn)是否訪問過，初始值為0，如果訪問過，更新此頂點(diǎn)的標(biāo)志為1，這樣遇到上述情況時(shí)，判斷頂點(diǎn)的標(biāo)志數(shù)組是否為1即可解決。

圖的遍歷方法有：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷，兩種遍歷方法對(duì)無向圖，有向圖都適用。通過圖的遍歷可以知道圖是否為連通圖。

深度優(yōu)先搜索遍歷

深度優(yōu)先搜索遍歷和二叉樹的先序遍歷類似，盡可能先對(duì)縱深方向進(jìn)行搜索。

基本思想：

? 先從圖的某個(gè)頂點(diǎn) V0 出發(fā)，訪問頂點(diǎn)，然后依次從V0 各個(gè)未訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷，直到所有和 V0 相通的頂點(diǎn)都被訪問到。如果是非連通圖，上述操作結(jié)束后，需要再選另一個(gè)圖中未被訪問的頂點(diǎn)作為新的出發(fā)點(diǎn)，重復(fù)上述操作。

?

?深度優(yōu)先搜索遍歷的結(jié)果為：A B D F C G E H I 。

一個(gè)頂點(diǎn)可能會(huì)有多個(gè)鄰接點(diǎn)，訪問次序不同，所以圖的遍歷的序列不唯一。

對(duì)于鄰接矩陣存儲(chǔ)結(jié)構(gòu)的圖，適合稠密圖 ，遍歷時(shí)，需要檢查n^2個(gè)元素，時(shí)間復(fù)雜度為O（n^2）。

鄰接表存儲(chǔ)結(jié)構(gòu)的圖，適合稀疏圖,找鄰接點(diǎn)只需在邊表中所有邊結(jié)點(diǎn)檢查一遍，時(shí)間為O（e），時(shí)間復(fù)雜度為O（n+e）。

遞歸深度優(yōu)先搜索遍歷

?采用遞歸的方式遍歷，如果訪問到頂點(diǎn)A1，根據(jù)判斷條件知其沒有鄰接點(diǎn)(無法深度優(yōu)先搜索遍歷)，需要回退到上一個(gè)頂點(diǎn)A，繼續(xù)查找A的其余鄰接點(diǎn)A2，，，

算法思想：

?從一個(gè)頂點(diǎn)v出發(fā)

1、訪問頂點(diǎn)，標(biāo)記此頂點(diǎn)訪問過

2、從鄰接矩陣中找到頂點(diǎn)位置，依次選擇其鄰接點(diǎn)且并判斷是否訪問過，進(jìn)行深度遍歷。

遍歷偽代碼：

void DFS(Graph g,int v0)
{
    visit(vo);            //訪問頂點(diǎn)
    visited[v0]=1;        //標(biāo)記訪問過頂點(diǎn)
    w=FirstAdjVex(g,vo);   //查找vo的第一個(gè)鄰接點(diǎn)
    while(w!=-1)          // 鄰接點(diǎn)存在
         {
             if(!visited[w])     //鄰接點(diǎn)未訪問過
                DFS(g,w);
             w=NextAdjVex(g,vo,w);  //  vo的下一個(gè)鄰接點(diǎn)
          }
}
void TraverseG(Graph g)
{
     for(v=0;v
非遞歸深度優(yōu)先搜索遍歷

二叉樹遍歷時(shí)已經(jīng)知道，對(duì)于遞歸遍歷可以通過棧轉(zhuǎn)化為非遞歸遍歷的形式。

? 算法思想：

1、棧初始化

2、訪問頂點(diǎn)，標(biāo)記訪問過，該頂點(diǎn)入棧

3、當(dāng)棧不為空時(shí)：

1 、取棧頂頂點(diǎn)的位置，存在未被訪問的鄰接點(diǎn)w

2、訪問頂點(diǎn)w，標(biāo)記訪問，w頂點(diǎn)入棧（便于查找w頂點(diǎn)的其他鄰接點(diǎn)）然后在棧不為空的條件下重復(fù)上述操作。

3、否則，當(dāng)前頂點(diǎn)出棧，（表明頂點(diǎn)的鄰接點(diǎn)都訪問過，或該棧頂頂點(diǎn)沒有鄰接點(diǎn)，出棧，繼續(xù)尋找現(xiàn)在棧頂頂點(diǎn)的鄰接點(diǎn)）。

廣度優(yōu)先搜索遍歷
基本思想：

?廣度優(yōu)先搜索遍歷與二叉樹的層次遍歷類似，從某個(gè)頂點(diǎn)出發(fā)開始訪問，先訪問該頂點(diǎn)的所有鄰接點(diǎn)，然后根據(jù)其鄰接點(diǎn)的訪問順序再訪問各自的所有鄰接點(diǎn)，直到所有與頂點(diǎn)路徑相通的頂點(diǎn)都被訪問到。圖中若有未被訪問到，另選該頂點(diǎn)作為出發(fā)點(diǎn)。

廣度優(yōu)先搜索遍歷的結(jié)果為：A B C D E F G H I 。

算法思想：

? 根據(jù)隊(duì)列的特點(diǎn)，先進(jìn)先出，訪問頂點(diǎn)時(shí)入隊(duì)，并標(biāo)記訪問過，然后出隊(duì)，隊(duì)頭元素出隊(duì)時(shí)，依次將其未被訪問到的頂點(diǎn)訪問并入隊(duì)，每個(gè)頂點(diǎn)都入隊(duì)一次。

? 從V0頂點(diǎn)出發(fā)

? 1、隊(duì)初始化

? 2、訪問V0頂點(diǎn)，標(biāo)記訪問過，并入隊(duì)

? 3、當(dāng)隊(duì)不為空時(shí)：

? 出隊(duì)；

? 將出隊(duì)的頂點(diǎn)所有未被訪問過的頂點(diǎn)訪問，標(biāo)記并入隊(duì)。

算法實(shí)現(xiàn)的綜合應(yīng)用：（無向圖為例）? ? ? ?
? ? ? ? ? ? ? ? ? ? 運(yùn)行結(jié)果：

??

?

算法實(shí)現(xiàn)：
#include#include#define MAXVEX 20
typedef struct
{
	int arcs[MAXVEX][MAXVEX];
	char vex[MAXVEX];
	int vexnum;
	int arcnum;
}AdjMatrix;
//對(duì)圖的頂點(diǎn)初始化
AdjMatrix* Init()
{
	AdjMatrix* G = (AdjMatrix*)malloc(sizeof(AdjMatrix));
	if (G == NULL)
		printf("申請(qǐng)內(nèi)存錯(cuò)誤");
	for (int i = 0; iarcs[i][j] = 0;
	}
	for (int i = 0; i< MAXVEX; i++)
		G->vex[i] = 0;
	G->vexnum = 0;
	G->arcnum = 0;
	return G;
}
//===================================  鄰接矩陣存儲(chǔ)結(jié)構(gòu)創(chuàng)建圖  =========================
//查找匹配的頂點(diǎn)在矩陣中的位置
int LocateVex(AdjMatrix* G, char v)
{
	int i;
	for (i = 1; i<= G->vexnum; i++)
	{
		if (G->vex[i] == v)
			return i;
	}
	return 0; 
}
AdjMatrix* Create()  
{    
	AdjMatrix* G=Init();
	int i, j, k;
	char vex1, vex2;
	printf("----輸入圖的頂點(diǎn)數(shù)與邊數(shù)-----\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	printf("-----依次輸入圖中%d個(gè)頂點(diǎn)------\n", G->vexnum);
	for (i = 1; i<=G->vexnum; i++)
	{
		scanf(" %c",&(G->vex[i]));           //注意點(diǎn)一：
	}
	printf("-----輸入圖中%d條邊-----\n", G->arcnum);
	for (k = 1; k<= G->arcnum; k++)
	{
		printf("第%d條邊：\n ", k);
		scanf(" %c", &vex1);
		scanf(" %c", &vex2);
		i = LocateVex(G, vex1);
		j = LocateVex(G, vex2);
		G->arcs[i][j] = 1;
		G->arcs[j][i] = 1;
	}
	printf("=================》鄰接矩陣建立圖完成  ================《\n");
	return G;
}
//====================================  鄰接矩陣遞歸深度搜索遍歷  ======================
void DFS(AdjMatrix*G, int v)      
{
	int i = 0;
	static int visited[20];          //注意點(diǎn)二：
	printf("%c ", G->vex[v]);
	visited[v] = 1;
	for (i = 1; i<= G->vexnum; i++)
	{
		if (G->arcs[v][i] != 0 && visited[i] != 1)
			DFS(G, i);
	}
}
//========================================  棧  =======================================
//定義結(jié)點(diǎn)結(jié)構(gòu)
typedef struct Node
{
	char data;
	struct Node* next;
}Slstacktype;
//初始化棧頭指針
Slstacktype* Initstack()
{
	Slstacktype* top = (Slstacktype*)malloc(sizeof(Slstacktype));
	top->next = NULL;
	return top;
}
//進(jìn)棧
Slstacktype* Push(Slstacktype* top,char vex)
{
	Slstacktype* p=(Slstacktype*)malloc(sizeof(Slstacktype));
	if (p == NULL)
		return NULL;
	p->data = vex;
	p->next = top->next;
	top->next = p;
	return top;
}
//出棧
Slstacktype* Pop(Slstacktype* top)
{
	Slstacktype* q;
	if (top->next == NULL)  //判斷棧是否為空
		return NULL;
	q = top->next;
	top->next = q->next;
	free(q);
	return top;
}
//===================================  非遞歸鄰接矩陣存儲(chǔ)結(jié)構(gòu)的深度搜索遍歷  =============
//取棧頂頂點(diǎn)的位置
int include_stack(AdjMatrix* G, Slstacktype* top)  
{
	int i;
	for (i = 1; i<= G->vexnum; i++)
	{
		if (G->vex[i] == top->next->data)
			return i;
	}
	return 0;
}
void DFS_stack(AdjMatrix*G,int v)
{
	int i;
	Slstacktype* top = Initstack(); //棧的初始化
	static int visited[20];         //定義靜態(tài)的標(biāo)志數(shù)組
	printf("%c ", G->vex[v]);
	visited[v] = 1;
	Push(top, G->vex[v]);
	while (top->next != NULL)
	{
		v = include_stack(G, top);
		for (i = 1; i<= G->vexnum; i++)
		{
			if (G->arcs[v][i] != 0 && visited[i] != 1)
			{
				printf("%c ", G->vex[i]);
				visited[i] = 1;
				Push(top, G->vex[i]);
				break;
			}
		}
		if (i >G->vexnum)         //頂點(diǎn)的鄰接點(diǎn)都訪問過，或沒有鄰接點(diǎn)時(shí)退棧頂結(jié)點(diǎn)
		{
		top = Pop(top);
		}
	}
}

//===========================================  隊(duì)列 ======================================
typedef struct Node2
{
	char data;
	struct Node2* next;
}QNode;
typedef struct
{
	QNode* front;
	QNode* rear;
}LQNode;
//隊(duì)的初始化
LQNode* Init_Q()
{
	LQNode* p = (LQNode*)malloc(sizeof(LQNode));
	QNode* q = (QNode*)malloc(sizeof(QNode));
	p->front = p->rear = q;
	q->next = NULL;
	return p;
}
//入隊(duì)
void Push_Q(LQNode* p, char vex)
{
	QNode* q = (QNode*)malloc(sizeof(QNode));
	if (q == NULL)
		printf("申請(qǐng)空間錯(cuò)誤");
	q->data = vex;
	q->next = NULL;
	p->rear->next = q;
	p->rear = q;
}
//出隊(duì)
char Pop_Q(LQNode* p)
{
	char vex;
	QNode* q;
	if (p->front == p->rear)
		return ;
	q = p->front->next;
	p->front->next = q->next;
	vex = q->data; 
	if (p->front->next == NULL)
		p->rear = p->front;
	free(q);
	return vex;
}
//========================================== 鄰接矩陣的廣度優(yōu)先搜素遍歷 ====================
int include_Q(AdjMatrix* G, char vex)   //取出隊(duì)頂點(diǎn)在鄰接矩陣中的位置
{
	for (int i = 1; i<= G->vexnum; i++)
	{
		if (G->vex[i] == vex)
			return i;
	}
	return 0;
}
void BFS(AdjMatrix* G, int v)
{
	static visited[20];
	LQNode* p = Init_Q();
	printf("%c ", G->vex[v]);
	visited[v] = 1;
	Push_Q(p, G->vex[v]);
	while (p->front->next!=NULL)
	{
		int i;
		v = include_Q(G,Pop_Q(p));
		for (i = 1; i<= G->vexnum; i++)
		{
			if (G->arcs[v][i] != 0 && visited[i] != 1)
			{
				printf("%c ", G->vex[i]);
				visited[i] = 1;
				Push_Q(p, G->vex[i]);
			}
		}
	}
}
//========================================   打印鄰接矩陣  ==============================
void print(AdjMatrix* G)
{
	for (int i = 1; i<= G->vexnum; i++)
	{
		for (int j = 1; j<= G->vexnum; j++)
		{
			printf("%d ", G->arcs[i][j]);
		}
		printf("\n");
	}
}
main()
{
	int v;
	printf("==============》 鄰接矩陣存儲(chǔ)結(jié)構(gòu)創(chuàng)建圖 《===========\n");
	AdjMatrix* G = Create();  
	printf("==============》  打印鄰接矩陣 《============\n");
	print(G);
	printf("\n");
	printf("----輸入遍歷起始位置-----\n");
	scanf("%d", &v);
	printf("==============》  遞歸 深度搜索遍歷  《========== \n");
	DFS(G, v);
	printf("\n");
	printf("==============》 非遞歸 深度搜索遍歷 《========== \n");
	DFS_stack(G, v);
	printf("\n");
	printf("==============》  廣度優(yōu)先搜索遍歷   《==============\n ");
	BFS(G, v);
	printf("\n");
}
算法實(shí)現(xiàn)過程中的注意點(diǎn)及解決方法：
注意點(diǎn)一：

再多次用scanf（）函數(shù)輸入值時(shí)，輸入的是字符類型的值時(shí)，需要考慮scanf函數(shù)的問題

? 解決方法：

可以在 %c前面空格用于接收留在緩沖區(qū)中的空格、回車等符號(hào)

注意點(diǎn)二：

?定義的標(biāo)志數(shù)組，需要初始化為0，每次訪問過后需要更新為1，然而在遞歸函數(shù)中，每一次調(diào)用都會(huì)重新初始化數(shù)組，然后就會(huì)造成死循環(huán)的情況（可以試試寫寫，印象更深）。

解決方法：

可以定義一個(gè)大一點(diǎn)的數(shù)組，利用靜態(tài)數(shù)組未初始化就會(huì)給所有的數(shù)組元素賦初值0，就很好的解決這個(gè)問題。

?靜態(tài)數(shù)組：靜態(tài)數(shù)組的長(zhǎng)度是預(yù)先定義好的,在整個(gè)程序中,一旦給定大小后就無法改變。 靜態(tài)數(shù)組在內(nèi)存中位于棧區(qū),是在定義時(shí)就已經(jīng)在棧上分配了固定大小,在運(yùn)行時(shí)這個(gè)大小不能改變,在函數(shù)執(zhí)行完以后,系統(tǒng)自動(dòng)銷毀; 如:int a[10]; 雖然c語(yǔ)言規(guī)定,只有靜態(tài)存儲(chǔ)的數(shù)組才能初始化,但一般的c編譯系統(tǒng)都允許對(duì)動(dòng)態(tài)存儲(chǔ)的數(shù)組賦初值。靜態(tài)存儲(chǔ)的數(shù)組如果沒有初始化,系統(tǒng)自動(dòng)給所有的數(shù)組元素賦0。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：圖（二）——圖的遍歷-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://muchs.cn/article30/dhgppo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、網(wǎng)站維護(hù)、營(yíng)銷型網(wǎng)站建設(shè)、搜索引擎優(yōu)化、移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)