[アルゴリズム概念]成長木(生成木)
ひろがりじゅ
すべての頂点がつながっていて、循環のない木です.
グラフィックのn個の頂点をn-1本の幹線に接続する
1つの図には多くの伸長木が存在することができる.
深度優先検索または幅優先検索では、幹線を収集するだけで作成できます.
//깊이 우선탐색을 개조한 신장트리 간선 모으기
depth_search(v):
v를 방문처리
for u in (v에 인접한 정점 == u):
if (u가 방문되지 않았다면):
(v,u)를 신장 트리 간선으로 표시;
depth_search(u);伸長ツリーは、通信ネットワークの構築によく使用されます.例えば、最小リンクを用いてn個の位置を接続する通信ネットワークを構築する場合、最小リンク数は(n−1)である.そのため、伸びた木を探すことで解決できます.ただし、リンクごとに構築コストは異なります.したがって,最小のリンクを使用するだけでなく,最もコストの低い成長木を選択する必要がある.
最小生成ツリー(Minimum生成ツリーMST)
クルースカ
クリーム
Reference
この問題について([アルゴリズム概念]成長木(生成木)), 我々は、より多くの情報をここで見つけました https://velog.io/@gandi0330/알고리즘-개념-신장트리spanning-treeテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol