Primアルゴリズム(プリムアルゴリズム)

説明:
1つの連通図の生成ツリーは、図中のすべての頂点を含む極小連通サブマップを指すが、1つのツリーを構成するのに十分なn−1エッジしかない.連通網を構築する最小コスト生成ツリーを最小生成ツリーとする.Primアルゴリズムは最小生成ツリーを構築するアルゴリズムである.
定義:
N=(P,{E})は連通網であり,TEはN上の最小生成ツリーにおける辺の集合であると仮定する.アルゴリズムはU={U 0}から(U 0はVに属する).すべてのuがUに属し、vがV-Uに属するエッジ(u,v)がEに属する中で、最もコストの小さいエッジ(u 0,v 0)が集合TEに組み込まれ、同僚v 0がUに組み込まれ、U=Vを知るまで繰り返し実行します.このときTEには必ずn-1辺があり,T=(V,{TE})はNの最小生成木である.
機能:
もしあなたが電信の実施エンジニアであれば、1つの町の9つの村のために通信ネットワークを設置する必要があります.村はこの町に散らばっていて、村ごとに一定の距離があります.primアルゴリズムで接続方法を見つけることができます.このようにして、全体の経路が最も短いことを保証することができます.
時間複雑度:O(n 2)
コード:

#include <stdio.h>

#include <stdlib.h>

#define MAXVERTEX 10

#define INF 65535

typedef char VertexType;

typedef int EdgeType;

typedef struct MGraph

{

    VertexType data[MAXVERTEX];

    EdgeType edge[MAXVERTEX][MAXVERTEX];

    int numVertex;

    int numEdge;

}MGraph;

//     

void CreateMGraph(MGraph *G)

{

    int i = 0,j = 0,k = 0,w = 0;

    VertexType c;

    printf("             ：       ，      :
");

    scanf("%d,%d",&G->numVertex,&G->numEdge);

    fflush(stdin);

    printf("          ,       :
");

    scanf("%c",&c);

    while(i < G->numVertex)

    {

        if(c == '
')

            break;

        G->data[i] = c;

        i++;

        scanf("%c",&c);

    }

    for(i = 0;i < G->numVertex;i++)

    {

        for(j = 0;j < G->numVertex;j++)

        {

            if(i == j)

                G->edge[i][j] = 0;

            else

                G->edge[i][j] = INF;

        }

    }

    fflush(stdin);

    for(k = 0;k < G->numEdge;k++)

    {

        printf("    vi-vj        i   j ，    w，       ，      :
");

        scanf("%d,%d,%d",&i,&j,&w);

        G->edge[i][j] = w;

        G->edge[j][i] = G->edge[i][j];

    }

    printf("
        ：
");

    for(i = 0;i < G->numVertex;i++)

    {

        for(j = 0;j < G->numVertex;j++)

        {

            printf("%d ",G->edge[i][j]);

        }

        printf("
");

    }

}



void Prim(MGraph *G)

{

    int i = 0,j = 0,k = 0,min,m;

    int adjvex[MAXVERTEX];

    int lowcost[MAXVERTEX];

    for(i = 0;i < G->numVertex;i++)

    {

        adjvex[i] = 0;

    }

    lowcost[0] = 0;

    for(i = 1;i < G->numVertex;i++)

    {

        lowcost[i] = G->edge[0][i];

    }

    for(i = 1;i < G->numVertex;i++)

    {

        j = 1,k = 0;

        min = INF;

        while(j < G->numVertex)

        {

            if(lowcost[j] != 0 && lowcost[j] < min)

            {

                min = lowcost[j];

                k = j;

            }

            j++;

        }

        printf("(%d,%d) ",adjvex[k],k);

        lowcost[k] = 0;

        for(j = 1;j < G->numVertex;j++)

        {

            if(lowcost[j] != 0 && G->edge[k][j] < lowcost[j])

            {

                lowcost[j] = G->edge[k][j];

                adjvex[j] = k;

            }

        }

    }

}

int main()

{

    MGraph G;

    CreateMGraph(&G);

    printf("
******************************
");

    printf("
  Prim          ：
");

    Prim(&G);

    printf("
******************************
");

    return 0;

}