⑴ c语言数据结构 克鲁斯卡尔算法求无向网的最小生成树。
//要用到并查集判断回路，代码先给你吧，看不懂追问
#include<algorithm>
#include<stdio.h>
usingnamespacestd;
#defineMAXN1005//假设点数不超过1000
intn,m;
intfa[MAXN];
intid[MAXN];
structEdge{//边的数据结构
intfrom,to;
intlen;
};
Edgeedge[MAXN*MAXN];
boolcmp(Edgea,Edgeb){//边的比较函数
returna.len<b.len;
}
intfind(intx){//并查集，用于判断是否与已选择的边构成环
if(fa[x]==-1)
returnx;
else
returnfa[x]=find(fa[x]);
}
voidKruskal(intn){
memset(fa,-1,sizeof(fa));//初始化fa数组
intcnt=0;
for(inti=0;i<m;i++){
intu=edge[i].from;
intv=edge[i].to;
intt1=find(u);//找第一个点的起始点
intt2=find(v);//找第二个点的起始点
if(t1!=t2){//如果不相等，则不构成回路
fa[t1]=t2;
id[cnt]=i;
cnt++;
if(cnt==n-1)//当已选了n-1条边时，退出循环
break;
}
}
}
intmain()
{
while(scanf("%d%d",&n,&m))
{
inta,b,c;
for(inti=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[i].from=min(a,b);
edge[i].to=max(a,b);
edge[i].len=c;
}
sort(edge,edge+m,cmp);
Kruskal(n);
for(inti=0;i<n-1;i++)
{
intt=id[i];
printf("%d%d%d ",edge[t].from,edge[t].to,edge[t].len);
}
}
return0;
}
⑵ 求kruskal算法的C语言标准程序 越简单越好！
给你个C++的，和C差不多，就头文件、文件读取不一样
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
int v,e;
int L[1000]={0},R[1000]={0},W[1000]={0};
int f[100]={0};
int ans=0;
int find_set(int m)
{
if(m!=f[m]) f[m]=find_set(f[m]);
return f[m];
}
void Kruskal()
{
for(int i=1;i<=v; ++i)//初始化并查集
f[i]=i;
for(int i=1; i<=e; ++i)
{
int x,y;
x=find_set(L[i]); y=find_set(R[i]);
if(x!=y)
{
ans+=W[i];
f[y]=x;
}
}
fout<<ans;
}
void kp(int left,int right)
{
int i=left,j=right,mid=W[(left+right)>>1],t;
while(i<=j)
{
while(W[i]<mid) ++i;
while(W[j]>mid) --j;
if(i<=j)
{
t=L[i]; L[i]=L[j]; L[j]=t;
t=R[i]; R[i]=R[j]; R[j]=t;
t=W[i]; W[i]=W[j]; W[j]=t;
++i; --j;
}
}
if(i<right) kp(i,right);
if(left<j) kp(left,j);
}
int main()
{
fin>>v>>e;
for(int i=1; i<=e; ++i)
fin>>L[i]>>R[i]>>W[i];
kp(1,e);
Kruskal();
return 0;
}
⑶ 求一个学过数据结构（C语言版）的大神，有一个关于克鲁斯卡尔算法和普里姆算法的问题！
克鲁斯卡尔和prime算法都是最小生成树的贪心算法，可以证明其拥有最优解结构。证明简单的可以参考wiki，要严格证明请参考算法导论和计算机程序设计的艺术中的相关内容。由于其相关论文比较久远，我也不建议你去查了。
⑷ 怎么用克鲁斯卡尔算法输出全部最小生成树,求代码C语言
你只要按深度优先或按广度优先遍历这个图，就可以得到你所说的树了
⑸ C语言 克鲁斯卡尔算法怎么判断是否构造成回路求大手解答
使用并查集，每个讲克鲁斯卡尔的算法都会涉及并查集。
初始为每个顶点属于互不相同的集合，当添加一条边时，就把这两条边的顶点加入到同一集合。如果边的两顶点属于不同集合，就可以添加这条边，否则就不可以添加（会构成回路）。
对于集合的操作，有子集的划分。前几天的天津还是哪个regional网络预赛，就有个子集划分的题目。
⑹ 用C语言写kruskal算法
既然思路你都懂，我就直接贴程序咯！
如下源代码来自CSDN大神分享
源代码仅网页端可见！
#include<stdio.h>
#defineMAXSIZE30
#defineMAXCOST32767
typedefstruct
{
intu;//边的起始顶点
intv;//边的起始终点
intw;//边的权值
}Edge;
voidBubblesort(EdgeR[],inte)//冒泡排序，对数组R中的e条边按权值递增排序
{
Edgetemp;
inti,j,swap;
for(i=0;i<e-1;j++)//进行e-1趟排序
{
swap=0;
for(j=0;j<e-i-1;j++)
if(R[j].w>R[j+1].w)
{
temp=R[j];R[j]=R[j+1];R[j+1]=temp;//交换R[j]和R[j+1]
swap=1;//置有交换标志
}
if(swap==0)break;//本趟比较中未出现交换则结束排序
}
}
voidKruskal(intgm[][6],intn)//在顶点为n的连接图中构造最小的生成树，gm为连通网的邻接矩阵
{
inti,j,u1,v1,sn1,sn2,k;
intvest[MAXSIZE];//数组vest用于判断两顶点之间是否连通
EdgeE[MAXSIZE];//MAXSIZE为可存放边数的最大常量值
k=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i<j&&gm[i][j]!=MAXCOST)//MAXCOST为一个极大的常量值
{
E[k].u=i;
E[k].v=j;
E[k].w=gm[i][j];
k++;
}
Bubblesort(E,k);//采用冒泡排序对数组E中的k条边按权值递增排序
for(i=0;i<n;i++)//初始化辅助数组
vest[i]=i;//给每个顶点置不同连通分量编号，即初始时有n个连通分量
k=1;//k表示当前构造生成树的第n条边，初始值为1
j=0;//j为数组E中元素的下标，初值为0
while(k<n)//产生最小生成树的n-1条边
{
u1=E[j].u;v1=E[j].v;//取一条边的头尾顶点
sn1=vest[u1];
sn2=vest[v1];//分别得到这两个顶点所属的集合编号
if(sn1!=sn2)//两顶点分属于不同集合则该边为最小生成树的一条边
{
printf("Edge:(%d,%d),Wight:%d ",u1,v1,E[j].w);
k++;//生成的边数增1
for(i=0;i<n;i++)//两个集合统一编号
if(vest[i]==sn2)//集合编号为sn2的第i号边其边号改为sn1
vest[i]=sn1;
}
j++;//扫描下一条边
}
}
voidmain()
{
intg[6][6]={{100,6,1,5,100,100},{6,100,5,100,3,100},{1,5,100,5,6,4},
{5,100,5,100,100,2},{100,3,6,100,100,6},{100,100,4,2,6,100}};
Kruskal(g,6);//生成最小生成树
getchar();
}
运行如下图所示：
⑺ 数据结构C语言克鲁斯卡尔求最小生成树
你好 楼主。
很幸运的看到你的问题。
但是又很遗憾到现在还没有人回答你的问题。也可能你现在已经在别的地方找到了答案，那就得恭喜你啦。
对于你的问题我爱莫能助！
可能是你问的问题有些专业了。或者别人没有遇到或者接触过你的问题，所以帮不了你。建议你去问题的相关论坛去求助，那里的人通常比较多，也比较热心，可能能快点帮你解决问题。
希望我的回答也能够帮到你！
祝你好运。
快过年了，
最后祝您全家幸福健康快乐每一天！
⑻ 求最小生成树 利用Kruskal算法求图G的一棵最小生成树T，用c语言
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 并查集存储结构
// Tags: 值为-1则表示为根节点
struct DisjointSet
{
int *arr;// 值为父节点下标
int number;// arr元素个数
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化并查集结构
// Input: number - 元素的个数
// Output:s - number个元素自成一集的并查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 删除并查集结构
// Input: s - 并查集存储结构
// Output:s - 回收内存后的结构
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 获得某个结点的根节点
// Input: s - 并查集; index - 结点下标
// Output: return - 根节点下标
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];
return index;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合并index1和index2所在的两个集合
// Input: index1 - 结点1下标, index2 - 结点2下标
// Output: s - 并查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);
s.arr[root1] = root2;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 判断两个结点是否在同一个集合中
// Input: s - 并查集, index1 - 结点1下标, index2 - 结点2下标
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接矩阵
struct Graph
{
int **value;// 权值,-1表示无法到达
int number;
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一个图
// Input: g - 图的存储结构, number - 结点个数
// Output: g - 图
void InitGraph(Graph &g, int number)
{
int i = 0;
g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];
g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一个图
// Input: g - 图, number - 结点个数
// Output: g - 图的存储结构
void FreeGraph(Graph &g)
{
int i = 0;
for (i = 0; i < g.number; i++)
delete []g.value[i];
delete []g.value;
g.value = 0;
g.number = 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图在a，b间添加一条边
// Input:e1, e2 - 两个结点, value - 权值
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 显示一条边
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}
int a, b;// 边的两个结点
int value; // 边的权值
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根据权值判断两个边的大小
// Tags: 由于priority_queue是最大堆，所以这里小于号变成大于号，从而使priority_queue变成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户输入图的边
// Input: n - 加边的个数
// Output: graph - 加边后的图
// Tags: Console下用户输入点对(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}
int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;
Graph graph;// 图
DisjointSet set;// 并查集
priority_queue<OneEdge> edge;// 2叉堆
InitGraph(graph, NODE_NUMBER);// 初始化图
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化并查集
int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));
int min_pay = 0;// 最小耗费值
int add_num = 0;// 已经添加了几个边
OneEdge min_value_edge;// 当前权值最小边
while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 这里是因为了STL中2叉堆的结构中有一个缓冲区
// 需要将缓冲区中的每一个元素弹出来
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}
printf("%d", min_pay);
return 0;
}
这个是c++语言的，最小权值存储在min_pay中，树存储在并查集set中，且在获取最小权值路径的时候用了STL中的2叉堆，算法复杂度为O(|V| * lgE)
不知是否满足您的要求
⑼ C语言，克鲁斯卡尔算法里的找尾有什么作用
网络里网络一下。