プロジェクトの1つに隣接行列を作成しましたが、その行列から最小全域木を構築できる必要があります。読んでみると、この場合にはプリムのアルゴリズムが最適であるように見えますが、作業する必要のあるグラフの少なくとも1つに約数千のグラフがあることを知っているため、グラフが1つの大きな連結成分であるとは想定できません。接続されたコンポーネント。プリムのアルゴリズムはここでも実行可能ですか？実行可能な場合、私が行う必要のある追加のことはありますか？
ここではJavaでコーディングしていますが、隣接行列をうまく構築できます。この部分に固執しているだけです。
つまり、スパニングツリーがない可能性があるということですか？この場合、プリムは問題ありません。選択した列に可能なパスがあることを確認するチェックを追加する必要があります。スパニングツリーがない場合は、それを使って何かをしようとするのは複雑になりますが、ツリーに追加したすべての頂点を削除し、残りを新しいグラフとして扱う必要があります。
編集：マトリックス（google'D1 prims matrix'）で手作業でプリムを実行する場合、選択した列にアークがないことの意味を簡単に視覚化できます。
グラフが接続されていない限り、最小スパニング ツリーのようなものはありません。
そのため、次の 2 つのいずれかを実行したい場合があります。接続されているすべてのコンポーネントの最小スパニング フォレストを構築します。または、エッジを追加してコンポーネントを接続することにより、グラフ全体の MST を構築します。それがどれであるかは、問題のドメインによって異なります。
それとも、グラフが接続されていないことを検出し、それが不可能であることを示すことになっているのでしょうか? それは簡単です。