Kruskal(クルースカル)最小生成ツリーアルゴリズム詳細+テンプレート

最小生成ツリー
n個の頂点を含む連通図においてn−1辺を選択し、極小連通サブ図を構成し、この連通サブ図におけるn−1辺の重み値の和を最小にすることを連通網の最小生成ツリーと呼ぶ.例えば、図G 4に示すような連通網については、重み値の総和が異なる複数の生成木があってもよい.
クルースカルアルゴリズムはクルースカル(Kruskal)アルゴリズムを紹介し,重み付け連通図の最小生成ツリーを求めるアルゴリズムである.
**基本思想:**重み値の小さい順にn-1辺を選択し、このn-1辺が回路を構成しないことを保証する.**具体的なやり方:**まずn個の頂点のみを含む森林を構築し、その後、重み値に従って小さいから大きいまで連通網の中から選択しながら森林に添加し、森林が木になるまで森林に回路を生じさせない.上記図G 4を例として、クルーズカールアルゴリズムは、最小生成ツリー結果を配列Rで保存すると仮定して、クルーズカールを実証する.
ステップ1:エッジ(E,F)をRに追加します.エッジ**(E,F)の重み値が最小であるため、最小生成ツリー結果Rに加えられる.ステップ2:エッジ(C,D)をRに追加します.前回の操作後、エッジ(C,D)の重み値が最小になるので、最小生成ツリー結果Rに加えます.ステップ3:エッジ(D,E)をRに追加します.前回の操作後、エッジ(D,E)の重み値が最小になるので、最小生成ツリー結果Rに加えられる.ステップ4:エッジ(B,F)をRに追加します.前の操作の後、エッジ(C,E)の重みは最小ですが、(C,E)は既存のエッジと回路を構成します.したがって,エッジ(C,E)をスキップする.同様に、エッジ(C,F)をスキップします.最小生成ツリー結果Rにエッジ(B,F)を加えます.ステップ5:エッジ(E,G)をRに追加します.前回の操作の後、エッジ(E,G)の重み値が最小になるので、最小生成ツリー結果Rに加えられる.ステップ6:エッジ(A,B)をRに追加します.前の操作の後、エッジ(F,G)の重みは最小であるが、(F,G)は既存のエッジと回路を構成する.したがって,エッジ(F,G)をスキップする.同様に、エッジ(B,C)をスキップします.最小生成ツリー結果R**にエッジ(A,B)を加えます.
このとき、最小生成ツリー構造が完了します!これに含まれるエッジは、(E,F)(C,D)(D,E)(B,F)(E,G)(A,B)の順である.前に紹介したクルーズカールアルゴリズムの基本思想とやり方に基づいて、クルーズカールアルゴリズムが重点的に解決しなければならない以下の2つの問題を理解することができる:問題の1対の図のすべてのエッジが重みの大きさに従ってソートされる.問題2最小生成ツリーにエッジを追加した場合,ループが形成されているかどうかをどのように判断するか.
問題がうまく解決すれば,ソートアルゴリズムを用いてソートすればよい.
問題2、処理方法は、「最小生成ツリー」における頂点の終点を記録し、頂点の終点は「最小生成ツリーで連通する最大頂点」である(この点については、後述する).そして,最小生存木に1つのエッジを追加するたびに,そのエッジの2つの頂点の終点が重なるか否かを判断し,重なるとループを構成する.最小生成ツリーRに(E,F)(C,D)(D,E)を加えると、これらのエッジの頂点に終点がある.
(01)Cの終点はFです.(02)Dの終点はFである.(03)Eの終点はFである.(04)Fの終点はFである.
終点については、すべての頂点を小さい順に並べた後です.頂点の終点は、[それに接続された最大頂点](Max Vertices)です.したがって,次に,(C,E)は重み値が最も小さいエッジであるが.しかしCとEのポイントはいずれもFであり,それらの終点は同じであるため,(C,E)を最小生成木に加えるとループが形成される.これが回路を判断する方法です.クルーズカールアルゴリズムのコード説明
前のアルゴリズム解析の後、具体的なコードを確認します.ここで「隣接マトリクス」を選択して説明すると、「隣接テーブル」実装の図については、後述するソースコードに対応するソースコードが与えられる.
1.基本定義

//     
typedef struct _graph
{
    char vexs[MAX];       //     
    int vexnum;           //    
    int edgnum;           //   
    int matrix[MAX][MAX]; //     
}Graph, *PGraph;

//      
typedef struct _EdgeData
{
    char start; //     
    char end;   //     
    int weight; //     
}EData;

Graphは隣接行列に対応する構造体である.vexsは頂点を保存するために使用され、vexnumは頂点数であり、edgnumは辺数である.matrixはマトリクス情報を保存するための2次元配列である.例えば、matrix[i][j]=1は、「頂点i(すなわちvexs[i])」と「頂点j(すなわちvexs[j])」が隣接点であることを示す.matrix[i][j]=0は、隣接点ではないことを示す.EDataは隣接マトリクスエッジに対応する構造体である.転入先http://www.cnblogs.com/skywang12345/2.クルーズカールアルゴリズムテンプレート1

/*
 *      （Kruskal)     
 */
void kruskal(Graph G)
{
    int i,m,n,p1,p2;
    int length;
    int index = 0;          // rets     
    int vends[MAX]={0};     //     "       "              。
    EData rets[MAX];        //     ，  kruskal       
    EData *edges;           //        

    //   "      "
    edges = get_edges(G);
    //     " "       (    )
    sorted_edges(edges, G.edgnum);

    for (i=0; i

テンプレート2

#include
#include
#define inf 0x3f3f3f3f
int map[110][110],dis[110],visit[110];
/*
      ：map          ，  map[1][2]=3，  1   2      3
dis                 ，  dis[3]=5，      3       5
visit     0  1，1         。
*/
int n,m;
int dijstra()
{
    int i,j,pos=1,min,sum=0;
    memset(visit,0,sizeof(visit));//    .，        
    for(i=1; i<=n; ++i)
    {
        dis[i]=map[1][i];
    }
    visit[1]=1;
    dis[1]=0;
    for(i=1; idis[j])
            {
                min=dis[j];
                pos=j;
            }
        }
        visit[pos]=1;//         
        for(j=1; j<=n; ++j)
        {
            if(visit[j]==0&&dis[j]>dis[pos]+map[pos][j])//  dis  
                dis[j]=dis[pos]+map[pos][j];
        }
    }
    return dis[n];
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m),n||m)//n  n  ，m  m  
    {
        for(i=1; i<=n; ++i)
        {
            for(j=1; j<=n; ++j)
            {
                map[i][j]=inf;//            
            }
        }
        int a,b,c;
        for(i=1; i<=m; ++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c