重み付きグラフ
正式名称
Weighted Graph（ウェイテッドグラフ）
一言でいうと
辺に距離やコストなどの数値を持つグラフ
初心者向け説明
重み付きグラフとは、辺に数値を設定したグラフです。
例えば、
5
A -------- B
\ /
2 3
\ /
C
というグラフでは、辺についている5、2、3が重みです。
重みには、
- 距離
- 時間
- 料金
- 通信コスト
- 遅延
などを設定できます。
例えばネットワークなら、ルータ同士の経路コストを重みとして考えることができます。
ポイント
- 辺に数値を持たせる
- 重みの意味は用途によって異なる
- 最短経路問題などで使われる
関連用語
関連記事
- グラフ理論とは？サイクリックグラフや重み付きグラフを基礎から理解しよう
🍯 はちみつメモ
重み付きグラフ = 「つながり」に数字を持たせたグラフ