Kruscal算法

Kruscal算法也是最小生成树算法，这个算法感觉起来可能更直观一点，我们要求最小生成树，我们可以依次找图中的最小权重所在的边，只要这些边不构成回路就添加，知道覆盖所有的顶点。

算法的具体过程：

1、将权重排序，要对权重排序，在邻接矩阵中权重处理不是很方便，构建边的结构

typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

2、避免环的时候的处理手法，也就是通过一个点找到其下一个点，再根据这个点找下面一个点，依次。。。

int findParent(int *parent,int f)
{
    while(parent[f]>0)
    {
        f=parent[f];
    }
    return f;
}

这样就可以根据一个边的起点找到一个点，根据边的结束点找到另外一个连接点，如果找到这两个点不一致，则说明不是环。

具体的怎个代码如下：

#include <stdio.h>

#define MAXVEX 20

#define INFINITY 65535

typedef struct

{

    int arc[MAXVEX][MAXVEX];

    int numVertexes, numEdges;

}MGraph;

typedef struct

{

    int begin;

    int end;

    int weight;

}Edge;

void createMGraph(MGraph *g);

void sort(Edge edges[],MGraph *g);

void swapn(Edge *edges,int i,int j);

int findParent(int *parent,int f);

void minSpanTreeKruskal(MGraph g);

void createMGraph(MGraph *g)

{

    int i, j;

    g->numEdges=15;

    g->numVertexes=9;

    for (i = 0; i < g->numVertexes; i++)

    {

        for ( j = 0; j < g->numVertexes; j++)

        {

            if (i==j)

                g->arc[i][j]=0;

            else

                g->arc[i][j] = g->arc[j][i] = INFINITY;

        }

    }

    g->arc[0][1]=10;

    g->arc[0][5]=11;

    g->arc[1][2]=18;

    g->arc[1][8]=12;

    g->arc[1][6]=16;

    g->arc[2][8]=8;

    g->arc[2][3]=22;

    g->arc[3][8]=21;

    g->arc[3][6]=24;

    g->arc[3][7]=16;

    g->arc[3][4]=20;

    g->arc[4][7]=7;

    g->arc[4][5]=26;

    g->arc[5][6]=17;

    g->arc[6][7]=19;

    for(i = 0; i < g->numVertexes; i++)

    {

        for(j = i; j < g->numVertexes; j++)

        {

            g->arc[j][i] =g->arc[i][j];

        }

    }

}

void sort(Edge edges[],MGraph *g)

{

    int i,j;

    for(i=0;i<g->numEdges;i++)

    {

        for(j=i+1;j<g->numEdges;j++)

        {

            if(edges[i].weight>edges[j].weight)

            {

                swapn(edges,i,j);

            }

        }

    }

}

void swapn(Edge *edges,int i,int j)

{

    int temp;

    temp = edges[i].begin;

    edges[i].begin = edges[j].begin;

    edges[j].begin = temp;

    temp = edges[i].end;

    edges[i].end = edges[j].end;

    edges[j].end = temp;

    temp = edges[i].weight;

    edges[i].weight = edges[j].weight;

    edges[j].weight = temp;

}

void minSpanTreeKruskal(MGraph g)

{

    int i,j,n,m;

    int k =0;

    int parent[MAXVEX];

    Edge edges[MAXVEX];

    for(i = 0;i<g.numVertexes-1;i++)

    {

        for(j=i+1;j<g.numVertexes;j++)

        {

            if(g.arc[i][j]<INFINITY)

            {

                edges[k].begin = i;

                edges[k].end = j;

                edges[k].weight = g.arc[i][j];

                k++;

            }

        }

    }

    sort(edges,&g);

    for(i=0;i<g.numVertexes;i++)

    {

        parent[i] = 0;

    }

    printf("打印:\n");

    for(i = 0; i<g.numEdges; i++)

    {

        n= findParent(parent,edges[i].begin);

        m= findParent(parent,edges[i].end);

        if(n!=m)

        {

            parent[n] = m;

            printf("(%d,%d) %d\n",edges[i].begin,edges[i].end,edges[i].weight);

        }

    }

}

int findParent(int *parent,int f)

{

    while(parent[f]>0)

    {

        f=parent[f];

    }

    return f;

}

int main()

{

    MGraph g;

    createMGraph(&g);

    minSpanTreeKruskal(g);

    return 0;

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

巴特西

Kruscal算法

最新文章

热门文章