アルゴリズムとデータ構造
アルゴリズムとデータ構造
アルゴリズムとデータ構造
アルゴリズムとデータ構造
2011
2011年
年
77月
月
44日
日
酒居敬一
酒居敬一
((
sakai.keiichi@kochi
[email protected]
tech.ac.jp
))
http://www info kochi
http://www info kochi--tech ac jp/k1sakai/Lecture/ALG/2011/index html
tech ac jp/k1sakai/Lecture/ALG/2011/index html
http://www.info.kochi
グラフの定義
（２２５ページ）
• グラフは頂点の集合と辺の集合からなる。
• グラフには有向グラフと無向グラフがある。
• グラフに対する 教科書４章の仮定
グラフに対する、教科書４章の仮定。
– (ｖ, ｖ)の形の辺（ＮＤＡのε遷移みたいなの）はない。
頂点 から
結ぶ辺は高
– 頂点ｕからｖへ結ぶ辺は高々１つ。
• 辺の属性として数値を持つ場合、重みという。
辺
属性 し 数値を持 場合、重み
う。
• いくつかの辺をつないでできる経路は道。
有向グラフでは辺はすべて同じ向きをたどる
– 有向グラフでは辺はすべて同じ向きをたどる。
• 頂点からその頂点自身への道は閉路。
• 木はグラフの一種。
グラフの定義
（つづき）
• 木が複数集まったグラフは森という。
木と木が なが ていなくてもいい
– 木と木がつながっていなくてもいい。
• 頂点につながる辺の数を次数という。
– 有向グラフでは、入次数・出次数と区別する。
• 正則グラフでは全頂点の次数が同じ
• 正則グラフでは全頂点の次数が同じ。
– このときの次数をグラフの次数とする場合がある。
• ハイパーキューブなど
• グラフ全体を組織的に調べることを探索という。
グラフ全体を組織的に調
る とを探索という。
– ただし、単に頂点を訪問するだけ、かもしれない。
グラフアルゴリズムの計算量
グラフアルゴリズムの計算量
• 頂点数をｎとしたときの最大の辺の数ｍは、
グ
無向グラフでは
有向グラフでは
2
/
)
1
(
2=
×
−
=
C
n
n
m
n)
1
(
−
×
=
n
n
m
有
ラ
• 辺の数が最大のものを完全グラフという。
辺の数が０でもグラ である
)
(
• 辺の数が０でもグラフである。
• 密なグラフか、疎なグラフか。
密なグラフか、疎なグラフか。
– 次数がある程度以下なら疎と考える。
• 「ある程度」とは 問題に依存する
• 「ある程度」とは、問題に依存する。
• ＣＣＣ（Ｃｕｄｅ Ｃｏｎｎｅｃｔｅｄ Ｃｙｃｌｅ）なら次数は３。疎？
人工的なネ トワ クか 自然なネ トワ クか
• 人工的なネットワークか、自然なネットワークか。
グラフの表現法
（２３０ページ）
• 隣接行列
頂点から頂点
の接続の有無や辺の重みを持
– 頂点から頂点への接続の有無や辺の重みを持つ
– 密なグラフにはいい
• 配列やＬｉｓｔやＳｅｔやＭａｐによる表現
– 正則グラフなら配列
– 正則グラフなら配列
– 二分探索木のような順序木のグラフならＬｉｓｔ
グ
– 無向グラフならＬｉｓｔでもＳｅｔでもＭａｐでもいい
• ＭａｐならＫｅｙを接続先の頂点、Ｖａｌｕｅを重みにするなど
• 計算で求める
– 配列上のヒープソートの 部分順序つき二分木
– 配列上のヒ プソ トの、部分順序つき二分木
– スパコン内部ネットワークなど
1101
0101
0100
0101
1100
1101
0100
1100
0110
0111
1110
1111
0000
0001
1000
1001
1011
0011
0010
1010
Ａ
Ｂ
深さ優先探索
（２３４ペ ジ）
Ｂ
Ｃ
Ａ
１
（２３４ページ）
Ｄ
Ａ
Ｂ
２
７
Ｅ
Ｆ
Ａ
Ｃ
Ｄ
２
６
１
５
Ｇ
Ｂ
Ｃ
Ｅ
Ｆ
図４
.３.２ ａ
３
５
２
４
Ｃ
Ｄ
Ｅ
Ｆ
Ｇ
図４ ３ ２ ｂ
４
４
Ｅ
Ｆ
Ｇ
図４
.３.２ ｂ
３
６
•木の辺（実線で表示）
•逆辺（点線で表示）
Ｇ
図４
.３.３
７
•逆辺（点線で表示）
•連結グラフなら木が得られ、
そうでなければ森が得られる
public class Node<E> {
private E value; // 頂点の値
private Collection<Node<E>> edges; // 有向辺 i t b l isit d
public boolean isVisited() { return visited;
}
bli id s tVisit d(b l ) { private boolean visited;
private int sequence;
private boolean searching;
public Node(E value, Collection<Node<E>> edges) {
public void setVisited(boolean v) { this.visited = v;
}
public int getSequence() {
p ( , g ) { this.value = value; this.edges = edges; reset(); } p g q () { return sequence; }
public void setSequence(int s) { this s qu nc s;
}
public void reset(){ this.visited = false; this.sequence = 0;
this.sequence = s; }
public boolean isSearching() { return searching; q this.edges.clear(); this.searching = false; } public E getValue() { // 頂点の値を得る g }
public void setSearching(boolean s) { this.searching = s;
} public E getValue() { // 頂点の値を得る。
return value; }
public Collection<Node<E>> getEdges(){
}
public void connect(Node<E> to){
this.edges.add(to); //無向辺を追加 if( !to.getEdges().contains(this) ){ p g g (){ return this.edges; } ( g g () ( ) ){ to.getEdges().add(this); } }
public void connectTo(Node<E> to){
8
グラフの頂点を表すクラス
（
4.3と4.4で使う）
public void connectTo(Node<E> to){ this.edges.add(to); //有向辺を追加 }
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>>()); pr vate stat c Node haracter nodeD new Node haracter ( D , new L nkedL st Node haracter ()); 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>>();
p _ w L L ();
static {
test_data.add(nodeA); test_data.add(nodeB); test data.add(nodeC);
public class DepthFirstSearch {
private static <E> void visit(Node<E> node){ node.setVisited(true); _ ( ); test_data.add(nodeD); test_data.add(nodeE); test_data.add(nodeF); test_data.add(nodeG); node.setV s ted(true); System.out.print(node.getValue());
for(Node<E> neighbor: node.getEdges()){
if(neighbor.isVisited()) continue; // 訪問済み S t t i t(" ") _ ( ); } System.out.print(" -> "); visit(neighbor); } }}
public static <E> void search(Collection<Node<E>> graph){ for(Node<E> node: graph){
if(node.isVisited()) continue; // 訪問済み S st t i tl ( d tV l () "から探索します ");
テストデータのうち、
グラフの頂点とその集合
System.out.println(node.getValue() + "から探索します。"); visit(node); System.out.println(); } 9 } } }深さ優先探索のプログラム
public static void main(String[] args) { System.out.println("図4.3.2");
for(Node<Character> node: test_data){
d s t() bli i id i ( i [] ) { node.reset();
}
nodeA.connect(nodeC); nodeA.connect(nodeD);
public static void main(String[] args) { System.out.println("図4.3.3");
for(Node<Character> node: test_data){
node reset(); public static void main(String[] args) { ( ); nodeA.connect(nodeB); nodeC.connect(nodeE); nodeC.connect(nodeF); n d D c nn ct(n d B); node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); d A t( d B)
public static void main(String[] args) { System.out.println("図4.3.4");
for(Node<Character> node: test_data){ node.reset(); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); nodeA.connect(nodeB); nodeC.connect(nodeF); nodeC.connect(nodeE); nodeD.connect(nodeB); } nodeA.connectTo(nodeC); nodeA.connectTo(nodeD); nodeA connectTo(nodeE); ( ) search(test_data); } nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); h(t t d t ) nodeA.connectTo(nodeE); nodeC.connectTo(nodeB); nodeB.connectTo(nodeA); nodeD.connectTo(nodeC); search(test_data); } nodeD.connectTo(nodeE);nodeF.connectTo(nodeA); nodeF.connectTo(nodeG); search(test data);
図4.3.2
search(test_data); }図4 3 3
Aから探索します。
A -> C -> E -> G -> F -> D -> B
図4.3.4
Aから探索します。
10図4.3.3
Aから探索します。
A -> C -> F -> D -> B -> E -> G
A -> C -> B -> D -> E
Fから探索します。
F -> G
Ｆ
Ａ
•上昇辺
子孫から祖先
向かう辺
Ｂ
Ｇ
子孫から祖先へ向かう辺
無向グラフでは逆辺
•下降辺
祖先から子孫へ向かう辺
Ｃ
Ｅ
Ｄ
Ｇ
祖先から子孫へ向かう辺
無向グラフでは逆辺
•交差辺
上昇辺でも下降辺でもない辺
図４
.３.４ ａ
１
連結グラフとは グラフ全体が
交差辺
上昇辺でも下降辺でもない辺
３
１
６
Ｆ
Ａ
連結グラフとは、グラフ全体が
つながっていること。無向グラフ
では、深さ優先探索で全ての
頂点をたどる事ができれば連結
上昇辺
５
７
Ｂ
Ｅ
Ｇ
頂点をたどる事ができれば連結
グラフである。
しかし 有向グラフでは必ずしも
下降辺
２
４
Ｃ
Ｅ
Ｄ
しかし、有向グラフでは必ずしも
そうとはならない。
図４
.３.４ ｂ
交差辺
public class DirectedDepthFirstSearch<E> { private int sequence;
private void visit(Node<E> node){
d s tVisit d(t )
有向グラフの深さ優先探索
node.setVisited(true); node.setSequence(++this.sequence); node.setSearching(true); System.out.print(node.getValue());有向グラフの深さ優先探索
（２４０ページ）
y p ( g ());for(Node<E> neighbor: node.getEdges()){ if(neighbor.getSequence() == 0){
System.out.print(" -> "); isit(n i hb ); // 木の辺 visit(neighbor); // 木の辺
} else if (neighbor.getSequence() > node.getSequence()) {
System.out.print(" 下降辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); } else if (neighbor.isSearching()){
} ( g g()){
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){
p ( g p ){
this.sequence = 0;
for(Node<E> node: graph){
if(node.getSequence() == 0){
System out println(node getValue() + "から探索します "); System.out.println(node.getValue() + から探索します。 ); visit(node);
System.out.println(); }}}}
public static void main(String[] args) { S st m ut println("図4 3 4");
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); 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から探索します。
A -> C -> B 上昇辺(B, A) -> D 交差辺(D, C) -> E 下降辺(A, E)
Fから探索します。
F 交差辺(F
A)
> G
13F 交差辺(F, A) -> G
トポロジカルソート
（２４２ページ）
（２４２ページ）
•Ｔｏｐｏｌｏｇｙ は「位相」のこと。トポロジカルソートのときはこちら。
•Ｐｈａｓｅ も「位相」と訳せます。ベクタの位相はこちら。
⎤ ⎡5たとえば、ベクターがあったとします。
⎥ ⎤ ⎢ ⎡2 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 5 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 0大きさ０
大きさを比較することは
⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 0 ⎥ ⎦ ⎢ ⎣0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 4 3 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 2 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 0 ⎤ ⎡5 ⎡3⎤ ⎡0⎤大きさ２
できますが、大きさが同じ
だからといって同じベクター
であるとは限りませんよね？
⎦ ⎣0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 0 ⎦ ⎣4 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 5 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 4 3 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 5 0大きさ
5
全要素間で順序がつけられる → 全順序関係
⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 5 0全要素間で順序
けられる
全順序関係
一部の要素間に順序がつけられる → 半順序関係
同じだけど同じじゃない、というのは順序がつけられて
図
4.3.6 ＤＡＧ
（Ｄｉｒｅｃｔｅｄ Ａｃｙｃｌｉｃ Ｇｒａｐｈ）
ません。そういうデータは、ＤＡＧで保持することができる。
Ａ
幅優先探索
（２４４ペ ジ）
Ｂ
（２４４ページ）
Ｃ
Ｄ
１
Ｅ
Ｆ
４
Ａ
Ｂ
Ｆ
Ｇ
図４
.３.２ ａ
２
３
Ｃ
Ｄ
図
５
６
Ｅ
７
Ｅ
Ｆ
Ｇ
図４
.３.７
Ｇ
public class BreadthFirstSearch {
public static <E> void search(Collection<Node<E>> graph){
Queue<Node<E>> queue = new LinkedList<Node<E>>(); // FIFO f (N d E d h){
for(Node<E> node: graph){ if(node.isVisited()){ continue; // 訪問済み }} queue.add(node); // enqueue node.setVisited(true); while( !queue.isEmpty() ){ N d <E> n xt qu u m (); // d qu u Node<E> next = queue.remove(); // dequeue System.out.print("頂点" + next.getValue());
for(Node<E> neighbor: next.getEdges()){ if( neighbor.isVisited() ){( g () ){ continue; } queue.add(neighbor); // enqueue neighbor setVisited(true); neighbor.setVisited(true);
System.out.print(" 辺(" + next.getValue() + ", " + neighbor.getValue() + ")"); } System.out.print(" -> ");y p ( ) } System.out.println(); } }} } 16
public static void main(String[] args) { System.out.println("図4.3.7");
for(Node<Character> node: test_data){ d s t() node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD);( ); nodeA.connect(nodeB); nodeC.connect(nodeE); nodeC.connect(nodeF); n d D c nn ct(n d B); 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) ->
頂点C 辺(C, E) 辺(C, F) >
頂点D ->
頂点B ->
頂点E 辺(E, G) ->
17頂点E 辺(E, G) >
頂点F ->
頂点G ->
public class DepthFirstSearchStack {
public static <E> void search(Collection<Node<E>> graph){
St k N d E t k St k N d E () // LIFO Stack<Node<E>> stack = new Stack<Node<E>>(); // LIFO for(Node<E> node: graph){
if(node.isVisited()){ continue; // 訪問済み continue; // 訪問済み } stack.push(node); // push node.setVisited(true); hil ( ! t k t () ){ while( !stack.empty() ){
Node<E> next = stack.pop(); // pop System.out.print("頂点" + next.getValue());
for(Node<E> neighbor: next.getEdges()){ for(Node E ne ghbor next.getEdges()){
if( neighbor.isVisited() ){ continue; } t k dd( i hb ) // h stack.add(neighbor); // push neighbor.setVisited(true); } System.out.print(" -> ");y m p ( );
