この問題は「最小全域木」を求める問題です。最小というのは重みの和が最小ということで、全域というのは元のグラフの全てのノードを持つグラフということで、木というのはループが無い連結グラフということです。この用語さえ知っていればあとは検索してアルゴリズムを見つけるだけです。
まず、検索して最初に出てくるプリム法を実装しましょう。
まず1点を適当に選びます。例題なら、例えばAを選びます。Aを端点とした辺をPriorityQueueに入れます。3辺入れることになります。PriorityQueueは重みが小さい辺から取り出せるようにしておきます。Pythonなら(重み,端点1,端点2)というタプルを入れればよいです。次にPriorityQueueから辺を取り出します。ACが取り出されます。これが最小全域木の一つの辺となります。Cを端点とした辺をPriorityQueueに入れます。ただし、すでに選ばれた点Aを端点とした辺は排除します。そして、PriorityQueueから辺を取り出して最小全域木の辺にします。これを(ノード数-1)回繰り返せば最小全域木が得られます。
