kruskal算法
对于c语言，指针是灵魂，特别是在稍微高级点的程序中，指针是必不可少的。以下程序没有用到链表，结构体用到了。当然如果你一定要用二维数组代替结构体去存储也行，代码会变得相当麻烦而且可读性差，维护困难。
另外注释加上了。代码临时写成，自带个人风格呵呵。
#include <stdio.h>
#include <stdlib.h>
#define TURE 1
#define FALSE 0
#define MAX 1000
#define abs(a) a > 0 ? a : -a
//图相关----------------------
typedef struct Tnode
{
int loc;
struct Tnode *next;
} Tnode; //顶点存放结点
typedef struct Ttable
{
Tnode *head;
Tnode *rear;
int length;
} Ttable; //顶点链表结构
typedef int ArcCell; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/
typedef int booleanType; //状态变量
typedef struct
{
ArcCell **arcs; /*邻接矩阵*/
int vexnum; /*图的顶点数和弧数*/
} MGraph; /*（Adjacency Matrix Graph）*/
//----------------------------
//队列相关（链式）-------------
typedef struct QNode //队列结点
{
int data;
struct QNode *next;
} QNode;
typedef struct //队列
{
QNode *front, *rear;
} LinkQueue;
//-----------------------------
MGraph G; //图
ArcCell **steparcs; //辅助矩阵
Ttable TE; //顶点链表指针
booleanType *visited; //建立标志数组(全局量）
LinkQueue Q; //定义队列
int GetGraph(MGraph *G); //建立图结构
void Back(); //还原矩阵
int kruskalTravel(MGraph G); //克鲁斯卡尔算法建立最小生成树
int MinSearch(MGraph G, int *i, int *j); //查找权值最小的边，以i，j返回其两端顶点。
int FirstAdjVex(int v);
int NextAdjVex(int v, int w);
int InitQueue(LinkQueue *Q); //初始化队列
int EmptyQueue(LinkQueue Q); //判空
int EnQueue(LinkQueue *Q, int v); //入队
int OutQueue(LinkQueue *Q); //出队
int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y); //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE
int main()
{
GetGraph(&G);
printf("Kruskal:\n");
kruskalTravel(G);
return 0;
}
int GetGraph(MGraph *G) //建立邻接矩阵
{
int i, j;
scanf("%d", &(G->vexnum));
G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum);
for(i = 0; i < G->vexnum; i++)
{
G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum);
} //建立二维动态数组
for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
scanf("%d", G->arcs[i] + j);
}
} //输入数据
return 0;
}//GetGraph
int kruskalTravel(MGraph G) //克鲁斯卡尔算法建立最小生成树
{
int i, j;
int N = G.vexnum;
steparcs = (ArcCell**)malloc(sizeof(ArcCell*) * G.vexnum); //建立二维动态数组
for(i = 0; i < G.vexnum; i++)
{
steparcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G.vexnum);
} //建立二维动态数组
for(i = 0; i < G.vexnum; i++) //初始化辅助矩阵
{
for(j = 0; j < G.vexnum; j++)
{
steparcs[i][j] = 0;
printf("%d ", steparcs[i][j]);
}
printf("\n");
}
printf("\n");
while(N > 1) //只要剩余的连通分量大于一，就继续链接各个连通分量
{
//查找权值最小的边，以i，j返回其两端顶点。如果两个顶点属于同一连通分量，则查找权次最小边，标志矩阵为负
MinSearch(G, &i, &j);
if(!WFSTravel(&G, &Q, i, j)) //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE
{
steparcs[i][j] = steparcs[j][i] = G.arcs[i][j]; //将符合条件的边和顶点并入到连通分量中
G.arcs[i][j] *= -1; //标志邻接矩阵，表明此条边已经查询过
G.arcs[j][i] *= -1;
N--; //剩余的连通分量
for(i = 0; i < G.vexnum; i++) //输出本次步骤
{
for(j = 0; j < G.vexnum; j++)
{
printf("%d ", steparcs[i][j]);
}
printf("\n");
}
printf("\n");
} //if
} //while
return 0;
}
int MinSearch(MGraph G, int *i, int *j) //查找权值最小的边，返回其值，并以i，j返回其两端顶点。
{
int temp = MAX; //存放当前最小值
int m, n;
for(n = 0; n < G.vexnum; n++) //循环查找
{
for(m = 0; m < G.vexnum; m++)
{
if(G.arcs[n][m] > 0 && G.arcs[n][m] < temp) //找最小值
{
temp = G.arcs[n][m];
*i = n;
*j = m;
}
}
}
return temp;
}
int FirstAdjVex(int v)
{
int i;
for(i = 0; i < G.vexnum; i++)
if(steparcs[v][i] != 0)
return i;
return -1;
}
// 返回下一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
int NextAdjVex(int v, int w)
{
int i;
for(i = w + 1; i < G.vexnum; i++)
if(steparcs[v][i] != 0)
return i;
return -1;
}
int InitQueue(LinkQueue *Q) //初始化队列
{
Q->front = Q->rear = (QNode*)malloc(sizeof(QNode)); //头结点
return 0;
}
int EmptyQueue(LinkQueue Q) //判空
{
return Q.front == Q.rear ? 1 : 0;
}
int EnQueue(LinkQueue *Q, int v) //入队
{
Q->rear->next = (QNode*)malloc(sizeof(QNode));
Q->rear = Q->rear->next;
Q->rear->data = v;
return 0;
}
int OutQueue(LinkQueue *Q) //出队
{
int e;
QNode *p;
if(Q->front == Q->rear)
{
printf("Queue Empty\n");
exit(0);
}
p = Q->front;
Q->front = Q->front->next;
e = Q->front->data;
free(p);
return e; //返回队头元素
}
//广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE
int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y)
{
int v, vtop = x, i;
visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum);
InitQueue(Q);
for(v = 0; v < G->vexnum; v++) //初始化标志数组
{
visited[v] = FALSE;
}
v = vtop; //初始查询顶点
if(!visited[v]) //如果没有遍历过，从此处开始遍历
{
visited[v] = TURE; //遍历该结点并标志结点状态
EnQueue(Q, v);
while(!EmptyQueue(*Q)) //如果队列中有元素，继续访问其邻接点
{
i = OutQueue(Q);
for(v = FirstAdjVex(i); v >= 0; v = NextAdjVex(i, v)) //寻找一个顶点的所有邻接点
{
if(!visited[v]) //访问未访问过的顶点
{
visited[v] = TURE;
if(v == y)
{
G->arcs[x][y] *= -1; //标志邻接矩阵，表明此条边已经查询过
G->arcs[y][x] *= -1;
return 1;
}
EnQueue(Q, v);
}
} //寻找一个顶点的所有邻接点
} //如果队列中有元素，继续访问其邻接点
} //如果没有遍历过，从此处开始遍历
return 0;
}//WFSprint
② kruskal算法的流程图。
我也在找啊```~~~
③ 什么是Kruskal算法如何避圈
1. Kruskal算法
(1) 算法思想
K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
初始时没有任何边被选择。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。
④ kruskal算法的介绍
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
⑤ kruskal算法是什么
kruskal算法是求加权连通图的最小生成树的算法。
kruskal算法总共选择n- 1条边，(共n个点)所使用的贪心准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。
kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
Kruskal算法基本思想：
每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量。
排序使用Quicksort(O(eloge))。
检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数。
Union-Find使用rank启发式合并和路径压缩。
总复杂度O(eloge)=O(elogv) (因为e<n(n-1)/2)。
⑥ 求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;
}
⑦ kruskal算法的举例描述
克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。
首先第一步，我们有一张图，有若干点和边
第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。
排序完成后，我们率先选择了边AD。这样我们的图就变成了
.
.
.
.
.
.
第二步，在剩下的边中寻找。我们找到了CE。这里边的权重也是5
.
.
.
.
.
.
依次类推我们找到了6,7,7。完成之后，图变成了这个样子。
.
.
.
.
.
.
下一步就是关键了。下面选择那条边呢？ BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。
最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是下图：
.
.
.
.
.
.
到这里所有的边点都已经连通了，一个最小生成树构建完成。
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
⑧ Kruskal算法适合于什么图
边数较少可以用kruskal,因为kruskal算法每次查找最短的边。
边数较多可以用prim，因为它是每次加一个顶点，对边数多的适用。
⑨ kruskal算法
给每个子树一个不同的编号，对每一个顶点引入一个标记t，表示这个顶点所在的子树编号。当加入一条红色边，就会使该边两端点所在的两个子树连接起来，成为一个子树，从而两个子树中的顶点标记要改变成一样。综上，可将Kruskal算法细化使其更容易计算机实现。
kruskal应该是递归算法吧，在定义图中各端点时，可以多设一个标记，把图递归遍历一遍，在同一连同子图上的点，标记为一样的整型数值即可。
参考：http://ke..com/view/580403.htm