2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

• グラフの実装表現
  
  • 接続行列表現
    
    • 行に点、列に辺をとり、点が辺の端点なら１(始点なら１、終点なら−1)、そうでなければ、０
    • 必要領域：O(点の数ｘ辺の数)
  • 隣接行列表現
    
    • 行と列に点をとり、点のペア間に辺があれば１、なければ０。向きを考慮するときは辺があれば、１もしくは−１
    • 必要領域：O(点の数ｘ点の数)
  • 隣接リスト表現
    
    • 点をID化し、辺をID化する。辺の始点・終点を点のIDで登録する。点に隣接する辺のIDを登録する
    • 必要領域：O(２ｘ点の数ｘlog(辺の数))
• 隣接リスト表現Javaクラスとグラフ走査GraphScan
  
  • ある点からの到達可能性走査
    
    • ある点から到達可能な点とそのパスの和は、点を根とした(有向)木として得られる
      
      • その探索法は深さ優先探索と幅優先探索
    • 連結性
      
      • ある１点からの到達可能性走査によって、全転を含む木が得られる
    • 最短パス
      
      • 幅優先探索においては、走査により最短パスを与える。辺に非負の重みをつけて最短パスを求める方法であるDijkstraのアルゴリズムはこの一般化である
    • 強連結性
      
      • 有向グラフにおいて、２点が相互に到達可能であるとき、その２点は互いに強連結であるという