重み付けされたグラフとアプリケーション

各エッジに重みが割り当てられている場合、グラフは重み付きグラフになります。加重グラフには多くの実用的な用途があります。

上の図は、グラフが都市間の航空便数を表していると仮定しています。 BFS を適用して、2 都市間のフライト数の最小値を見つけることができます。以下の図に示すように、エッジが都市間の走行距離を表すと仮定します。すべての都市を接続するための最小合計距離はどうやって見つけますか? 2 つの都市間の最短経路をどのように見つけますか?この章では、これらの質問について説明します。前者は最小スパニング ツリー (MST) 問題として知られ、後者は最短パス問題として知られています。

前の章ではグラフの概念を紹介しました。エッジ配列、エッジ リスト、隣接行列、および隣接リストを使用してエッジを表現する方法と、Graph インターフェイス、AbstractGraph クラス、および UnweightedGraph クラス。前の章では、グラフを走査するための 2 つの重要なテクニック、深さ優先検索と幅優先検索も紹介し、実際的な問題を解決するために走査を適用しました。次の投稿では、重み付けされたグラフを紹介します。 post で最小スパニング ツリーを見つけるアルゴリズムと、 post で最短パスを見つけるアルゴリズムを学習します。

以上が重み付けされたグラフとアプリケーションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。