真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

C++構(gòu)造無(wú)向圖，鄰接矩陣，深度優(yōu)先遍歷，廣度優(yōu)先遍歷-創(chuàng)新互聯(lián)

目錄

創(chuàng)新互聯(lián)的客戶來(lái)自各行各業(yè)，為了共同目標(biāo)，我們?cè)诠ぷ魃厦芮信浜?，從?chuàng)業(yè)型小企業(yè)到企事業(yè)單位，感謝他們對(duì)我們的要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。專(zhuān)業(yè)領(lǐng)域包括網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、電商網(wǎng)站開(kāi)發(fā)、微信營(yíng)銷(xiāo)、系統(tǒng)平臺(tái)開(kāi)發(fā)。

定義無(wú)向圖鄰接矩陣

構(gòu)造無(wú)向圖

打印鄰接矩陣

無(wú)向圖鄰接矩陣深度優(yōu)先遍歷（DFS）

無(wú)向圖鄰接矩陣廣度優(yōu)先遍歷（BFS）

測(cè)試

完整代碼

定義無(wú)向圖鄰接矩陣
#define MVNum 100 //大頂點(diǎn)數(shù)

//定義無(wú)向圖鄰接矩陣
struct AMGraph
{
	string vexs[MVNum]; //頂點(diǎn)表
	int arcs[MVNum][MVNum]; //鄰接矩陣
	int vexnum, arcnum; //圖的當(dāng)前定點(diǎn)數(shù)和邊數(shù)
};
構(gòu)造無(wú)向圖

1、輸入總頂點(diǎn)數(shù)和總邊數(shù)

2、依次輸入頂點(diǎn)信息存入頂點(diǎn)表

3、初始化鄰接矩陣,使每個(gè)權(quán)值初始化為極大值

4、構(gòu)造鄰接矩陣

//聲明
int LocateVex(AMGraph G, string u);

//創(chuàng)建無(wú)向圖
bool CreateUDN(AMGraph& G)
{
	//1.輸入頂點(diǎn)數(shù)和邊數(shù)
	cout<< "請(qǐng)輸入頂點(diǎn)數(shù)："<< endl;
	cin >>G.vexnum;
	cout<< "請(qǐng)輸入邊數(shù)："<< endl;
	cin >>G.arcnum;

	//2.依次輸入頂點(diǎn)信息存入頂點(diǎn)表
	cout<< "請(qǐng)輸入頂點(diǎn)："<< endl;
	for (int i = 0; i< G.vexnum; i++)
	{
		cin >>G.vexs[i];
	}

	//3.初始化鄰接矩陣,使每個(gè)權(quán)值初始化為極大值
	for (int i = 0; i< G.vexnum; i++)
	{
		for (int j = 0; j< G.vexnum; j++)
		{
			G.arcs[i][j] = 0; //初始化鄰接矩陣為0
		}
	}

	//4.構(gòu)造鄰接矩陣
	cout<< "請(qǐng)輸入一條邊所依附的兩個(gè)頂點(diǎn)及邊的權(quán)值："<< endl;
	for (int k = 0; k< G.arcnum; k++)
	{
		string v1, v2;
		//int w;
		cin >>v1 >>v2; //輸入一條邊所依附的兩個(gè)頂點(diǎn)及邊的權(quán)值
		int i = LocateVex(G, v1); //確定v1,v2在G中的位置
		int j = LocateVex(G, v2);
		G.arcs[i][j] = 1; //邊(v1,v2)的權(quán)值置為w
		G.arcs[j][i] = G.arcs[i][j]; //置邊(v1,v2)的對(duì)稱(chēng)邊(v2,v1)的權(quán)值為w
	}
	return true;
}

//在圖中查找頂點(diǎn)u，存在返回頂點(diǎn)表中的下標(biāo)，否則返回-1
int LocateVex(AMGraph G, string u)
{
	for (int i = 0; i< G.vexnum; i++)
	{
		if (u == G.vexs[i])
		{
			return i;
		}
	}
	return -1;
}
打印鄰接矩陣
//打印鄰接矩陣
void PrintVex(AMGraph G)
{
	for (int i = 0; i< G.vexnum; i++)
	{
		for (int j = 0; j< G.vexnum; j++)
		{
				cout<< G.arcs[i][j]<< "\t";
		}
		cout<< endl;
	}
}
無(wú)向圖鄰接矩陣深度優(yōu)先遍歷（DFS）

1、在訪問(wèn)圖中某一起始頂點(diǎn)v后，由v出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)w1；

2、再?gòu)膚1出發(fā)，訪問(wèn)與w1鄰接但還未被訪問(wèn)過(guò)的頂點(diǎn)w2;

3、然后再?gòu)膚2出發(fā)，進(jìn)行類(lèi)似的訪問(wèn)，...

4、如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)u為止。接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。

5、如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類(lèi)似的訪問(wèn);

6、如果沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。

bool visited[MVNum]; //深度優(yōu)先訪問(wèn)標(biāo)志數(shù)組， 其初值為 "false"

//無(wú)向圖深度優(yōu)先遍歷
void DFS(AMGraph G, int v)
{
	cout<< G.vexs[v]<< " "; //訪問(wèn)第v個(gè)頂點(diǎn)
	visited[v] = true; //訪問(wèn)后標(biāo)志數(shù)組中第v個(gè)頂點(diǎn)設(shè)為true（1）
	for (int w = 0; w< G.vexnum; w++) //依次檢查鄰接矩陣v所在行
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w])) //表示w是v的鄰接點(diǎn)， 如果w未訪問(wèn)， 則遞歸調(diào)用DFS
		{
			DFS(G, w);
		}
	}
}
無(wú)向圖鄰接矩陣廣度優(yōu)先遍歷（BFS）

1、從圖的一結(jié)點(diǎn)出發(fā)，首先依次訪問(wèn)該結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)v1,v2......vn再按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)與它們相鄰的所有未被訪問(wèn)的頂點(diǎn)。

2、重復(fù)此過(guò)程，直至所有頂點(diǎn)均被訪問(wèn)為止。

bool visited1[MVNum]; //廣度優(yōu)先訪問(wèn)標(biāo)志數(shù)組， 其初值為 "false"

//無(wú)向圖廣度優(yōu)先遍歷
void BFS(AMGraph G, int v)
{
	cout<< G.vexs[v]<< " "; //訪問(wèn)第v個(gè)頂點(diǎn)
	visited1[v] = true;//訪問(wèn)后標(biāo)志數(shù)組中第v個(gè)頂點(diǎn)設(shè)為true（1）
	queueQ;//創(chuàng)建隊(duì)列Q
	Q.push(v); //v進(jìn)隊(duì)
	while (!Q.empty())//隊(duì)列非空
	{
		int p = Q.front(); //取出隊(duì)頭元素賦給p
		for (int i = 0; i< G.vexnum; i++)
		{
			if ((G.arcs[p][i] != 0) && (!visited1[i]))//判斷i是否是p未訪問(wèn)的鄰接點(diǎn)
			{
				cout<< G.vexs[i]<< " ";//訪問(wèn)第i個(gè)頂點(diǎn)
				Q.push(i);//i進(jìn)隊(duì)
				visited1[i] = true;
			}
		}
		Q.pop();//刪除隊(duì)頭元素
	}
}
測(cè)試
int main()
{
	AMGraph G;
	CreateUDN(G); //構(gòu)造圖
	cout<< "圖G的鄰接矩陣為："<< endl;
	PrintVex(G); //打印
	int v = 0;
	cout<< "廣度優(yōu)先遍歷為："<< endl;
	BFS(G, v);
	cout<< endl;
	cout<< "深度優(yōu)先遍歷為："<< endl;
	DFS(G, v);
	cout<< endl;

	system("pause");
	return 0;
}

完整代碼
#includeusing namespace std;
#include#define MVNum 100 //大頂點(diǎn)數(shù)

//定義無(wú)向圖鄰接矩陣
struct AMGraph
{
	string vexs[MVNum]; //頂點(diǎn)表
	int arcs[MVNum][MVNum]; //鄰接矩陣
	int vexnum, arcnum; //圖的當(dāng)前定點(diǎn)數(shù)和邊數(shù)
};

bool visited[MVNum]; //深度優(yōu)先訪問(wèn)標(biāo)志數(shù)組， 其初值為 "false"

bool visited1[MVNum]; //廣度優(yōu)先訪問(wèn)標(biāo)志數(shù)組， 其初值為 "false"


int LocateVex(AMGraph G, string u);

//創(chuàng)建無(wú)向圖
bool CreateUDN(AMGraph& G)
{
	//1.輸入頂點(diǎn)數(shù)和邊數(shù)
	cout<< "請(qǐng)輸入頂點(diǎn)數(shù)："<< endl;
	cin >>G.vexnum;
	cout<< "請(qǐng)輸入邊數(shù)："<< endl;
	cin >>G.arcnum;

	//2.依次輸入頂點(diǎn)信息存入頂點(diǎn)表
	cout<< "請(qǐng)輸入頂點(diǎn)："<< endl;
	for (int i = 0; i< G.vexnum; i++)
	{
		cin >>G.vexs[i];
	}

	//3.初始化鄰接矩陣,使每個(gè)權(quán)值初始化為極大值
	for (int i = 0; i< G.vexnum; i++)
	{
		for (int j = 0; j< G.vexnum; j++)
		{
			G.arcs[i][j] = 0; //初始化鄰接矩陣為0
		}
	}

	//4.構(gòu)造鄰接矩陣
	cout<< "請(qǐng)輸入一條邊所依附的兩個(gè)頂點(diǎn)及邊的權(quán)值："<< endl;
	for (int k = 0; k< G.arcnum; k++)
	{
		string v1, v2;
		//int w;
		cin >>v1 >>v2; //輸入一條邊所依附的兩個(gè)頂點(diǎn)及邊的權(quán)值
		int i = LocateVex(G, v1); //確定v1,v2在G中的位置
		int j = LocateVex(G, v2);
		G.arcs[i][j] = 1; //邊(v1,v2)的權(quán)值置為w
		G.arcs[j][i] = G.arcs[i][j]; //置邊(v1,v2)的對(duì)稱(chēng)邊(v2,v1)的權(quán)值為w
	}
	return true;
}

//在圖中查找頂點(diǎn)u，存在返回頂點(diǎn)表中的下標(biāo)，否則返回-1
int LocateVex(AMGraph G, string u)
{
	for (int i = 0; i< G.vexnum; i++)
	{
		if (u == G.vexs[i])
		{
			return i;
		}
	}
	return -1;
}

//打印鄰接矩陣
void PrintVex(AMGraph G)
{
	for (int i = 0; i< G.vexnum; i++)
	{
		for (int j = 0; j< G.vexnum; j++)
		{
				cout<< G.arcs[i][j]<< "\t";
		}
		cout<< endl;
	}
}

//無(wú)向圖深度優(yōu)先遍歷
void DFS(AMGraph G, int v)
{
	cout<< G.vexs[v]<< " "; //訪問(wèn)第v個(gè)頂點(diǎn)
	visited[v] = true; //訪問(wèn)后標(biāo)志數(shù)組中第v個(gè)頂點(diǎn)設(shè)為true（1）
	for (int w = 0; w< G.vexnum; w++) //依次檢查鄰接矩陣v所在行
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w])) //表示w是v的鄰接點(diǎn)， 如果w未訪問(wèn)， 則遞歸調(diào)用DFS
		{
			DFS(G, w);
		}
	}
}

//無(wú)向圖廣度優(yōu)先遍歷
void BFS(AMGraph G, int v)
{
	cout<< G.vexs[v]<< " "; //訪問(wèn)第v個(gè)頂點(diǎn)
	visited1[v] = true;//訪問(wèn)后標(biāo)志數(shù)組中第v個(gè)頂點(diǎn)設(shè)為true（1）
	queueQ;//創(chuàng)建隊(duì)列Q
	Q.push(v); //v進(jìn)隊(duì)
	while (!Q.empty())//隊(duì)列非空
	{
		int p = Q.front(); //取出隊(duì)頭元素賦給p
		for (int i = 0; i< G.vexnum; i++)
		{
			if ((G.arcs[p][i] != 0) && (!visited1[i]))//判斷i是否是p未訪問(wèn)的鄰接點(diǎn)
			{
				cout<< G.vexs[i]<< " ";//訪問(wèn)第i個(gè)頂點(diǎn)
				Q.push(i);//i進(jìn)隊(duì)
				visited1[i] = true;
			}
		}
		Q.pop();//刪除隊(duì)頭元素
	}
}

int main()
{
	AMGraph G;
	CreateUDN(G); //構(gòu)造圖
	cout<< "圖G的鄰接矩陣為："<< endl;
	PrintVex(G); //打印
	int v = 0;
	cout<< "廣度優(yōu)先遍歷為："<< endl;
	BFS(G, v);
	cout<< endl;
	cout<< "深度優(yōu)先遍歷為："<< endl;
	DFS(G, v);
	cout<< endl;

	system("pause");
	return 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)查看詳情吧


當(dāng)前名稱(chēng)：C++構(gòu)造無(wú)向圖，鄰接矩陣，深度優(yōu)先遍歷，廣度優(yōu)先遍歷-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://weahome.cn/article/dpdogj.html

其他資訊

在線咨詢(xún)

微信咨詢(xún)

電話咨詢(xún)

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部