最小生成树算法

左手的ㄟ右手 2022-08-04 01:56 195阅读 0赞

最小生成树的两种算法是Prim算法和Kruskal算法，前者的复杂度只跟图的边数目相关：O(n^2)，后者的复杂度只跟图的顶点数目相关：O(eloge)。两个算法都依据贪心算法。

# Prim算法 #

从图中任选一个顶点（下面的算法选取编号为1的顶点）作为起始顶点，然后从此顶点开始，依次将各个顶点加入这个子树中，每次加入的都是未访问过的、权值最小的边和所连接的那个顶点。

题目：

有n个岛屿，为了方便大家，在这n个岛屿之间修n-1架桥，要使修桥的代价最小（桥的总长度最小）。

输入格式：第一行输入岛屿的数量m，接下来的m行依次输入各个岛屿之间的距离，自己到自己的距离为0.

输出格式：输出最小的代价值

输入：

0 1 2

1 0 5

2 5 0

输出：3

//如下的代码没有完全按照题目给出的输出格式，大体思想而已

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int prim(vector<vector<int> >& vec, int n) {
    	//visited数组标记某结点是否已经被访问
    	vector<bool> visited(n + 1, false);
    
    	//low记录某点到相邻、未被标记点的最小距离
    	vector<int> low(n + 1, 0);
    	int i, j, min;
    	int result = 0;  //result记录最小权值和
    	int pos = 1;     //选取下标为1的点作为起始点
    	visited[1] = true;
    
    	//将结点1(pos等于1)到各个结点的最小距离全部更新
    	for (i = 1; i <= n; ++i) {
    		if (i != pos)
    			low[i] = vec[pos][i];
    	}
    
    	//对除了下标为1的其他结点都找出最小权值并记录
    	for (i = 1; i < n; ++i) {
    		min = INT_MAX;
    		for (j = 1; j <= n; ++j) {
    			if (visited[j] == false && min > low[j]) {
    				min = low[j];
    				pos = j;
    			}
    		}
    		result += min;
    		visited[pos] = true;
    
    		//更新权值，low[j]记录pos到各个结点的最小权值
    		for (j = 1; j <= n; j++) {
    			if (visited[j] == false && low[j] > vec[pos][j])
    				low[j] = vec[pos][j];
    		}
    	}
    	return result;
    }
    
    int main() {
    	int m;
    	cin >> m;
    	if (m > 1000 || m < 3)
    		return 0;
    
    	int n = m + 1;
    	vector<vector<int> > vec(n, vector<int>(n, INT_MAX));
    	int i,j;
    	int value;
    	for (i = 1; i < n; ++i) {
    		for (j = 1; j < n; ++j) {
    			cin >> value;
    			vec[i][j] = value;
    		}
    	}
    	cout << prim(vec, m) << endl;
    	return 0;
    }

参考：

[http://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html][http_www.cnblogs.com_aiyelinglong_archive_2012_03_26_2418707.html]

# Kruskal算法 #

按照修路的代价由小到大对输入的路径以及相应代价进行排序，利用并查集，依次将排序后的结点依次加入集合中。

题目：(来自这里：[http://acm.hdu.edu.cn/showproblem.php?pid=1863][http_acm.hdu.edu.cn_showproblem.php_pid_1863])

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。

Sample Input

3 3
    1 2 1
    1 3 2
    2 3 4
      
       
      
       
        
       
    1 3
    2 3 2
    0 100

Sample Output

3
    ?

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct node {
    	int value;
    	int start;
    	int end;
    };
    
    bool comp(node& a, node& b) {
    	return a.value < b.value;
    }
    
    int set[100];
    int find_set(int x) {
    	int r = x;
    	while (r != set[r])
    		r = set[r];
    
    	int i = x, j;
    	while (set[i] != r) {
    		j = set[i];
    		set[i] = r;
    		i = j;
    	}
    	return r;
    }
    
    void merge(int x, int y) {
    	int fx = find_set(x);
    	int fy = find_set(y);
    	if (fx != fy)
    		set[fx] = fy;
    }
    
    void kruskal() {
    	int road, city, result = 0;
    	cin >> road >> city;
    
    	//初始化并查集，各点孤立
    	for (int i = 0; i < city; ++i)
    		set[i] = i;
    
    	vector<node> num(road);
    	for (int i = 0; i < road; ++i)
    		cin >> num[i].start >> num[i].end >> num[i].value;
    
    	sort(num.begin(), num.end(), comp);
    	
    	for (int i = 0; i < road; ++i) {
    		if (find_set(num[i].start) != find_set(num[i].end)) {
    			merge(num[i].start, num[i].end);
    			result += num[i].value;
    		}
    	}
    
    	//用于判断是否全部连通，只有根结点的父结点才是自己
    	int exist = 0;  
    	for (int i = 0; i < city; ++i) {
    		if (set[i] == i)
    			++exist;
    	}
    	
    	if (exist > 1)
    		cout << "非连通图" << endl;
    	else
    		cout << "最小代价为：" << result << endl;
    }
    
    int main() {
    	kruskal();
    }

参考：

并查集：[http://blog.csdn.net/dellaserss/article/details/7724401][http_blog.csdn.net_dellaserss_article_details_7724401]

Kruskal：[http://www.cnblogs.com/Veegin/archive/2011/04/29/2032423.html][http_www.cnblogs.com_Veegin_archive_2011_04_29_2032423.html]

[http_www.cnblogs.com_aiyelinglong_archive_2012_03_26_2418707.html]: http://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html
[http_acm.hdu.edu.cn_showproblem.php_pid_1863]: http://acm.hdu.edu.cn/showproblem.php?pid=1863
[http_blog.csdn.net_dellaserss_article_details_7724401]: http://blog.csdn.net/dellaserss/article/details/7724401
[http_www.cnblogs.com_Veegin_archive_2011_04_29_2032423.html]: http://www.cnblogs.com/Veegin/archive/2011/04/29/2032423.html