c++實(shí)現(xiàn)圖的操作(最小生成樹(shù)和最短路徑)-創(chuàng)新互聯(lián)

【題目描述】

（1）圖的深度優(yōu)先搜索演示。

專(zhuān)業(yè)領(lǐng)域包括網(wǎng)站設(shè)計(jì)、做網(wǎng)站、購(gòu)物商城網(wǎng)站建設(shè)、微信營(yíng)銷(xiāo)、系統(tǒng)平臺(tái)開(kāi)發(fā)， 與其他網(wǎng)站設(shè)計(jì)及系統(tǒng)開(kāi)發(fā)公司不同，創(chuàng)新互聯(lián)的整合解決方案結(jié)合了幫做網(wǎng)絡(luò)品牌建設(shè)經(jīng)驗(yàn)和互聯(lián)網(wǎng)整合營(yíng)銷(xiāo)的理念，并將策略和執(zhí)行緊密結(jié)合，為客戶提供全網(wǎng)互聯(lián)網(wǎng)整合方案。

要求：圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，編程實(shí)現(xiàn)圖的創(chuàng)建、圖的深度優(yōu)先搜索遞歸算法。 ???????

（2）圖的廣度優(yōu)先搜索演示。

要求：圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，編程實(shí)現(xiàn)圖的創(chuàng)建、圖的深度優(yōu)先搜索遞歸算法。

（3）求帶權(quán)無(wú)向圖的最小生成樹(shù)問(wèn)題。

（4）求帶權(quán)有向圖中從某個(gè)源點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑問(wèn)題。

【代碼實(shí)現(xiàn)】

廢話不多說(shuō)直接上代碼

#include#includeusing namespace std;
#define MVNum 100//大的頂點(diǎn)數(shù)
#define Max 1000//沒(méi)有權(quán)值時(shí)的∞
//邊節(jié)點(diǎn)
typedef struct ArcNode {
	int adjvex;//該邊所指向的頂點(diǎn)的位置
	ArcNode* nextarc;//指向下一條邊的指針
	int info;//邊的權(quán)值
};
//點(diǎn)節(jié)點(diǎn)
typedef struct VNode {
	char data;//頂點(diǎn)信息
	ArcNode* firstarc;//指向第一條依附該頂點(diǎn)的邊的指針
};
//鄰接表
typedef struct ALGragh {
	VNode vertices[MVNum];//頂點(diǎn)數(shù)組
	int visited[MVNum];//標(biāo)志數(shù)組
	int vexnum, arcnum;//圖當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
};
//輔助數(shù)組的定義，用來(lái)記錄從頂點(diǎn)集U到V-U的權(quán)值最小的邊
typedef struct closeEdge {
	int adjvex;//最小邊在U中的那個(gè)頂點(diǎn)
	int lowcost;//最小邊的權(quán)值
};
//通過(guò)點(diǎn)的信息定位點(diǎn)的位置
int LocateVex(ALGragh G, char c) {
	for (int i = 0; i< G.vexnum; i++) {
		if (G.vertices[i].data == c) {
			return i;
		}
	}
}
//將標(biāo)志數(shù)組歸零，每次深度遍歷圖之后都要?dú)w零
void reZero(ALGragh &G) {
	for (int i = 0; i< G.vexnum; i++)	
		G.visited[i] = 0;
}
//鄰接表創(chuàng)建帶權(quán)無(wú)向圖(undirected graph)
void CreateUDG(ALGragh& G) {
	cout<< "請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):";
	cin >>G.vexnum >>G.arcnum;
	cout<< "請(qǐng)依次輸入各頂點(diǎn)信息(以空格分割):";
	for (int i = 0; i< G.vexnum; i++) {
		cin >>G.vertices[i].data;
		G.visited[i] = 0;//將標(biāo)志數(shù)組初始化為0
		G.vertices[i].firstarc = NULL;
	}
	char v1, v2;
	int info;
	for (int k = 0; k< G.arcnum; k++) {
		cout<< "請(qǐng)輸入一條邊的兩個(gè)頂點(diǎn)信息和邊的權(quán)值:";
		cin >>v1 >>v2 >>info;
		//確定v1和v2在G中的位置
		int i = LocateVex(G, v1); int j = LocateVex(G, v2);
		//分別將頂點(diǎn)v1和v2指向該條邊
		ArcNode *p1 = new ArcNode;//生成一個(gè)新的邊節(jié)點(diǎn)
		p1->adjvex = j; p1->info = info;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		ArcNode* p2 = new ArcNode;
		p2->adjvex = i; p2->info = info;
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}
//鄰接表創(chuàng)建帶權(quán)有向圖(undirected graph)
void CreateDG(ALGragh& G) {
	cout<< "請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):";
	cin >>G.vexnum >>G.arcnum;
	cout<< "請(qǐng)依次輸入各頂點(diǎn)信息(以空格分割):";
	for (int i = 0; i< G.vexnum; i++) {
		cin >>G.vertices[i].data;
		G.visited[i] = 0;//將標(biāo)志數(shù)組初始化為0
		G.vertices[i].firstarc = NULL;
	}
	char v1, v2;
	int info;
	for (int k = 0; k< G.arcnum; k++) {
		cout<< "請(qǐng)輸入一條邊的兩個(gè)頂點(diǎn)信息和邊的權(quán)值:";
		cin >>v1 >>v2 >>info;
		//確定v1和v2在G中的位置
		int i = LocateVex(G, v1); int j = LocateVex(G, v2);
		//有向圖只需將v1連接該條邊
		ArcNode* p1 = new ArcNode;//生成一個(gè)新的邊節(jié)點(diǎn)
		p1->adjvex = j; p1->info = info;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
	}
}
//圖的深度優(yōu)先遍歷
void DFS(ALGragh &G,char v) {
	cout<< v; G.visited[LocateVex(G,v)] = 1;//將訪問(wèn)過(guò)的標(biāo)志數(shù)組設(shè)為1
	ArcNode *p = G.vertices[LocateVex(G,v)].firstarc;//p指向v的邊鏈表的第一個(gè)邊節(jié)點(diǎn)
	while (p != NULL) {
		int w = p->adjvex;//w是v的鄰接點(diǎn)
		//如果w未訪問(wèn)，則繼續(xù)遞歸
		if (!G.visited[w])	DFS(G, G.vertices[w].data);
		p = p->nextarc;//否則繼續(xù)深入
	}
}
//圖的廣度優(yōu)先遍歷
void BFS(ALGragh G, char v) {
	cout<< v; G.visited[LocateVex(G, v)] = 1;
	queueQ;
	Q.push(v);//v入隊(duì)
	while (!Q.empty()) {
		char u = Q.front(); Q.pop();//隊(duì)首出隊(duì)
		ArcNode* p = G.vertices[LocateVex(G, u)].firstarc;
		while (p != NULL) {
			int w = p->adjvex;
			if (!G.visited[w]) {
				cout<< G.vertices[w].data;//如果w未訪問(wèn)，則輸出該節(jié)點(diǎn)
				G.visited[w] = 1;
				Q.push(G.vertices[w].data);//入隊(duì)
			}
			p = p->nextarc;
		}
	}
}
//查找輔助數(shù)組的V-U中，邊的最小值
int Min(closeEdge c[],int num) {
	int min = Max;//記錄最小邊的權(quán)值
	int flag = 0;//記錄最小邊所在頂點(diǎn)
	for (int i = 0; iadjvex].lowcost = p->info;
		p = p->nextarc;
	}
	//prim
	for (int i = 0; i< G.vexnum - 1; i++) {
		k = Min(ce,G.vexnum);
		int u0 = ce[k].adjvex;//最小邊的頂點(diǎn)
		cout<< G.vertices[u0].data<< " "<< G.vertices[k].data<< " 權(quán)值:"<< ce[k].lowcost<< endl;
		ce[k].lowcost = 0;//將第k個(gè)頂點(diǎn)并入U(xiǎn)集
		//新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊
		p = G.vertices[k].firstarc;
		while (p != NULL) {
			for (int j = 0; j< G.vexnum; j++)
				if (p->info< ce[j].lowcost && j == p->adjvex)
					ce[j] = { k,p->info };
			p = p->nextarc;
		}
	}
}
//用dijkstra算法求最短路徑
void ShortestPath_Dijkstra(ALGragh G,char a) {
	bool S[MVNum];//記錄從源點(diǎn)到終點(diǎn)是否已被確認(rèn)是最短路徑
	int D[MVNum];//記錄從源點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度
	int Path[MVNum];//記錄從源點(diǎn)到某一點(diǎn)是否有路徑
	int v0 = LocateVex(G, a);
	ArcNode* p = G.vertices[v0].firstarc;
	//初始化
	for (int v = 0; v< G.vexnum; v++) {
		S[v] = false;
		D[v] = Max;
		Path[v] = -1;//無(wú)弧記為-1
	}
	while (p != NULL) {
		D[p->adjvex] = p->info;
		Path[p->adjvex] = v0;//v0到v有弧
		p = p->nextarc;
	}
	S[v0] = true; D[v0] = 0;//除去源點(diǎn)
	//初始化結(jié)束，開(kāi)始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)的最短路徑，將v加入S集
	for (int i = 1; i< G.vexnum; i++) {
		int min = Max;//min用來(lái)保存當(dāng)前的最短路徑，初始化為極大值
		int v;//用來(lái)記錄當(dāng)前終點(diǎn)
		for (int w = 0; w< G.vexnum; w++)
			if (!S[w] && D[w]< min) {
				v = w; min = D[w];
			}
		S[v] = true;
		//更新從v0出發(fā)到集合V-S上所有頂點(diǎn)的最短路徑長(zhǎng)度
		p = G.vertices[v].firstarc;
		while (p != NULL) {
			for (int w = 0; w< G.vexnum; w++)
				if (!S[w] && (D[v] + p->info< D[w]) && w == p->adjvex) {
					D[w] = D[v] + p->info;//更新D[w]
					Path[w] = v;//更改w的前驅(qū)為v
				}
			p = p->nextarc;
		}
	}
	//算法結(jié)束，輸出從源點(diǎn)到各個(gè)點(diǎn)的最短路徑
	for (int i = 0; i< G.vexnum; i++) {
		if (i!=v0) {
			cout<< "從"<< a<< "到"<< G.vertices[i].data<< "的最短路徑長(zhǎng)度為:";
			cout<< D[i]<< endl;
		}
	}
}
int main() {
	ALGragh G1, G2;
	cout<< "請(qǐng)創(chuàng)建帶權(quán)無(wú)向圖G1:"<< endl;
	CreateUDG(G1);
	cout<< "請(qǐng)創(chuàng)建帶權(quán)有向圖G2:"<< endl;
	CreateDG(G2);
	cout<< "深度優(yōu)先遍歷圖"<< endl;
	cout<< "G1:"; DFS(G1, 'A');
	cout<< "\nG2:"; DFS(G2, 'A');
	reZero(G1); reZero(G2);
	cout<< "\n廣度優(yōu)先遍歷圖"<< endl;
	cout<< "G1:"; BFS(G1, 'A');
	cout<< "\nG2:"; BFS(G2, 'A');
	cout<< "\n普利姆算法求G1的最小生成樹(shù):"<< endl;
	MiniSpanTree_Prim(G1,'A');
	cout<< "迪杰斯特拉算法求G2的最短路徑:"<< endl;
	ShortestPath_Dijkstra(G2, 'A');
}
【功能測(cè)試】 （1）功能測(cè)試--圖的創(chuàng)建

圖 4.1 圖的創(chuàng)建測(cè)試結(jié)果

圖的創(chuàng)建就是先輸入圖的頂點(diǎn)數(shù)和邊數(shù)，然后依次輸出各頂點(diǎn)的信息(以空格分割)，然后根據(jù)邊的個(gè)數(shù)，依次輸入每個(gè)邊的兩個(gè)頂點(diǎn)和邊的權(quán)值，根據(jù)輸入的頂點(diǎn)值根據(jù)LocateVex函數(shù)定位頂點(diǎn)數(shù)組的位置，之后創(chuàng)建邊節(jié)點(diǎn)讓兩頂點(diǎn)指向該條邊，然后接入頂點(diǎn)數(shù)組的指針上，有向圖和無(wú)向圖創(chuàng)建的區(qū)別只在生成幾個(gè)邊節(jié)點(diǎn)，無(wú)向圖會(huì)生成兩個(gè)邊節(jié)點(diǎn)，而有向圖只生成一個(gè)，因?yàn)樗蟹较颉?/p>（2）功能測(cè)試--深度優(yōu)先遍歷

圖 4.2 深度優(yōu)先遍歷測(cè)試結(jié)果

深度優(yōu)先遍歷就是用棧來(lái)實(shí)現(xiàn)，先進(jìn)后出，在這里我用的是遞歸來(lái)實(shí)現(xiàn)，在圖的構(gòu)造中我增加了一個(gè)標(biāo)志數(shù)組(初始化值為0)用來(lái)標(biāo)志訪問(wèn)過(guò)的頂點(diǎn)，選一個(gè)頂點(diǎn)，然后一直遞歸深入圖，就是一條路走到黑，當(dāng)頂點(diǎn)為空的時(shí)候再退回去繼續(xù)遞歸，訪問(wèn)過(guò)的頂點(diǎn)，其對(duì)應(yīng)的數(shù)組就設(shè)為1，直到全部的頂點(diǎn)全部訪問(wèn)過(guò)。

（3）功能測(cè)試--廣度優(yōu)先遍歷

圖 4.3 深度優(yōu)先遍歷測(cè)試結(jié)果

廣度優(yōu)先遍歷就是用隊(duì)列實(shí)現(xiàn)，先進(jìn)先出，用c++標(biāo)準(zhǔn)庫(kù)里的queue隊(duì)列，將頂點(diǎn)保存到隊(duì)列里，先將頂點(diǎn)的全部鄰接頂點(diǎn)入隊(duì)，然后依次出隊(duì)頂點(diǎn)，重復(fù)循環(huán)該操作，這樣就能實(shí)現(xiàn)廣度優(yōu)先遍歷。

（4）功能測(cè)試--Prim算法求最小生成樹(shù)

圖 4.4 Prim算法求最小生成樹(shù)測(cè)試結(jié)果

prim算法的核心就是歸并頂點(diǎn)，使每一次循環(huán)找最小的邊都是局部最小，然后一步步擴(kuò)大它的范圍。

在本題我學(xué)習(xí)課本增加了一個(gè)存放當(dāng)前頂點(diǎn)與其它頂點(diǎn)的邊的最小值closeEdge數(shù)組，然后在函數(shù)里對(duì)該數(shù)組初始化，將所有除它本身的頂點(diǎn)，都附上他們兩點(diǎn)間的權(quán)值，若兩點(diǎn)間沒(méi)有權(quán)值則賦予大值Max，且將初識(shí)頂點(diǎn)的lowcost設(shè)為0完成初始化。然后到程序的核心，首先在closeEdge數(shù)組中選擇當(dāng)前頂點(diǎn)的最小邊作為并入最小生成樹(shù)邊的集合中，并將該邊的頂點(diǎn)并入最小生成樹(shù)的點(diǎn)中，同時(shí)將該點(diǎn)的lowcose置為0，說(shuō)明該點(diǎn)已經(jīng)連成，重復(fù)該步驟就能完成圖的最小生成樹(shù)。

本題的難點(diǎn)在于書(shū)上的例子用的是鄰接矩陣來(lái)實(shí)現(xiàn)，我在創(chuàng)建圖的過(guò)程用的是鄰接表，所以我應(yīng)找出鄰接矩陣和鄰接表的不同從而對(duì)該算法的修改。

（5）功能測(cè)試--Dijkstra算法求最短路徑

圖 4.5 Dijkstra算法求最短路徑測(cè)試結(jié)果

Dijkstra算法的思想就是按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑，每寫(xiě)一個(gè)頂點(diǎn)都是在上一個(gè)最短路徑產(chǎn)生的，依次修改路徑長(zhǎng)度，從而達(dá)到最優(yōu)。

在本題我從課本上學(xué)習(xí)，用了幾個(gè)數(shù)組分別來(lái)儲(chǔ)存路徑的信息。S數(shù)組用于記錄源點(diǎn)到某一個(gè)頂點(diǎn)是否已經(jīng)是最短路徑，D數(shù)組用于記錄源點(diǎn)到某一個(gè)頂點(diǎn)的路徑長(zhǎng)度，Path數(shù)組用于記錄某一個(gè)頂點(diǎn)和另一個(gè)頂點(diǎn)是否有弧，有弧則記錄該頂點(diǎn)的下標(biāo)，無(wú)弧則為-1，然后根據(jù)這些定義來(lái)初始化算法。

初始化結(jié)束，開(kāi)始主循環(huán)，每次求得源點(diǎn)到某個(gè)頂點(diǎn)的最短路徑，將找到的最短路徑記錄到S中。每次找到源點(diǎn)到某個(gè)頂點(diǎn)的最短路徑，都要更新S數(shù)組為false的路徑長(zhǎng)度，重復(fù)循環(huán)完成算法。

本題的難點(diǎn)也是在于鄰接矩陣和鄰接表的不同從而需要對(duì)算法進(jìn)行修改，比如在更新數(shù)組的時(shí)候，判斷是否是該路徑上的點(diǎn)需要加上該頂點(diǎn)是否等于p->adjvex。

你是否還在尋找穩(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)查看詳情吧

網(wǎng)頁(yè)標(biāo)題：c++實(shí)現(xiàn)圖的操作(最小生成樹(shù)和最短路徑)-創(chuàng)新互聯(lián)
當(dāng)前地址：http://muchs.cn/article10/dpsido.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、服務(wù)器托管、外貿(mào)建站、網(wǎng)站維護(hù)、網(wǎng)站設(shè)計(jì)、App設(shè)計(jì)

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)

商城網(wǎng)站建設(shè)