酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月4日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html.

Presentation on theme: "酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月4日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html."— Presentation transcript:

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2011年7月4日

2 グラフの定義（２２５ページ） グラフは頂点の集合と辺の集合からなる。 グラフには有向グラフと無向グラフがある。
グラフに対する、教科書４章の仮定。 (ｖ, ｖ)の形の辺（ＮＤＡのε遷移みたいなの）はない。 頂点ｕからｖへ結ぶ辺は高々１つ。 辺の属性として数値を持つ場合、重みという。 いくつかの辺をつないでできる経路は道。 有向グラフでは辺はすべて同じ向きをたどる。 頂点からその頂点自身への道は閉路。 木はグラフの一種。

3 グラフの定義（つづき） 木が複数集まったグラフは森という。 頂点につながる辺の数を次数という。 正則グラフでは全頂点の次数が同じ。
木と木がつながっていなくてもいい。 頂点につながる辺の数を次数という。 有向グラフでは、入次数・出次数と区別する。 正則グラフでは全頂点の次数が同じ。 このときの次数をグラフの次数とする場合がある。 ハイパーキューブなど グラフ全体を組織的に調べることを探索という。 ただし、単に頂点を訪問するだけ、かもしれない。

4 グラフアルゴリズムの計算量 頂点数をｎとしたときの最大の辺の数ｍは、 無向グラフでは 有向グラフでは 辺の数が最大のものを完全グラフという。
辺の数が０でもグラフである。 密なグラフか、疎なグラフか。 次数がある程度以下なら疎と考える。 「ある程度」とは、問題に依存する。 ＣＣＣ（Ｃｕｄｅ　Ｃｏｎｎｅｃｔｅｄ　Ｃｙｃｌｅ）なら次数は３。疎？ 人工的なネットワークか、自然なネットワークか。

5 グラフの表現法（２３０ページ） 隣接行列 配列やＬｉｓｔやＳｅｔやＭａｐによる表現 計算で求める 頂点から頂点への接続の有無や辺の重みを持つ
密なグラフにはいい 配列やＬｉｓｔやＳｅｔやＭａｐによる表現 正則グラフなら配列 二分探索木のような順序木のグラフならＬｉｓｔ 無向グラフならＬｉｓｔでもＳｅｔでもＭａｐでもいい ＭａｐならＫｅｙを接続先の頂点、Ｖａｌｕｅを重みにするなど 計算で求める 配列上のヒープソートの、部分順序つき二分木 スパコン内部ネットワークなど

6 4-dimentional binary hyper cube
0100 0101 1100 1101 0110 0111 1110 1111 0000 0001 1000 1001 0010 0011 1010 1011 4-dimentional binary hyper cube

7 深さ優先探索 Ａ Ｂ Ｃ Ａ Ｄ Ｂ Ｅ Ｃ Ｆ Ａ Ｄ Ｂ Ｇ Ｅ Ｃ Ｆ Ｄ Ｇ Ｅ Ｆ Ｇ （２３４ページ） １ ７ ２ １ ６ ５
図４.３.２ ａ ３ ２ ５ ４ ４ 図４.３.２ ｂ ６ ３ 木の辺（実線で表示） 逆辺（点線で表示） 連結グラフなら木が得られ、 　そうでなければ森が得られる ７ 図４.３.３

8 グラフの頂点を表すクラス （4.3と4.4で使う） public class Node<E> {
private E value; // 頂点の値 private Collection<Node<E>> edges; //　有向辺 private boolean visited; private int sequence; private boolean searching; public Node(E value, Collection<Node<E>> edges) { this.value = value; this.edges = edges; reset(); } public void reset(){ this.visited = false; this.sequence = 0; this.edges.clear(); this.searching = false; public E getValue() { // 頂点の値を得る。 return value; public Collection<Node<E>> getEdges(){ return this.edges; public boolean isVisited() { return visited; } public void setVisited(boolean v) { this.visited = v; public int getSequence() { return sequence; public void setSequence(int s) { this.sequence = s; public boolean isSearching() { return searching; public void setSearching(boolean s) { this.searching = s; public void connect(Node<E> to){ this.edges.add(to); //無向辺を追加 if( !to.getEdges().contains(this) ){ to.getEdges().add(this); public void connectTo(Node<E> to){ this.edges.add(to); //有向辺を追加 グラフの頂点を表すクラス （4.3と4.4で使う）

9 テストデータのうち、 グラフの頂点とその集合 深さ優先探索のプログラム public class DepthFirstSearch {
private static Node<Character> nodeA = new Node<Character>('A', new LinkedList<Node<Character>>()); private static Node<Character> nodeB = new Node<Character>('B', new LinkedList<Node<Character>>()); private static Node<Character> nodeC = new Node<Character>('C', new LinkedList<Node<Character>>()); private static Node<Character> nodeD = new Node<Character>('D', new LinkedList<Node<Character>>()); private static Node<Character> nodeE = new Node<Character>('E', new LinkedList<Node<Character>>()); private static Node<Character> nodeF = new Node<Character>('F', new LinkedList<Node<Character>>()); private static Node<Character> nodeG = new Node<Character>('G', new LinkedList<Node<Character>>()); private static Collection<Node<Character>> test_data = new LinkedList<Node<Character>>(); static { test_data.add(nodeA); test_data.add(nodeB); test_data.add(nodeC); test_data.add(nodeD); test_data.add(nodeE); test_data.add(nodeF); test_data.add(nodeG); } public class DepthFirstSearch { private static <E> void visit(Node<E> node){ node.setVisited(true); System.out.print(node.getValue()); for(Node<E> neighbor: node.getEdges()){ if(neighbor.isVisited()) continue; // 訪問済み System.out.print(" -> "); visit(neighbor); } public static <E> void search(Collection<Node<E>> graph){ for(Node<E> node: graph){ if(node.isVisited()) continue; // 訪問済み System.out.println(node.getValue() + "から探索します。"); visit(node); System.out.println(); テストデータのうち、 グラフの頂点とその集合 深さ優先探索のプログラム

10 A -> C -> E -> G -> F -> D -> B 図4.3.4 Aから探索します。
public static void main(String[] args) { System.out.println("図4.3.2"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); nodeA.connect(nodeB); nodeC.connect(nodeE); nodeC.connect(nodeF); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); search(test_data); public static void main(String[] args) { System.out.println("図4.3.3"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); nodeA.connect(nodeB); nodeC.connect(nodeF); nodeC.connect(nodeE); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); search(test_data); public static void main(String[] args) { System.out.println("図4.3.4"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connectTo(nodeC); nodeA.connectTo(nodeD); nodeA.connectTo(nodeE); nodeC.connectTo(nodeB); nodeB.connectTo(nodeA); nodeD.connectTo(nodeC); nodeD.connectTo(nodeE); nodeF.connectTo(nodeA); nodeF.connectTo(nodeG); search(test_data); 図4.3.2 Aから探索します。 A -> C -> E -> G -> F -> D -> B 図4.3.4 Aから探索します。 A -> C -> B -> D -> E Fから探索します。 F -> G 図4.3.3 Aから探索します。 A -> C -> F -> D -> B -> E -> G

11 Ｂ Ｃ Ｅ Ｄ Ｆ Ｇ Ａ Ｂ Ｃ Ｅ Ｄ Ｆ Ｇ Ａ 上昇辺 子孫から祖先へ向かう辺 無向グラフでは逆辺
上昇辺 　子孫から祖先へ向かう辺 　無向グラフでは逆辺 下降辺 　祖先から子孫へ向かう辺 　無向グラフでは逆辺 交差辺 　上昇辺でも下降辺でもない辺 図４.３.４ ａ 交差辺 １ 連結グラフとは、グラフ全体が つながっていること。無向グラフ では、深さ優先探索で全ての 頂点をたどる事ができれば連結 グラフである。 しかし、有向グラフでは必ずしも そうとはならない。 上昇辺 ６ Ｂ Ｃ Ｅ Ｄ Ｆ Ｇ Ａ ３ 下降辺 ７ ５ ２ ４ 図４.３.４ ｂ 交差辺

12 有向グラフの深さ優先探索 （２４０ページ） public class DirectedDepthFirstSearch<E> {
private int sequence; private void visit(Node<E> node){ node.setVisited(true); node.setSequence(++this.sequence); node.setSearching(true); System.out.print(node.getValue()); for(Node<E> neighbor: node.getEdges()){ if(neighbor.getSequence() == 0){ System.out.print(" -> "); visit(neighbor); // 木の辺 } else if (neighbor.getSequence() > node.getSequence()) { System.out.print(" 下降辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); } else if (neighbor.isSearching()){ System.out.print(" 上昇辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); } else { System.out.print(" 交差辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); }} node.setSearching(false); } public void search(Collection<Node<E>> graph){ this.sequence = 0; for(Node<E> node: graph){ if(node.getSequence() == 0){ System.out.println(node.getValue() + "から探索します。"); visit(node); System.out.println(); }}}} 有向グラフの深さ優先探索 （２４０ページ）

13 A -> C -> B 上昇辺(B, A) -> D 交差辺(D, C) -> E 下降辺(A, E)
public static void main(String[] args) { System.out.println("図4.3.4"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connectTo(nodeC); nodeA.connectTo(nodeD); nodeA.connectTo(nodeE); nodeC.connectTo(nodeB); nodeB.connectTo(nodeA); nodeD.connectTo(nodeC); nodeD.connectTo(nodeE); nodeF.connectTo(nodeA); nodeF.connectTo(nodeG); new DirectedDepthFirstSearch<Character>().search(test_data); 図4.3.4 Aから探索します。 A -> C -> B 上昇辺(B, A) -> D 交差辺(D, C) -> E 下降辺(A, E) Fから探索します。 F 交差辺(F, A) -> G

14 （Ｄｉｒｅｃｔｅｄ Ａｃｙｃｌｉｃ Ｇｒａｐｈ）
トポロジカルソート （２４２ページ） Ｔｏｐｏｌｏｇｙ　は「位相」のこと。トポロジカルソートのときはこちら。 Ｐｈａｓｅ　も「位相」と訳せます。ベクタの位相はこちら。 たとえば、ベクターがあったとします。 大きさ０ 大きさを比較することは できますが、大きさが同じ だからといって同じベクター であるとは限りませんよね？ 大きさ２ 大きさ5 　　　全要素間で順序がつけられる　→　全順序関係 一部の要素間に順序がつけられる　→　半順序関係 同じだけど同じじゃない、というのは順序がつけられて ません。そういうデータは、ＤＡＧで保持することができる。 簡単に説明しすぎ？ 図4.3.6 ＤＡＧ （Ｄｉｒｅｃｔｅｄ Ａｃｙｃｌｉｃ Ｇｒａｐｈ）

15 幅優先探索 Ａ Ｂ Ｃ Ｄ Ａ Ｂ Ｅ Ｆ Ｃ Ｇ Ｄ Ｅ Ｆ Ｇ （２４４ページ） １ ４ ２ 図４.３.２ ａ ３ ５ ６ ７
図４.３.７

16 public class BreadthFirstSearch {
public static <E> void search(Collection<Node<E>> graph){ Queue<Node<E>> queue = new LinkedList<Node<E>>(); // FIFO for(Node<E> node: graph){ if(node.isVisited()){ continue; // 訪問済み } queue.add(node); // enqueue node.setVisited(true); while( !queue.isEmpty() ){ Node<E> next = queue.remove(); // dequeue System.out.print("頂点" + next.getValue()); for(Node<E> neighbor: next.getEdges()){ if( neighbor.isVisited() ){ continue; queue.add(neighbor); // enqueue neighbor.setVisited(true); System.out.print(" 辺(" + next.getValue() + ", " + neighbor.getValue() + ")"); System.out.print(" -> "); System.out.println();

17 頂点A 辺(A, C) 辺(A, D) 辺(A, B) -> 頂点C 辺(C, E) 辺(C, F) -> 頂点D ->
public static void main(String[] args) { System.out.println("図4.3.7"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); nodeA.connect(nodeB); nodeC.connect(nodeE); nodeC.connect(nodeF); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); search(test_data); 図4.3.7 頂点A 辺(A, C) 辺(A, D) 辺(A, B) -> 頂点C 辺(C, E) 辺(C, F) -> 頂点D -> 頂点B -> 頂点E 辺(E, G) -> 頂点F -> 頂点G ->

18 ＢｒｅａｄｔｈＦｉｒｓｔＳｅａｒｃｈのＦＩＦＯ（リスト）を ＬＩＦＯ（スタック）に変えたもの。 この変更により、幅優先探索だったプログラムが
public class DepthFirstSearchStack { public static <E> void search(Collection<Node<E>> graph){ Stack<Node<E>> stack = new Stack<Node<E>>(); // LIFO for(Node<E> node: graph){ if(node.isVisited()){ continue; // 訪問済み } stack.push(node); // push node.setVisited(true); while( !stack.empty() ){ Node<E> next = stack.pop(); // pop System.out.print("頂点" + next.getValue()); for(Node<E> neighbor: next.getEdges()){ if( neighbor.isVisited() ){ continue; stack.add(neighbor); // push neighbor.setVisited(true); System.out.print(" -> "); System.out.println(); ＢｒｅａｄｔｈＦｉｒｓｔＳｅａｒｃｈのＦＩＦＯ（リスト）を ＬＩＦＯ（スタック）に変えたもの。 この変更により、幅優先探索だったプログラムが 深さ優先探索プログラムになる。 （２４７ページ）