スパニングツリーアルゴリズムの直感的な理解

スパニングツリーアルゴリズムの目的はループがない一つの経路をつくること

スパニングツリーアルゴリズムは水流をイメージするとわかりやすい

地面にはネットワーク上の溝があり、各溝交点がノードとする

ノードの中から任意にノードを一つ決めそれを Root ノードとする

Root ノードから水を流すと、他のそれぞれのノードに対して、もっとも水が早く届く Route (発音が似ててややこしい）が必ず一つ決まる

まったく同じ速度で複数の route から水が届くことがあるが後述するように一旦無視

もっとも水が早くとどくという制約上、出来上がった route にはループがない

もし同じ速度で届いた場合はループが起きるが、その場合は何らかの規則でどれか一つの route を選べばいい

教科書的なスパニングツリーアルゴリズムは前述を実現するもの

ルートポートの選択は、各ノードの、最も早く流れ着く水流の方向を表している

代表ポートの選出は各溝の両端のうち、最も早く水が到達してくる方向を示している

そしてそれ以外をブロックする、つまり残った線が前述の水流の経路になる

わかりずらいので可視化したい…

ルートポートで距離がまったく同じ場合はどう算出するのだろう