數據結構》08-圖7 公路村村通（最小生成樹問）

題目
現有村落間道路的統計數據表中，列出了有可能建設成標準公路的若干條道路的成本，求使每個村落都有公路連通所需要的最低成本。

輸入格式:
輸入數據包括城鎮數目正整數N（≤1000）和候選道路數目M（≤3N）；隨后的M行對應M條道路，每行給出3個正整數，分別是該條道路直接連通的兩個城鎮的編號以及該道路改建的預算成本。為簡單起見，城鎮從1到N編號。

輸出格式:
輸出村村通需要的最低成本。如果輸入數據不足以保證暢通，則輸出?1，表示需要建設更多公路。

輸入樣例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

輸出樣例:

12
—————————————————————————

方法一：Kruskal算法

核心–不停地找權重最小的變合在一起但需要注意的是 不能構成回路 如何找最小權重所在的邊，可以靠最小堆來解決，如何判斷是否構成回路呢，可以用并查集看是否屬于同一棵樹，這可以參考之前的并查集的blog

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define maxsize 1001
int n;     //頂點
int m;     //邊
int parent[maxsize];
struct node {
	int v1;
	int v2;
	int weight;
	bool operator<(const node& a)const {
		return a.weight<this->weight;
	}
};
priority_queue<node>q;
vector<node>mst;            //最小生成樹
int sum = 0;
void build()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		parent[i] = -1;
	}
	for (int i = 1; i <= m; i++) {
		node temp;
		cin >> temp.v1 >> temp.v2 >> temp.weight;
		q.push(temp);
	}
}
int find(int x) //路徑壓縮查找頭結點
{
	if (parent[x] < 0)
		return x;
	else
		return parent[x] = find(parent[x]);
}
void Union(int x1, int x2)     //按秩歸并(具體看之前發的并查集的blog）
{
	x1 = find(x1);
	x2 = find(x2);
	if (parent[x1] < parent[x2]) {
		parent[x1] += parent[x2];
		parent[x2] = x1;
	}
	else {
		parent[x2] += parent[x1];
		parent[x1] = x2;
	}
}
void kruskal()
{
	while (mst.size() != m - 1 && !q.empty()) {
		node E = q.top();
		q.pop();
		if (find(E.v1) != find(E.v2)) {
			sum += E.weight;
			Union(E.v1, E.v2);
			mst.push_back(E);
		}
	}
}
int main()
{
	build();
	kruskal();
	if (mst.size() == n - 1)
		cout << sum;
	else
		cout << -1;
	return 0;
}

—————————————————————————

方法二

prim算法,類似于DJ算法，貪心思想，找到臨近最短的就更新

#include<iostream>
#include<vector>
using namespace std;
#define inf 100000
#define maxsize 1001
int g[maxsize][maxsize];
int parent[maxsize];
int dist[maxsize];
int n;
int m;
int sum;
using namespace std;
vector<int>mst;
void build()
{
	int v1, v2;
	int w;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = 0;
		}
		dist[i]= inf;
		parent[i] = -1;
	}
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2 >> w;
		g[v1][v2] = w;
		g[v2][v1] = w;
	}
}

void init(int x)       //初始化第一個點和到周圍點的距離
{
	dist[x] = 0;
	mst.push_back(x);
	for (int i = 1; i <= n; i++) {
		if (g[x][i]) {
			dist[i] = g[x][i];
			parent[i] = x;
		}
	}
}

int findmin()      //找點周圍路徑最短的點
{
	int min = inf;
	int xb = -1;
	for (int i = 1; i <= n; i++) {
		if (dist[i] && dist[i] < min) {
			min = dist[i];
			xb = i;
		}
	}
	return xb;
}
void prim(int s)
{
	init(s);
	while (1) {
		int v = findmin();
		if (v == -1)       //不存在這樣的點
			break;
		sum += dist[v];
		dist[v] = 0;
		mst.push_back(v);
		for (int i = 1; i <= n; i++) {
			if (g[v][i] && g[v][i] < dist[i]) {
				dist[i] = g[v][i];
				parent[i] = v;
			}
		}
	}
}
int main()
{
	build();
	prim(1);        //哪個點開始都無所謂的
	if (mst.size() == n)
		cout << sum;
	else
		cout << -1;
	return 0;
}

總結

以上是生活随笔為你收集整理的《数据结构》08-图7 公路村村通（最小生成树问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。