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

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

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

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

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

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

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

グラフの頂点を表すクラス （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で使う）

テストデータのうち、 グラフの頂点とその集合 深さ優先探索のプログラム 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(); テストデータのうち、 グラフの頂点とその集合 深さ優先探索のプログラム

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

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

有向グラフの深さ優先探索 （２４０ページ） 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(); }}}} 有向グラフの深さ優先探索 （２４０ページ）

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

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

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

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();

頂点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 ->

ＢｒｅａｄｔｈＦｉｒｓｔＳｅａｒｃｈのＦＩＦＯ（リスト）を ＬＩＦＯ（スタック）に変えたもの。 この変更により、幅優先探索だったプログラムが 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(); ＢｒｅａｄｔｈＦｉｒｓｔＳｅａｒｃｈのＦＩＦＯ（リスト）を ＬＩＦＯ（スタック）に変えたもの。 この変更により、幅優先探索だったプログラムが 深さ優先探索プログラムになる。 （２４７ページ）