深さ優先探索

• グラフ上のあるノードからスタートし、隣接するノードを『訪問』する。『訪問中』のノードからさらに訪問可能なノードを『訪問』し、『訪問先』がなくなるまで続け、なくなったら、『訪問先』探索をまだ済ませていない『訪問中』のノードについて同様の処理を繰り返す
  
  • 連結か
    
    • 『訪問できる』ノードがなくなったときに、すべてのノードが訪問されていれば、『連結』であることがわかる
  • 閉路があるか
    
    • 『訪問先』探索中に、『すでに訪問したノード』に『再度訪問しそう』になったら、閉路を見出したことになる
• このアルゴリズムでは、すべてのノードとエッジが調べつくされる
• 隣接リスト表現での深さ優先探索
  
  • に比例：疎グラフで効率的
• 隣接行列表現での深さ優先探索
  
  • に比例：疎グラフで非効率的