プログラミングコンテストチャレンジブック 第2章 その6

第2章後半2-5 グラフを読みます。

まずグラフの一般的な話

  • 有効グラフと無向グラフ
    • 友人関係のグラフは無向グラフ、と書いてあるけど人物相関図は通常有向グラフで描かれるような
  • 重みつきグラフ
  • 連結グラフ
    • 全ての節のあいだにパスが存在する
  • 閉路を持たないグラフで連結グラフは「木」、連結グラフでないものは「森」
    • 辺の数が節の数-1 になっている連結グラフは木
  • 有向で閉路を持たないグラフ=DAG(Directed Acyclic Graph)
    • トポロジカル順序 - DAG の節に全ての辺の向きが一方向になるような番号付け
    • トポロジカルソート
  • グラフの表現方法
    • 隣接行列
    • 隣接リスト

グラフを用いた例題です

  • 二部グラフ判定
    • グラフに隣接する節が同じ色にならないように2色で塗り分けできるか
  • 最短路問題
    • 単一始点最短路問題(ベルマンフォード法)
    • 単一始点最短路問題(ダイクストラ法)
      • 負のコストの辺がない場合、距離(コスト)最短の節は最短路確定しているので使わないようにすることで計算量を下げる
    • 全点対最短路問題(ワーシャル-フロイド法)
        • シンプル! O(V^3) (V=節の数)だけど
    • 経路復元
    • 最小全域木
      • 辺を間引きして任意の2つの節の間にパスがあるようにする最小限の辺だけにした木
      • プリム法
      • クラスカル法
        • 辺をコストの小さい順にみて閉路ができなければ追加する