[データ構造]最小生成ツリー

≪最小生成ツリー｜Minimum Generation Tree｜oem_src≫:接続網を構築する最小コスト生成ツリー
1、Primアルゴリズム
Primアルゴリズムは、図の頂点の方向から、まず1つの頂点を決定し、その頂点から任意の他の頂点への連通代価を見つけ、次に、新しく決定されたノードに基づいて次のノードへの連通代価を更新する.
データ構造宣言:
  

struct Graph
{
    int vertexes[MAX];
    int arc[MAX][MAX];
    int sum_vertexes,sum_edges;
};

構築図:

void createGraph(Graph &graph)
{
    memset(graph.arc,0,sizeof(graph.arc));
    int x,y,weight;
    cout<<"       "<<endl;
    cin>>graph.sum_vertexes;
    cout<<"      "<<endl;
    cin>>graph.sum_edges;
    for(int i=0; i<graph.sum_vertexes; i++)
    {
        cout<<"   "<<i+1<<"      "<<endl;
        cin>>graph.vertexes[i];
    }
    for(int i=0; i<graph.sum_edges; i++)
    {
        cout<<"   "<<i+1<<"           "<<endl;
        cin>>x>>y>>weight;
        graph.arc[x][y]=graph.arc[y][x]=weight;
    }
}

Primアルゴリズム:

void Prim(Graph graph)
{
    int adjvex[MAX];
    int lowcost[MAX];
    lowcost[0]=-1;
    adjvex[0]=0;
    //   
    for(int i=1; i<graph.sum_vertexes; i++)
    {
        lowcost[i]=graph.arc[0][i];
        adjvex[i]=0;
    }
    //lowcost :-1        ，0        ，      
    for(int i=1; i<graph.sum_vertexes; i++)
    {
        //  <65535
        int min=65535;
        int k;
        for(int j=1; j<graph.sum_vertexes; j++)
        {
            if(lowcost[j]!=-1&&lowcost[j]!=0&&lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
        }
        lowcost[k]=-1;
        cout<<adjvex[k]<<"   "<<k<<endl;
        //  lowcost adjvex
        for(int j=1; j<graph.sum_vertexes; j++)
        {
            if(lowcost[j]!=-1&&graph.arc[k][j]!=0&&(graph.arc[k][j]<lowcost[j]||lowcost[j]==0))
            {
                    lowcost[j]=graph.arc[k][j];
                    adjvex[j]=k;
            }
        }
    }
}

2、Kruskalアルゴリズム
Primアルゴリズムは定点から出発し,Kruskalは辺の方向から考え,図の各辺を連通代価に従って小さいから大きいまで並べ替え,次いで結果に一度に辺を加え,リングの形成を避けるために判断機構を加える.
データ構造宣言:

struct  Edge
{
    int start;
    int stop;
    int weight;
};

struct Graph
{
    Edge edge[MAX];
    int sum_edges;
};

構築図:

void createGraph(Graph &graph)
{
    int x,y,w;
    cout<<"      "<<endl;
    cin>>graph.sum_edges;
    for(int i=0;i<graph.sum_edges;i++)
    {
        cout<<"   "<<i+1<<"           "<<endl;
        cin>>x>>y>>w;
        graph.edge[i].start=x;
        graph.edge[i].stop=y;
        graph.edge[i].weight=w;
    }
}

Kruskalアルゴリズム

void sortEdges(Graph &graph)
{
    Edge temp;
    for(int i=0;i<graph.sum_edges;i++)
    {
        for(int j=i+1;j<graph.sum_edges;j++)
        {
            if(graph.edge[i].weight>graph.edge[j].weight)
            {
                temp=graph.edge[i];
                graph.edge[i]=graph.edge[j];
                graph.edge[j]=temp;
            }
        }
    }
}

int Find(int *parent,int t)
{
    while(parent[t]!=0)
        t=parent[t];
    return t;
}

void Kruskal(Graph graph)
{
    int m,n;
    int parent[MAX];
    //   
    for(int i=0;i<graph.sum_edges;i++)
        parent[i]=0;
    for(int i=0;i<graph.sum_edges;i++)
    {
            m=Find(parent,graph.edge[i].start);
            n=Find(parent,graph.edge[i].stop);
            if(m!=n)
            {
                parent[m]=n;
                cout<<graph.edge[i].start<<"   "<<graph.edge[i].stop<<"   "<<graph.edge[i].weight<<endl;
            }
    }
}

やはりコードを书いて図の中の2つのつながっていない頂点の间の连络の代価を0で表したいと思って、结果は実现する判断の中で多くいくつか条件の判断を追加して、もし使うのが无限大ならば、便利になりました~~~