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

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷

2年前作者：冧軒在努力分類(lèi)：Toy博客閱讀(24)違法舉報(bào)

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

一、圖

1.圖的概念

圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通過(guò)表示為G(V,E)，其中，G標(biāo)示一個(gè)圖，V是圖G中 頂點(diǎn)的集合，E是圖G中 邊的集合。

2.圖的種類(lèi)

圖分為無(wú)向圖和有向圖

無(wú)向圖：若頂點(diǎn)Vi到Vj之間的邊沒(méi)有方向，則稱(chēng)這條邊為無(wú)向邊（Edge），用序偶對(duì)(Vi,Vj)表示。

有向圖：若從頂點(diǎn)Vi到Vj的邊是有方向的，則成這條邊為有向邊，也稱(chēng)為?。ˋrc）。用有序?qū)Γ╒i，Vj）標(biāo)示，Vi稱(chēng)為弧尾，Vj稱(chēng)為弧頭。如果任意兩條邊之間都是有向的，則稱(chēng)該圖為有向圖。

無(wú)向圖：

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷

?有向圖：

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷

二、圖的創(chuàng)建（鄰接矩陣）

用一維數(shù)組圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組存儲(chǔ)圖中邊的信息（各頂點(diǎn)之間的鄰接關(guān)系）。存儲(chǔ)頂點(diǎn)之間鄰接關(guān)系的二維數(shù)組稱(chēng)為鄰接矩陣。結(jié)點(diǎn)數(shù)為n的圖G=(V,E)的鄰接矩陣A是n*n的，將G的頂點(diǎn)編號(hào)為v1,v2,......vn。若（vi,vj)∈E，則A[i][j]=1，否則A[i][j]=0。

鄰接矩陣用來(lái)存放邊的，兩頂點(diǎn)之間有邊相連那么在鄰接矩陣中它們對(duì)應(yīng)的值為1，否則為0

就如A與B有邊相連，那么它們對(duì)應(yīng)的值就為一，A與A自身無(wú)邊，那么就為零

1.鄰接矩陣示意圖

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷

?通過(guò)鄰接矩陣得到的結(jié)論：

  • 矩陣是對(duì)稱(chēng)的，可壓縮存儲(chǔ)（上（下）??? 三角）;
  • 第i行或第i 列中1的個(gè)數(shù)為頂點(diǎn)i 的度;
  • 矩陣中1的個(gè)數(shù)的一半為圖中邊的數(shù)目;
  • 很容易判斷頂點(diǎn)i 和頂點(diǎn)j之間是否有邊相連(看矩陣中i行j列值是否為1)。

鄰接矩陣法優(yōu)點(diǎn)：

容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等。

鄰接矩陣法缺點(diǎn)：

n個(gè)頂點(diǎn)需要n^2個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n^2)。 適合于存儲(chǔ)稠密圖，對(duì)稀疏圖而言浪費(fèi)空間.

2.先創(chuàng)建圖的結(jié)構(gòu)體

typedef struct
{
	char* vexs;//存放頂點(diǎn)的數(shù)組
	int** arcs;//存放邊的二維數(shù)組
	int vexsnum;//頂點(diǎn)個(gè)數(shù)
	int arcsnum;//邊的數(shù)目
}graph;

3.初始化圖

首先申請(qǐng)相關(guān)數(shù)組的節(jié)點(diǎn)

graph* InitGraph(int vexsnum)
{
	graph* g = new graph; //申請(qǐng)一個(gè)圖結(jié)構(gòu)體的節(jié)點(diǎn)
	
	g->vexs = new char[vexsnum];//申請(qǐng)頂點(diǎn)個(gè)數(shù)大小的數(shù)組
	
	g->arcs = new int* [vexsnum];//申請(qǐng)頂點(diǎn)個(gè)數(shù)大小的二維數(shù)組
	
	for (int i = 0; i < vexsnum; ++i)
	{
		g->arcs[i] = new int [vexsnum];  //給二維數(shù)組中的元素申請(qǐng)一個(gè)數(shù)組
		
	}
	g->vexsnum = vexsnum;
	g->arcsnum = 0;
	return g;
}

4.創(chuàng)建圖

其中vexs表示頂點(diǎn)元素的數(shù)組，arcs表示存放邊的二維數(shù)組

void CreateGraph(graph* g,char* vexs,int* arcs)
{
	for (int i = 0; i < g->vexsnum; ++i)
	{
		g->vexs[i] = vexs[i]; //將頂點(diǎn)存入存放頂點(diǎn)的數(shù)組中
	}

	for ( int i = 0; i < g->vexsnum; ++i)
	{
		for (int j = 0; j < g->vexsnum; ++j)
		{
			g->arcs[i][j] = *(arcs+i*g->vexsnum+j);//將傳入的二維數(shù)組賦值給圖結(jié)構(gòu)體中的二維數(shù)組
			if (g->arcs[i][j] != 0)
			{
				++g->arcsnum;//判斷邊的個(gè)數(shù)
			}
		}
	}
	g->arcsnum /= 2;//得到有效邊的個(gè)數(shù)
}

g->arcs[i][j] = *(arcs+i*g->vexsnum+j);該語(yǔ)句是將arcs一維數(shù)組賦值給g->arcs二維數(shù)組

g->arcsnum /= 2;該語(yǔ)句除二的原因：

判斷邊的個(gè)數(shù)的時(shí)候，每個(gè)頂點(diǎn)都判斷了一遍該頂點(diǎn)有幾條邊，所以重復(fù)判斷了

需要除二來(lái)得到真實(shí)邊的數(shù)目

三、深度優(yōu)先遍歷和廣度優(yōu)先遍歷

3.1深度優(yōu)先遍歷主要思路：

從圖中一個(gè)未訪問(wèn)的頂點(diǎn)?V?開(kāi)始，沿著一條路一直走到底，然后從這條路盡頭的節(jié)點(diǎn)回退到上一個(gè)節(jié)點(diǎn)，再?gòu)牧硪粭l路開(kāi)始走到底…，不斷遞歸重復(fù)此過(guò)程，直到所有的頂點(diǎn)都遍歷完成，它的特點(diǎn)是不撞南墻不回頭，先走完一條路，再換一條路繼續(xù)走。

就如二叉樹(shù)中的先序遍歷一樣，先訪問(wèn)根，左子樹(shù)，再訪問(wèn)右子樹(shù)

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷

?就像上面二叉樹(shù)的先序訪問(wèn)一樣，不撞南墻不回頭

3.2圖的深度優(yōu)先遍歷

visited表示一個(gè)一維數(shù)組，用來(lái)標(biāo)記被訪問(wèn)過(guò)的節(jié)點(diǎn)

index表示從第幾個(gè)頂點(diǎn)開(kāi)始訪問(wèn)

void DFS(graph*g, int* visited, int index)
{
	printf("%c ", g->vexs[index]);

	visited[index] = 1;//標(biāo)記已經(jīng)被訪問(wèn)過(guò)的頂點(diǎn)

	for (int i = 0; i < g->vexsnum; ++i)
	{
        //判斷如果有邊且該頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)，則可以訪問(wèn)
		if (g->arcs[index][i] == 1 && !visited[i])
		{
			DFS(g, visited, i);//遞歸訪問(wèn)
		}
	}
}

3.3廣度優(yōu)先遍歷的主要思想：

從某個(gè)節(jié)點(diǎn)（源點(diǎn)）出發(fā)，一次性訪問(wèn)所有未被訪問(wèn)的鄰接點(diǎn)，再依次從這些已訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)，一層一層地訪問(wèn)。如下圖所示，廣度優(yōu)先遍歷是按照廣度優(yōu)先搜索的方式對(duì)圖進(jìn)行遍歷的。

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷通過(guò)觀看右邊的鄰接矩陣，可以發(fā)現(xiàn)從A點(diǎn)出發(fā)，實(shí)際就是第一行先走完，然后再走B對(duì)應(yīng)的那一行，再走D對(duì)應(yīng)的那一行，再走C對(duì)應(yīng)的那一行，最后走E對(duì)應(yīng)的那一行

【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷

從B點(diǎn)出發(fā)，通過(guò)鄰接矩陣可以發(fā)現(xiàn)，實(shí)際就是第B對(duì)應(yīng)的那一行先走完，然后再走A對(duì)應(yīng)的那一行，再走C對(duì)應(yīng)的那一行，再走D對(duì)應(yīng)的那一行，最后走E對(duì)應(yīng)的那一行

3.4圖的廣度優(yōu)先遍歷

?廣度優(yōu)先遍歷就像二叉樹(shù)中的層數(shù)，一層一層的走完。

通過(guò)上面的示例可以發(fā)現(xiàn)，圖也是一層一層的走完，但是它不是按順序走的，而是按先訪問(wèn)到誰(shuí)就先走誰(shuí)的那一行

有了這個(gè)思想，那么很顯然此時(shí)我們就可以用隊(duì)列來(lái)實(shí)現(xiàn)了，把訪問(wèn)到的頂點(diǎn)入隊(duì)，然后等訪問(wèn)完 了該頂點(diǎn)相鄰的頂點(diǎn)，就出隊(duì)訪問(wèn)出隊(duì)的頂點(diǎn)和其相鄰的頂點(diǎn)，依次重復(fù)上述步驟，直到隊(duì)列為空

void BFS(graph*g,int* visited, int index)
{
	queue<int> q;
	printf("%c ", g->vexs[index]);
	visited[index] = 1;//標(biāo)記
	q.push(index);//入隊(duì)
	while (!q.empty())
	{
		int top = q.front();//出隊(duì)
		q.pop();
		for (int i = 0; i < g->vexsnum; ++i)
		{
			if (g->arcs[top][i] == 1 && !visited[i])
			{
				printf("%c ", g->vexs[i]);
				visited[i] = 1;
				q.push(i);
			}
		}
	}
}

3.5圖的實(shí)現(xiàn)代碼

#include<iostream>
#include<queue>
using namespace std;

#define N 5  //N表示圖的節(jié)點(diǎn)個(gè)數(shù)

typedef struct
{
	char* vexs;
	int** arcs;
	int vexsnum;
	int arcsnum;
}graph;

graph* InitGraph(int vexsnum)
{
	graph* g = new graph; //申請(qǐng)一個(gè)圖結(jié)構(gòu)體的節(jié)點(diǎn)
	
	g->vexs = new char[vexsnum];//申請(qǐng)頂點(diǎn)個(gè)數(shù)大小的數(shù)組
	
	g->arcs = new int* [vexsnum];//申請(qǐng)頂點(diǎn)個(gè)數(shù)大小的二維數(shù)組
	
	for (int i = 0; i < vexsnum; ++i)
	{
		g->arcs[i] = new int [vexsnum];  //給二維數(shù)組中的元素申請(qǐng)一個(gè)數(shù)組
		
	}
	g->vexsnum = vexsnum;
	g->arcsnum = 0;
	return g;
}

void CreateGraph(graph* g,char* vexs,int* arcs)
{
	for (int i = 0; i < g->vexsnum; ++i)
	{
		g->vexs[i] = vexs[i]; //將頂點(diǎn)存入存放頂點(diǎn)的數(shù)組中
	}

	for ( int i = 0; i < g->vexsnum; ++i)
	{
		for (int j = 0; j < g->vexsnum; ++j)
		{
		  g->arcs[i][j] = *(arcs+i*g->vexsnum+j);//將傳入的二維數(shù)組賦值給圖結(jié)構(gòu)體中的二維數(shù)組
			if (g->arcs[i][j] != 0)
			{
				++g->arcsnum;//判斷邊的個(gè)數(shù)
			}
		}
	}
	g->arcsnum /= 2;//得到有效邊的個(gè)數(shù)，
}

void DFS(graph*g, int* visited, int index)
{
	printf("%c ", g->vexs[index]);
	visited[index] = 1;
	for (int i = 0; i < g->vexsnum; ++i)
	{
		if (g->arcs[index][i] == 1 && !visited[i])
		{
			DFS(g, visited, i);
		}
	}
}

void BFS(graph*g,int* visited, int index)
{
	queue<int> q;
	printf("%c ", g->vexs[index]);
	visited[index] = 1;//標(biāo)記
	q.push(index);//入隊(duì)
	while (!q.empty())
	{
		int top = q.front();//出隊(duì)
		q.pop();
		for (int i = 0; i < g->vexsnum; ++i)
		{
			if (g->arcs[top][i] == 1 && !visited[i])
			{
				printf("%c ", g->vexs[i]);
				visited[i] = 1;
				q.push(i);
			}
		}
	}
}

int main()
{
	graph* g = InitGraph(N);//初始化圖
	char vexs[] = {'A','B','C','D','E'};//頂點(diǎn)元素
	int visited[N] = { 0 };//用來(lái)標(biāo)記的數(shù)組
	int arcs[N][N] =
	{
		0,1,0,1,0,
		1,0,1,1,0,
		0,1,0,1,1,
		1,1,1,0,1,
		0,0,1,1,0
	};//鄰接矩陣

	CreateGraph(g, vexs, (int*)arcs);//創(chuàng)建圖

	DFS(g, visited, 0);//深度優(yōu)先遍歷
	printf("\n");

	memset(visited, 0, sizeof(int) * N);//將標(biāo)記數(shù)組重新置為0

	BFS(g, visited, 1);//廣度優(yōu)先遍歷
	return 0;
}

關(guān)于圖的知識(shí)就分享到這了，謝謝支持！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-449773.html

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

本文來(lái)自互聯(lián)網(wǎng)用戶(hù)投稿，該文觀點(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)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包