易截截图软件、单文件、免安装、纯绿色、仅160KB

最小生成树的Kruskal算法(C/C++) 附有测试数据和结果

/*
*算法原理:将图G 中的边按权数从小到大逐条考察,
* 按不构成圈的原则加入到T中(若有选择时, 不同的选
* 择可能会导致最后生成树的权数不同), 直到
* q(T) = p(G)-1为止, 即 T 的边数 = G 的顶点1 为止.
*算法中无圈性的判定比较麻烦,应该用标记法最好,
*对各个分支的顶点标号。
*我没仔细看书,其实书上写得很清楚,是老师提醒的 ^_^ 。
*参考书:2004,《图论及其应用》,科学出版社,孙惠泉 编著。
*/
#include<iostream>
#include<fstream>
#define N 100
using namespace std;
int n;//结点数
int a[N][N] = {0};
bool judgeNode(int flagNodes[N]){//判断是否还有未访问结点
for(int i = 0; i < n; i++)
if(flagNodes[i] == 0) return 1;
return 0;
}
void judgeSub(int flagSub[N], int x, int y){//标记分支
if(flagSub[x] != 0){
if(flagSub[y] == 0) flagSub[y] = flagSub[x];
else{
int min = flagSub[x] < flagSub[y] ? flagSub[x] : flagSub[y];
int max = flagSub[x] + flagSub[y] - min;
for(int i = 0; i < n; i++)
if(flagSub[i] == max)
flagSub[i] = min;
}
}
else{
if(flagSub[y] == 0){
int max = 0;
for(int i = 0; i < n; i++){
if(flagSub[i] != 0 && flagSub[i] > max)
max = flagSub[i];
}
flagSub[x] = flagSub[y] = ++max;
}
else flagSub[x] = flagSub[y];
}
}
bool judgeCircle(int flagSub[N], int x, int y){//判断生成树中无圈
if(flagSub[x] == 0 && flagSub[y] == 0) return 1;
if(flagSub[x] != flagSub[y]) return 1;
return 0;
}
void kruskal(){
int temp[N][N] = {0};
int flagNodes[N] = {0};
int flagSub[N] = {0};
int least = N;
int x = 0, y = 0;
cout<<"The edges of Optimal tree:"<<endl;
while(judgeNode(flagNodes)){
least = N;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){


相关文档:

读《c程序设计语言》一些感受

     最近在看《c程序设计语言》,就是那本被誉为C语言圣经的书籍。几天看了一章,感触很大,开篇就涉及到很多实用程序,不像谭浩强那样让人深陷语法细节之中,而且学完谭的书感觉什么都不能做。很多问题谭都回避了。所谓专业看看c程序设计语言的代码的风格就能感受到,一种精心雕琢的艺术品。第一章有 ......

C/C++与Java多维数组,遍历与最大值获取方法!

C/C++
/*
* File: main.cpp
* Author: Vicky
*
* Created on 2010年4月29日, 上午9:46
*/
#include <iostream>
using namespace std;
int maximum(int[], int);
int main(int argc, char** argv) {
// int sg[3][4] = {
int sg[][4] = {
{68, 77, 73, 86},
{87, 96, 7 ......

C/C++ 头文件 常用头文件功能查询表

#include <assert.h>    //设定插入点
#include <ctype.h>     //字符处理
#include <errno.h>     //定义错误码
#include <float.h>     //浮点数处理
#include <fstream.h>    //文件输入/输出
#include  ......

C/C++ 常见误区


C/C++ 常见误区
 
1. C++虽然主要是以C的基础发展起来的一门新语言,但她不是C的替代品,不是C的升级,C++和C是兄弟关系。没有谁比谁先进的说法,更重要的一点是C和C++各自的标准委员会是独立的,最新的C++标准是C++98,最新的C标准是C99。因此也没有先学C再说C++的说法,也不再(注意这个"不再")有C++语法 ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号