データ構造とアルゴリズム-スパニングツリー
スパニングツリーはグラフGのサブセットであり、すべての頂点が最小数のエッジで覆われています。したがって、スパニングツリーにはサイクルがなく、切断することはできません。
この定義により、すべての接続された無向グラフGには少なくとも1つのスパニングツリーがあるという結論を導き出すことができます。切断されたグラフには、すべての頂点にスパンできないため、スパニングツリーはありません。
1つの完全グラフから3つのスパニングツリーが見つかりました。完全な無向グラフは最大値を持つことができますnn-2 スパニングツリーの数、ここで nノードの数です。上記の例では、n is 3, したがって、 33−2 = 3 スパニングツリーが可能です。
スパニングツリーの一般的なプロパティ
これで、1つのグラフに複数のスパニングツリーを含めることができることがわかりました。以下は、グラフG −に接続されたスパニングツリーのいくつかのプロパティです。
接続されたグラフGは、複数の全域木を持つことができます。
グラフGのすべての可能な全域木は、同じ数のエッジと頂点を持っています。
スパニングツリーにはサイクル（ループ）がありません。
スパニングツリーから1つのエッジを削除すると、グラフが切断されます。つまり、スパニングツリーは minimally connected。
スパニングツリーに1つのエッジを追加すると、回路またはループが作成されます。つまり、スパニングツリーは次のようになります。 maximally acyclic。
スパニングツリーの数学的特性
スパニングツリーには n-1 エッジ、ここで n はノード（頂点）の数です。
完全グラフから、最大値を削除することにより e - n + 1 エッジ、スパニングツリーを構築できます。
完全グラフは最大値を持つことができます nn-2 スパニングツリーの数。
したがって、スパニングツリーは接続されたグラフGのサブセットであり、切断されたグラフにはスパニングツリーがないと結論付けることができます。
スパニングツリーの適用
スパニングツリーは基本的に、グラフ内のすべてのノードを接続するための最小パスを見つけるために使用されます。スパニングツリーの一般的な用途は次のとおりです。
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
小さな例を通してこれを理解しましょう。都市ネットワークを巨大なグラフとして考えてみてください。現在、最小限の回線ですべての都市ノードに接続できるように電話回線を展開することを計画しています。ここで、スパニングツリーが思い浮かびます。
最小スパニングツリー（MST）
加重グラフでは、最小全域木は、同じグラフの他のすべての全域木よりも最小の重みを持つ全域木です。実際の状況では、この重みは、距離、混雑、交通負荷、またはエッジに示される任意の値として測定できます。
最小スパニングツリーアルゴリズム
ここでは、2つの最も重要なスパニングツリーアルゴリズムについて学習します。
クラスカルのアルゴリズム
プリムのアルゴリズム
どちらも欲張りアルゴリズムです。