07-17 田中_勉強会資料

参考文献

0. はじめに --- グラフ探索の動機

1. グラフ

グラフ (graph) とは、例えば「新しいクラスで誰と誰が既に知り合いか」といったように、

考えられる物事たちの集合 (先例では、クラスのメンバーの集合)

それらのメンバたちが互いにどう関係しているか (先例では、知り合い関係)

https://scrapbox.io/files/60f04c3466512a0022a89576.webp

1.1グラフの定義

頂点 (vertex) の有限集合 V

辺 (edge) の有限集合 E

頂点集合 V=V={青木君, 鈴木君, 高橋君, 小林君, 佐藤君}

辺集合: E=E={(青木君, 鈴木君), (鈴木君, 高橋君), (鈴木君, 小林君), (小林君, 佐藤君), (青木君, 佐藤君)}}

覚え方

https://scrapbox.io/files/60f0519545bfaf002317105a.jpeg

1-2. 有向グラフと無向グラフ

https://scrapbox.io/files/60f04d852cb946001c368960.webp

計算機上でのグラフの表し方

グラフ探索アルゴリズムを実装する前に、計算機上でグラフを表現するデータ構造について簡単に述べます。大きく分けて

隣接リスト表現 (adjacency-list representation)

隣接行列表現 (adjacency-matrix representation)

可変長配列 vector

二次元配列はvector vector

辺に重みがない場合

code:swift

//辺に重みがない場合

//Swiftは連結リストを作成する際に大きさを指定しておかないと範囲外エラーが起きる．

var graph: Int = Int.init(repeating: [], count: 1_000)

//graphの0番目とつながりのあるVを列挙する

graph0.append(32)

graph32.append(0)

graph0.append(13)

graph13.append(0)

print(graph0)

//32, 13

辺に重みがある場合

例えば鉄道路線図上で二駅間の最短経路を求める問題では、駅間の移動時間についての情報が必要になる．そのような場合に使える．

code: swift

//辺を定義

struct Edge {

//行き先

let to: Int

//重み

let weight: Int

}

var graph: Edge = Edge.init(repeating: [], count: 1000)

//0地点から13地点までの重み100

graph0.append(Edge(to: 13, weight: 100))

//0地点から32地点までの重み1000

graph0.append(Edge(to: 32, weight: 1000))

ここから本題

https://scrapbox.io/files/60f0aecec1aa86001c30bb4e.webp

深さ優先探索 (DFS) と幅優先探索 (BFS)

スタートを0としたとき次にどのページを読むか

DFS: たった今読了した頂点 1 からそのまま辿れる頂点 (3 か 8) へと突き進む

BFS:一旦、保留にしていた頂点 2, 4 に対応するページを読んでおく