5.4最小生成ツリー

2016 ワード
図の生成ツリーは、頂点セットで、エッジセットに1つのセットを見つけて、中にnつの頂点(すべての頂点)、n-1つのエッジがあって、このセットは1本の木を構成することができます.これが生成ツリーであり、最小生成ツリーは、このツリーのエッジ重みの和がすべての生成ツリーで最小である.
最小生成ツリーを実現するアルゴリズムは,頂点に向かうアルゴリズムとエッジに向かうアルゴリズムの2つに分けられる.
1.Primアルゴリズム(プリムアルゴリズム)
頂点に向かうアルゴリズムでは、まず1つの頂点をツリーに追加し、ツリーの頂点に最も近いツリーに追加されていない頂点をツリーに追加することが基本です.
//lowcost                 ，    ，                
for (i = 1; i < G.numVertexes;i++)
{
    min = INFINITY;
    while(j < G.numVertexes)//              
    {
        if (lowcost[j] != 0 && lowcost[j] < min)
        {
            min = lowcost[j];
            k = j;
        }
    }

    printf("")//          k
    lowcost[k] = 0;//  k          0，  k    

    for (j = 1; j < G.numVertexes; j++)
    {
        //      ，          k      lowcost  ，   lowcost
        if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
        {
            lowcost[j] = G.arc[k][j];
        }
    }
}

2.Kruskalアルゴリズム(クルーズアルゴリズム)
エッジ向けのアルゴリズムでは,最短のエッジをツリーに加え続けることが基本構想である.ただし、エッジが接続されてツリーにループが発生する可能性があるので、最短エッジが追加される前に、ツリーが図になるかどうかを判断します.
生成ツリーの本質はツリー状の連通図であり,Kruskalアルゴリズムが生成ツリーを形成する過程は,新しいエッジを絶えず追加することである.
この過程では,二つの状況にほかならない.
  • 新しいエッジが追加され、ツリーに頂点
    • が追加されました.
  • 新しいエッジを追加し、ツリーに1つの連通図(すなわち、すでに接続されている一連の頂点)を追加する第2のケースが存在する可能性があります.新しく追加された頂点がある連通図は、新しい連通図ではなく、同じ連通図の2つの点が接続してリングを形成しているので、この状況を判断するにはどうすればいいですか.すなわち、新しく追加されたエッジの2つの頂点が同じ連通図に存在するかどうか.
    • //   parent     0

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

//             ，            
for (i = 0; i< G.numEdges; i++)
{
    n = Find(parent, edges[i].begin);
    m = Find(parent, edges[i].end);

    if (n != m)
    {
        parent[n] = m;
        printf()//       
    }
}

    生成された連通図の点はいずれも<1,2>,<2,3><3,4>のようなシーケンスで記録される.parent配列,parent[1]=2,parent[2]=3,parent[3]=4の方式を用いる.
    したがってedges[i]に接続された2つの頂点は,同一の連通図内であれば,必ずFind()によって連通図シーケンスの最後の点を最終的に見つけることができる.したがって,このときm==nである.
    最短パスアルゴリズム:Bellman-fordアルゴリズム
    ノイズ除去/異常値処理