Design-and-analysis-of-algorithms-spanning-tree
DAA-スパニングツリー
- スパニングツリー*は、すべての頂点が最小数のエッジで接続されている無向グラフのサブセットです。
すべての頂点がグラフで接続されている場合、少なくとも1つのスパニングツリーが存在します。 グラフには、複数のスパニングツリーが存在する場合があります。
プロパティ
- スパニングツリーにはサイクルがありません。
- 他の頂点から任意の頂点に到達できます。
例
次のグラフでは、強調表示されたエッジがスパニングツリーを形成しています。
最小スパニングツリー
- Minimum Spanning Tree（MST）*は、すべての頂点を最小の総エッジウェイトと一緒に接続する、接続された重み付き無向グラフのエッジのサブセットです。 MSTを導出するには、PrimのアルゴリズムまたはKruskalのアルゴリズムを使用できます。 したがって、この章では、Primのアルゴリズムについて説明します。
すでに説明したように、1つのグラフに複数のスパニングツリーが存在する場合があります。 n 個の頂点がある場合、スパニングツリーには n-1 個のエッジが必要です。 このコンテキストで、グラフの各エッジが重みに関連付けられ、複数のスパニングツリーが存在する場合、グラフの最小スパニングツリーを見つける必要があります。
さらに、重複する重み付きエッジが存在する場合、グラフには複数の最小スパニングツリーが含まれることがあります。
上記のグラフでは、スパニングツリーを示していますが、これは最小スパニングツリーではありません。 このスパニングツリーのコストは、（5 + 7 + 3 + 3 + 5 + 8 + 3 + 4）= 38です。
Primのアルゴリズムを使用して、最小スパニングツリーを見つけます。
プリムのアルゴリズム
プリムのアルゴリズムは、最小スパニングツリーを見つける貪欲なアプローチです。 このアルゴリズムでは、MSTを形成するために、任意の頂点から開始できます。
Algorithm: MST-Prim’s (G, w, r)
for each u є G.V
u.key = ∞
u.∏ = NIL
r.key = 0
Q = G.V
while Q ≠ Ф
u = Extract-Min (Q)
for each v є G.adj[u]
if each v є Q and w(u, v) < v.key
v.∏ = u
v.key = w(u, v)関数Extract-Minは、最小のエッジコストで頂点を返します。 この関数はmin-heapで機能します。
例
Primのアルゴリズムを使用して、任意の頂点から開始できます。頂点 1 から開始しましょう。
頂点 3 は最小のエッジコストで頂点 1 に接続されているため、エッジ*（1、2）*がスパニングツリーに追加されます。
次に、エッジ*（2、3）は、エッジ *\ {（1、2）、（2、3）、（3、4）、（3、7）} の最小値であると見なされます。
次のステップでは、最小コストでエッジ*（3、4）および（2、4）を取得します。 エッジ（3、4）*はランダムに選択されます。
同様に、エッジ*（4、5）、（5、7）、（7、8）、（6、8）および（6、9）*が選択されます。 すべての頂点にアクセスすると、アルゴリズムが停止します。
スパニングツリーのコストは、（2 + 2 + 3 + 2 + 5 + 2 + 3 + 4）= 23です。 このグラフには、 23 未満のコストのスパニングツリーはありません。
