グラフ

• 頂点(vertex, node)と辺(edge) からなる
• 無向グラフと有効グラフがある
• 辺に重みのついたものを重み付きグラフという

  無向グラフ

• パス … 隣接している頂点の列
• 閉路 … 始点と終点が同じパス
• 連結グラフ … 任意の２頂点をつなぐパスが存在する
• 頂点の次数 … 頂点につながっている辺の数
• 木 … 連結グラフで閉路を持たないもの

  有効グラフ

• Directed Acyclic Graph … 有向グラフで閉路をもたないグラフ

グラフの表現

隣接行列

• V

  x

  V

  ２次元配列で表現。

• g[i][j]はi番目の頂点とj番の頂点を表す
• メモリ効率は悪い, O(|V|^2)のメモリを消費

  隣接リスト

• ある頂点から伸びている辺の頂点をリストで保持する

• メモリ効率がよい.O(

  V

  +

  E

  )

彩色問題

• 深さ優先探索で解く

  最短路問題

• ベルマンフォード法

  • d[i] = min

    d[j] + cost(j, i)

  • 閉路があるとだめ

  • O(

    V

    E

    )

• ダイクストラ法
  • すでに行ったところは無効にする

  • 隣接行列の場合はO(

    V

    ^2)

  • 隣接リストを使うとO(

    E

    )

    • 次に使う頂点の探索を最適化する必要がある

  • O(

    E

    log

    V

    )

  • 負の辺があるとだめ

    全点対最短路問題(ワーシャル-フロイド法)

経路復元

• d[j] = d[k] + cost[k][j]をたどって計算

  • O(

    E

    )

• 頂点を覚えておいても良い

  最小全域木

• 全域木(Spanning Tree) … 無向グラフの部分グラフで任意の２頂点を連結にするような木
• 最小全域木(Minimu Spanning Tree) … 辺にコストがあるときに辺のコストの和を最小にするもの

  プリム法

  クラスカル法