Min-heap
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/12/05 08:32 UTC 版)
初期化 入力: グラフ graph、辺の重みを返す関数 weight-function、初期頂点 initial vertex全頂点をまだ見ていない状態に初期化し、initial vertex を木に追加し、最小グラフから最小距離を除去することを考慮して全ての頂点を min-heap Q に置く。 for each vertex in graph set min_distance of vertex to ∞ set parent of vertex to null set minimum_adjacency_list of vertex to empty list set is_in_Q of vertex to trueset distance of initial vertex to zeroadd to minimum-heap Q all vertices in graph. アルゴリズム 上の初期化アルゴリズムで、次の状態になっている。nearest vertex とは Q[0] にあり、これが最新の追加である。 fringe とは Q 上の v であり、最も近い頂点を除去した後で v の距離が ∞ より小さいもの。 not seen とは Q 上の v であり、最も近い頂点を除去した後で v の距離が ∞ であるもの。 このwhileループは、remove minimum がヌルを返すと終了する。隣接リストは有向グラフを返せるように設定する。時間計算量: ループについては V、remove 関数については log(V) while latest_addition = remove minimum in Q set is_in_Q of latest_addition to false add latest_addition to (minimum_adjacency_list of (parent of latest_addition)) add (parent of latest_addition) to (minimum_adjacency_list of latest_addition) 時間計算量: E/V、平均頂点数 for each adjacent of latest_addition if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) < min_distance of adjacent) set parent of adjacent to latest_addition set min_distance of adjacent to weight-function(latest_addition, adjacent) 時間計算量: log(V)、ヒープの深さ update adjacent in Q, order by min_distance
※この「Min-heap」の解説は、「プリム法」の解説の一部です。
「Min-heap」を含む「プリム法」の記事については、「プリム法」の概要を参照ください。
- Min-heapのページへのリンク