克鲁斯卡尔算法求最小生成树 - C++教室 - C++论坛

楼主

问题点数：0 回复次数：8

克鲁斯卡尔算法求最小生成树

我想知道克鲁斯卡尔算法求最小生成树，怎么做，谢谢

搜索更多相关主题的帖子: 成树　克鲁斯卡尔　算法　小生　

第 2 楼

得分:0

就是用邻接矩阵那个？？
与prim用邻接矩阵生成的最小树一样
你是要算法，还是代码？？？
不是代码吧

嵌入式 ARM 单片机驱动 RT操作系统 J2ME LINUX Symbian C C++ 数据结构 JAVA Oracle 设计模式软件工程 JSP

第 3 楼

得分:0

yes 想看看代码来着算法会的

第 4 楼

得分:0

void Kruskal(edge edges[],int n){
int i,j,k,d;
int m1,m2;
edge c[MAX_VERTEX_NUM];

AdjMatrix S;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(i==j) S[i][j]=1;
else S[i][j]=0;
}

k=1;
d=0;
while(k<n){
for(i=0;i<n;i++){
if(S[i][edges[d].begin]==1) m1=i;
if(S[i][edges[d].end]==1) m2=i;
}
if(m1!=m2){
c[k-1]=edges[d];
printf("<< %d, %d >> %d\n", c[k-1].begin, c[k-1].end, c[k-1].weight);
k++;

for(j=0;j<n;j++){
if(S[m2][j]!=0){
S[m1][j]=S[m2][j];
S[m2][j]=0;
}
}
}
d++;
}
}

做最好的自己！

第 5 楼

得分:0

慢慢看。。。。。。

做最好的自己！

第 6 楼

得分:0

这个。。。我得好好看看。。。还不会呢。。

Go confidently in the directions of your dreams,live the life you have imagined!Just do it!
It is no use learning without thinking!

第 7 楼

得分:0

#include <stdio.h>
#define MAX_VERTEX_NUM 10
#define INFINITY 1000

typedef struct Edge
{
int weight;
}Edge, EdgeMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct MGraph
{
EdgeMatrix edges;
int vexnum;
int edgenum;
}MGraph;

typedef struct
{
int vertex;
int lowcost;
}Closedge;

void InitializeMG(MGraph &G)
{
G.edgenum = G.vexnum = 0;
for(int i = 0; i < MAX_VERTEX_NUM; ++i)
for(int j = 0; j < MAX_VERTEX_NUM; ++j)
G.edges[i][j].weight = INFINITY;
}

void CreateGraph(MGraph &G)
{
int i, j;
G.vexnum = 6;
G.edgenum = 10;

G.edges[0][1].weight = G.edges[1][0].weight = 6;
G.edges[0][2].weight = G.edges[2][0].weight = 1;
G.edges[0][3].weight = G.edges[3][0].weight = 5;
G.edges[1][2].weight = G.edges[2][1].weight = 5;
G.edges[1][4].weight = G.edges[4][1].weight = 3;
G.edges[2][3].weight = G.edges[3][2].weight = 5;
G.edges[2][4].weight = G.edges[4][2].weight = 6;
G.edges[2][5].weight = G.edges[5][2].weight = 4;
G.edges[3][5].weight = G.edges[5][3].weight = 2;
G.edges[4][5].weight = G.edges[5][4].weight = 6;

printf("\tv1\tv2\tv3\tv4\tv5\tv6\n");
for(i = 0; i < G.vexnum; ++i)
{
printf("\n\nv%d\t", i+1);
for(j = 0; j < G.vexnum; ++j)
printf("%d\t", G.edges[i][j].weight);
}
}

int GetMinIndex(MGraph G, Closedge closedge[])
{
int i, min_index = -1, min = INFINITY;
for(i = 1; i < G.vexnum; ++i)
if(closedge[i].lowcost && closedge[i].lowcost < min)
{
min = closedge[i].lowcost;
min_index = i;
}

return min_index;
}

bool MiniSpanTree_Prim(MGraph G, Closedge closedge[], int v0)
{
int i, j, k;
for(i = 0; i < G.vexnum; ++i)
{
closedge[i].vertex = v0;
closedge[i].lowcost = G.edges[v0][i].weight;
}
closedge[v0].lowcost = 0;

printf("\n\nThe Minimal-Span-Tree is composed of following edges:\nedge\t\tWeight\n");
for(i = 1; i < G.vexnum; ++i)
{
k = GetMinIndex(G, closedge);
if(k == -1)
return false;
printf("<%d, %d>\t\t%d\n",
closedge[k].vertex, k, closedge[k].lowcost);
closedge[k].lowcost = 0;
for(j = 0; j < G.vexnum; ++j)
if(G.edges[k][j].weight < closedge[j].lowcost)
{
closedge[j].vertex = k;
closedge[j].lowcost = G.edges[k][j].weight;
}
}
return true;
}

void main()
{
MGraph G;
Closedge closedge[6];

第 8 楼

得分:0

别人给我的给大家看看

第 9 楼

得分:0

#include<stdio.h>
#include<stdlib.h>

typedef struct
{
    char v1;
    char v2;
    int weight;
}Edge;
typedef struct{
     Edge space[100];
    int Elength;
}Headtype;

typedef struct
{
    char v;
    int flag;
}Dgree;
typedef struct{
  Dgree biao[20];
int Glength;
}Mark;

  void InitMark(Mark &M,int x){
    int j;
    M.Glength=x;
    printf("请依次输入这些点:\n");
    for(j=1;j<=x;j++)
    {
    scanf("%s",&M.biao[j].v);
     M.biao[j].flag=-1;
    }
      }
      void InitHeadType(Headtype &H,int y){
    int k;
    H.Elength=y;
    for(k=1;k<=y;k++)
    {
    printf("请输入边的关系:\n");
    scanf("%s%s%d",&H.space[k].v1,&H.space[k].v2,&H.space[k].weight);
    }

    }

void HeadAdjust(Headtype &H,int s,int m)
{    Edge rc;
    int p;
    rc=H.space[s];
    for(p=2*s;p<=m;p*=2)
    {
    if(p<m&&(H.space[p].weight<H.space[p+1].weight))
    ++p;
    if(rc.weight>H.space[p].weight)
    break;
    H.space[s]=H.space[p];
    s=p;
    }
    H.space[s]=rc;
}
void HeadSort(Headtype &H)
{    int q;
    Edge rb;
    for(q=H.Elength/2;q>0;--q)
    HeadAdjust(H,q,H.Elength);
    for(q=H.Elength;q>1;--q)
    {
        rb=H.space[1];
        H.space[1]=H.space[q];
        H.space[q]=rb;
        HeadAdjust(H,1,q-1);
    }
}


main (int)
{
    int Gnumber,Enumber,a,b,c;
    printf("请输入点的个数:\n");
    scanf("%d",&Gnumber);
    printf("请输入边数:\n");
    scanf("%d",&Enumber);
     Headtype H;
     Mark M;
    Dgree e1,e2;
     InitMark(M,Gnumber);
     InitHeadType(H,Enumber);
    HeadSort(H);
    printf("输出最小生成树;\n");
    for(a=1;a<=Enumber;a++)
    {
    for(b=1;b<=Gnumber;b++)
    {
     if(M.biao[b].v==H.space[a].v1)
    {e1=M.biao[b];  break; }
     }
    for(c=1;c<=Gnumber;c++)
    {
    if(M.biao[c].v==H.space[a].v2)
    {e2=M.biao[c];  break; }
    }
    while(e1.flag!=-1){
    b=e1.flag;
    e1=M.biao[e1.flag];}
    while(e2.flag!=-1){
    c=e2.flag;
e2=M.biao[e2.flag]; }
if(e2.v!=e1.v){
M.biao[b].flag=c;
    printf("(%c,%c):%d\n",H.space[a].v1,H.space[a].v2,H.space[a].weight);
        }
    }
}