【データ構造】最小生成ツリー(プリムアルゴリズムとクルースカルアルゴリズム)
4393 ワード
主な内容
基本概念プリムアルゴリズムクルーズカールアルゴリズム(エッジ法)
現実生活の多くの問題は図に変換して解決することができる.例えば、通信ネットワークを最小コストで構築する方法、地図内の2つの場所間の最短パスを計算する方法、複雑なアクティビティにおける各サブタスクの完了のために最適な順序を探す方法などがあります.
4つの一般的なアルゴリズム:最小生成ツリー、最短パス、トポロジソート、キーパス.
基本概念
n都市間に通信連絡網を構築すると仮定すると,n都市を連通するにはn−1回線しか必要としない.このとき,最も経費を節約した上でどのように任務を遂行するかを考えるのは当然である.
1つの連通網のすべての生成ツリーのうち、各エッジの代価の和が最も小さい生成ツリーを、その連通網の最小生成ツリーと呼ぶ.
MST性質:最小生成ツリーには必ず最小重み値を持つエッジが存在する.プリム(Prim)アルゴリズムとクルスカル(Kruskal)アルゴリズムはMST特性を利用して最小生成ツリーを構成する2つのアルゴリズムである.
プリムアルゴリズムの核心思想は帰結点であり,時間複雑度はO(n)である.²),稠密な網に適用する.
クルーズカールアルゴリズムの核心思想は,時間的複雑度がO(elog 2 e)であり,疎網との併用である.
プリムアルゴリズム
(1)すべての頂点を集合Vに保存し、集計された点を集合Uに保存すると、集計されていない点を集合V-Uに保存する.
(2)図中の任意の開始頂点v 1を探し、v 1はUに帰属し、V-Uから離れる.
(3)頂点v 1はv 2,v 3,v 4の3つの隣接頂点が存在し、重み値が最も小さいエッジ(v 1,v 3)を探し出す.
(4)頂点v 3はUに戻り、V-Uから離れる.
(5)頂点v 1は隣接頂点v 2,v 4が残り、頂点v 3は隣接頂点v 2,v 4,v 5,v 6がある.
(6)(v 1,v 2)と(v 3,v 2)を比較し、重み値がより小さいエッジ(v 3,v 2)を導出する.(v 1,v 4)と(v 3,v 4)を比較し、両方の重み値は同じである.
*論理的な考え方では,(6)ステップ目は省略でき,すべてのエッジの重み値を直接比較し,そこから重み値が最も小さいエッジを選択する.しかし、コード実装では、データ冗長性を回避し、一部の意味が重なるデータをフィルタリングする必要があります.
(7)比較(v 3,v 2),(v 1,v 4)または(v 3,v 4),(v 3,v 5),(v 3,v 6)は、重み値が最も小さいエッジ(v 3,v 6)を見つける.
(8)頂点v 6はUに戻り、V-Uから離れる.
(9)頂点v 1の残りの隣接頂点v 4(v 3,v 2)の重み値がより小さいため、v 1~v 2の場合を考慮する必要はない)、頂点v 3の残りの隣接頂点v 2,v 4,v 5,頂点v 6には隣接頂点v 4,v 5がある.
(10)ここまで考えがはっきりしているはずです.
――隣接行列を記憶構造とする無方向網
(1)頂点集合Vは、隣接マトリクス図における頂点情報を格納するための一次元配列vexs[vexnum]に等価である.
(2)アルゴリズムの最も巧みなところである構造体配列closedge[vexnum]は,集合Uにおける最小エッジの頂点(adjvex)と最小エッジの重み値(lowcost)という情報を含む.
構造体配列closedge[]の使用は、中ステップ(6)の体現である.
closedge[vi-1]は頂点viを表し、lowcastが0でない場合、viは集合V-Uにある.lowcastが0と表記されると、viは集合Uに集計される.
(3)closedge[]内のすべての要素のlowcast属性が0になるまで、あるコードをループし、すなわちすべての頂点が集合Uに組み込まれる.
(コードを見る前に「隣接マトリクス」の知識を振り返ることができます)
クルーズカールアルゴリズム
プリムアルゴリズムが「加点法」なら、クルーズカールアルゴリズムは「加辺法」だ.
(1)n個の頂点からなる連通図をn個の連通成分、すなわち各頂点が1個の連通成分に分割する.
(2)図上のすべてのエッジを重み値で並べ替える.
(3)最小エッジから動作し、集計エッジの判断条件は、次の被選択エッジが連通成分を回路形成できないこと、すなわち、被選択エッジの2つの頂点headとtailが同じ連通成分上に存在できないことである.
(4)すべての頂点が同一の連通成分に集約されるまで、ループ内でセグメントコードが実行される.
――隣接行列を記憶構造とする無方向網
(1)重み値順に「発泡法」と「選択法」を用いることができる.
(2)ステップ(3)から,プリムアルゴリズムにおけるclosedge[]のような補助配列が必要であることが分かる.含まれる情報:各エッジのヘッダ頂点とテール頂点、およびエッジの重み値.
(3)同時に、各頂点が属する連通成分の判断を補助するタグ配列が必要である.
(4)1つの頂点をまとめた後、頂点の連通成分をその連通成分に組み込むように変更する.
基本概念プリムアルゴリズムクルーズカールアルゴリズム(エッジ法)
現実生活の多くの問題は図に変換して解決することができる.例えば、通信ネットワークを最小コストで構築する方法、地図内の2つの場所間の最短パスを計算する方法、複雑なアクティビティにおける各サブタスクの完了のために最適な順序を探す方法などがあります.
4つの一般的なアルゴリズム:最小生成ツリー、最短パス、トポロジソート、キーパス.
基本概念
n都市間に通信連絡網を構築すると仮定すると,n都市を連通するにはn−1回線しか必要としない.このとき,最も経費を節約した上でどのように任務を遂行するかを考えるのは当然である.
1つの連通網のすべての生成ツリーのうち、各エッジの代価の和が最も小さい生成ツリーを、その連通網の最小生成ツリーと呼ぶ.
MST性質:最小生成ツリーには必ず最小重み値を持つエッジが存在する.プリム(Prim)アルゴリズムとクルスカル(Kruskal)アルゴリズムはMST特性を利用して最小生成ツリーを構成する2つのアルゴリズムである.
プリムアルゴリズムの核心思想は帰結点であり,時間複雑度はO(n)である.²),稠密な網に適用する.
クルーズカールアルゴリズムの核心思想は,時間的複雑度がO(elog 2 e)であり,疎網との併用である.
プリムアルゴリズム
(1)すべての頂点を集合Vに保存し、集計された点を集合Uに保存すると、集計されていない点を集合V-Uに保存する.
(2)図中の任意の開始頂点v 1を探し、v 1はUに帰属し、V-Uから離れる.
(3)頂点v 1はv 2,v 3,v 4の3つの隣接頂点が存在し、重み値が最も小さいエッジ(v 1,v 3)を探し出す.
(4)頂点v 3はUに戻り、V-Uから離れる.
(5)頂点v 1は隣接頂点v 2,v 4が残り、頂点v 3は隣接頂点v 2,v 4,v 5,v 6がある.
(6)(v 1,v 2)と(v 3,v 2)を比較し、重み値がより小さいエッジ(v 3,v 2)を導出する.(v 1,v 4)と(v 3,v 4)を比較し、両方の重み値は同じである.
*論理的な考え方では,(6)ステップ目は省略でき,すべてのエッジの重み値を直接比較し,そこから重み値が最も小さいエッジを選択する.しかし、コード実装では、データ冗長性を回避し、一部の意味が重なるデータをフィルタリングする必要があります.
(7)比較(v 3,v 2),(v 1,v 4)または(v 3,v 4),(v 3,v 5),(v 3,v 6)は、重み値が最も小さいエッジ(v 3,v 6)を見つける.
(8)頂点v 6はUに戻り、V-Uから離れる.
(9)頂点v 1の残りの隣接頂点v 4(v 3,v 2)の重み値がより小さいため、v 1~v 2の場合を考慮する必要はない)、頂点v 3の残りの隣接頂点v 2,v 4,v 5,頂点v 6には隣接頂点v 4,v 5がある.
(10)ここまで考えがはっきりしているはずです.
――隣接行列を記憶構造とする無方向網
(1)頂点集合Vは、隣接マトリクス図における頂点情報を格納するための一次元配列vexs[vexnum]に等価である.
(2)アルゴリズムの最も巧みなところである構造体配列closedge[vexnum]は,集合Uにおける最小エッジの頂点(adjvex)と最小エッジの重み値(lowcost)という情報を含む.
構造体配列closedge[]の使用は、中ステップ(6)の体現である.
closedge[vi-1]は頂点viを表し、lowcastが0でない場合、viは集合V-Uにある.lowcastが0と表記されると、viは集合Uに集計される.
(3)closedge[]内のすべての要素のlowcast属性が0になるまで、あるコードをループし、すなわちすべての頂点が集合Uに組み込まれる.
(コードを見る前に「隣接マトリクス」の知識を振り返ることができます)
typedef struct /* closedge[vexnum]*/
{
Vextype adjvex;
Arctype lowcast;
} closedge[vexnum];
void MiniSpanTree_Prim(AMGraph G, Vextype vi)
{
int i = LocateVex(G, vi); /* vi */
closedge[i] = {NULL, 0}; /* vi U */
for(int vj = 1; vj <= G.vexnum; vj++) /* V-U vj， closedge[vj-1]*/
{
int j = LocateVex(G, vj);
if(j != i) closedge[j] = {vi, G.arcs[i][j]};
}
for(int k = 1; k < G.vexnum; k ++) /* U ， */
{
i = Min(closedge); /* Min() closedge[] lowcast ， i*/
/* ， V-U vj*/
closedge[i].lowcast = 0; /* vj U */
u0 = closedge[i].adjvex /*u0 U */
v0 = G.vexs[i]; /*v0 V-U */
cout< (6)*/
if(G.arcs[i][j] < closedge[j].lowcast)
closedge[j] = {G.vexs[i], G.arcs[i][j]};
}
} クルーズカールアルゴリズム
プリムアルゴリズムが「加点法」なら、クルーズカールアルゴリズムは「加辺法」だ.
(1)n個の頂点からなる連通図をn個の連通成分、すなわち各頂点が1個の連通成分に分割する.
(2)図上のすべてのエッジを重み値で並べ替える.
(3)最小エッジから動作し、集計エッジの判断条件は、次の被選択エッジが連通成分を回路形成できないこと、すなわち、被選択エッジの2つの頂点headとtailが同じ連通成分上に存在できないことである.
(4)すべての頂点が同一の連通成分に集約されるまで、ループ内でセグメントコードが実行される.
――隣接行列を記憶構造とする無方向網
(1)重み値順に「発泡法」と「選択法」を用いることができる.
(2)ステップ(3)から,プリムアルゴリズムにおけるclosedge[]のような補助配列が必要であることが分かる.含まれる情報:各エッジのヘッダ頂点とテール頂点、およびエッジの重み値.
(3)同時に、各頂点が属する連通成分の判断を補助するタグ配列が必要である.
(4)1つの頂点をまとめた後、頂点の連通成分をその連通成分に組み込むように変更する.
typedef struct /* */
{
Vextype head;
Vextype tail;
Arctype lowcast;
} Arcs[arcnum];
int VexSet[vexnum]; /*VexSet[vi-1] = i; vi i， */
void MiniSpanTree_Kruskal(AMGraph G)
{
for(int t = 0; t < arcnum; t++) /* */
cin>>Arcs[t].head>>Arcs[t].tail>>Arcs[t].lowcast;
Sort(Arcs); /* */
for(int t = 0; t < arcnum; t++) /* （ ） */
{
Headv = LocateVex(G, Arcs[t].head); /* */
Tailv = LocateVex(G, Arcs[t].tail);
VS_h = VexSet[HeadV]; /* */
VS_t = VexSet[Tailv];
if(VS_h != VS_t) /* */
{
cout<