ALG2012-A.ppt

(1)

アルゴリズムとデータ構造

2012年7月9日

酒居敬一

(

[email protected]

)

(2)

グラフの定義（２２５ページ）

•  グラフは頂点の集合と辺の集合からなる。

•  グラフには有向グラフと無向グラフがある。

•  グラフに対する、教科書４章の仮定。

–  (ｖ, ｖ)の形の辺（ＮＤＡのε遷移みたいなの）はない。

–  頂点ｕからｖへ結ぶ辺は高々１つ。

•  辺の属性として数値を持つ場合、重みという。

•  いくつかの辺をつないでできる経路は道。

–  有向グラフでは辺はすべて同じ向きをたどる。

•  頂点からその頂点自身への道は閉路。

•  木はグラフの一種。

(3)

グラフの定義（つづき）

•  木が複数集まったグラフは森という。

–  木と木がつながっていなくてもいい。

•  頂点につながる辺の数を次数という。

–  有向グラフでは、入次数・出次数と区別する。

•  正則グラフでは全頂点の次数が同じ。

–  このときの次数をグラフの次数とする場合がある。

•  ハイパーキューブなど

•  グラフ全体を組織的に調べることを探索という。

–  ただし、単に頂点を訪問するだけ、かもしれない。

(4)

グラフアルゴリズムの計算量

•  頂点数をｎとしたときの最大の辺の数ｍは、

無向グラフでは

有向グラフでは

•  辺の数が最大のものを完全グラフという。

•  辺の数が０でもグラフである。

•  密なグラフか、疎なグラフか。

–  次数がある程度以下なら疎と考える。

•  「ある程度」とは、問題に依存する。

•  ＣＣＣ（ＣｕｄｅＣｏｎｎｅｃｔｅｄＣｙｃｌｅ）なら次数は３。疎？

•  人工的なネットワークか、自然なネットワークか。

2 /

)

1 (

2

=

×

−

=

C

n

m

_n

)

1 (

−

×

=

n

m

(5)

グラフの表現法（２３０ページ）

•  隣接行列

–  頂点から頂点への接続の有無や辺の重みを持つ

–  密なグラフにはいい

•  配列やＬｉｓｔやＳｅｔやＭａｐによる表現

–  正則グラフなら配列

–  二分探索木のような順序木のグラフならＬｉｓｔ

–  無向グラフならＬｉｓｔでもＳｅｔでもＭａｐでもいい

•  ＭａｐならＫｅｙを接続先の頂点、Ｖａｌｕｅを重みにするなど

•  計算で求める

–  配列上のヒープソートの、部分順序つき二分木

–  スパコン内部ネットワークなど

(6)

0000

0110

1101

1110

1111

1011

0111

0101

0011

0100

0010

0001

1100

1010

1001

1000

(7)

Ａ

Ｂ

Ｃ

Ｅ

Ｄ

Ｆ

Ｇ

Ａ

Ｂ

Ｃ

Ｅ

Ｄ

Ｆ

Ｇ

Ａ

Ｂ

Ｃ

Ｅ

Ｄ

Ｆ

Ｇ

図４

.３.２ａ

図４

.３.２ｂ

図４

.３.３

１

２

３

４

５

６

７

１

２

３

４

５

６

７ 深さ優先探索

（２３４ページ）

• 木の辺（実線で表示）

• 逆辺（点線で表示）

• 連結グラフなら木が得られ、

そうでなければ森が得られる

(8)

8

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;

}

グラフの頂点を表すクラス

（

4.3と4.4で使う）

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); //有向辺を追加 }

(9)

9 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)

10

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

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

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.3

Aから探索します。

A -> C -> F -> D -> B -> E -> G

図4.3.2

Aから探索します。

A -> C -> E -> G -> F -> D -> B

_図4.3.4

Aから探索します。

A -> C -> B -> D -> E

Fから探索します。

F -> 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(); }}}} 12

有向グラフの深さ優先探索

（２４０ページ）

(13)

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); } 13

図4.3.4

Aから探索します。

A -> C -> B 上昇辺(B, A) -> D 交差辺(D, C) -> E 下降辺(A, E)

Fから探索します。

(14)

トポロジカルソート

（２４２ページ）

図

4.3.6 ＤＡＧ

（ＤｉｒｅｃｔｅｄＡｃｙｃｌｉｃＧｒａｐｈ）

• Ｔｏｐｏｌｏｇｙは「位相」のこと。トポロジカルソートのときはこちら。

• Ｐｈａｓｅも「位相」と訳せます。ベクタの位相はこちら。

⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 2 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 5 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 4 3 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 5 0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 2 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 0 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 0 5 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 4 3 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 5 0

たとえば、ベクターがあったとします。

大きさ０

大きさ２

大きさ

5 大きさを比較することは

できますが、大きさが同じ

だからといって同じベクター

であるとは限りませんよね？

全要素間で順序がつけられる → 全順序関係

一部の要素間に順序がつけられる → 半順序関係

同じだけど同じじゃない、というのは順序がつけられて

ません。そういうデータは、ＤＡＧで保持することができる。

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

(17)

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); } 17

図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(); } } } ₁₈

ALG2012-A.ppt

アルゴリズムとデータ構造

2012年7月9日

酒居敬一

(

[email protected]

)

グラフの定義（２２５ページ）

• グラフは頂点の集合と辺の集合からなる。

• グラフには有向グラフと無向グラフがある。

• グラフに対する、教科書４章の仮定。

– (ｖ, ｖ)の形の辺（ＮＤＡのε遷移みたいなの）はない。

– 頂点ｕからｖへ結ぶ辺は高々１つ。

• 辺の属性として数値を持つ場合、重みという。

• いくつかの辺をつないでできる経路は道。

– 有向グラフでは辺はすべて同じ向きをたどる。

• 頂点からその頂点自身への道は閉路。

• 木はグラフの一種。

グラフの定義（つづき）

• 木が複数集まったグラフは森という。

– 木と木がつながっていなくてもいい。

• 頂点につながる辺の数を次数という。

– 有向グラフでは、入次数・出次数と区別する。

• 正則グラフでは全頂点の次数が同じ。

– このときの次数をグラフの次数とする場合がある。

• ハイパーキューブなど

• グラフ全体を組織的に調べることを探索という。

– ただし、単に頂点を訪問するだけ、かもしれない。

グラフアルゴリズムの計算量

• 頂点数をｎとしたときの最大の辺の数ｍは、

無向グラフでは

有向グラフでは

• 辺の数が最大のものを完全グラフという。

• 辺の数が０でもグラフである。

• 密なグラフか、疎なグラフか。

– 次数がある程度以下なら疎と考える。

• 「ある程度」とは、問題に依存する。

• ＣＣＣ（Ｃｕｄｅ Ｃｏｎｎｅｃｔｅｄ Ｃｙｃｌｅ）なら次数は３。疎？

• 人工的なネットワークか、自然なネットワークか。

2

/

)

1

(

=

×

−

=

C

n

n

m

)

1

(

−

×

=

n

n

m

グラフの表現法（２３０ページ）

• 隣接行列

– 頂点から頂点への接続の有無や辺の重みを持つ

– 密なグラフにはいい

• 配列やＬｉｓｔやＳｅｔやＭａｐによる表現

– 正則グラフなら配列

– 二分探索木のような順序木のグラフならＬｉｓｔ

– 無向グラフならＬｉｓｔでもＳｅｔでもＭａｐでもいい

• ＭａｐならＫｅｙを接続先の頂点、Ｖａｌｕｅを重みにするなど

• 計算で求める

– 配列上のヒープソートの、部分順序つき二分木

– スパコン内部ネットワークなど

0000

0110

1101

1110

1111

1011

0111

•  グラフは頂点の集合と辺の集合からなる。

•  グラフには有向グラフと無向グラフがある。

•  グラフに対する、教科書４章の仮定。

–  (ｖ, ｖ)の形の辺（ＮＤＡのε遷移みたいなの）はない。

–  頂点ｕからｖへ結ぶ辺は高々１つ。

•  辺の属性として数値を持つ場合、重みという。

•  いくつかの辺をつないでできる経路は道。

–  有向グラフでは辺はすべて同じ向きをたどる。

•  頂点からその頂点自身への道は閉路。

•  木はグラフの一種。

•  木が複数集まったグラフは森という。

–  木と木がつながっていなくてもいい。

•  頂点につながる辺の数を次数という。

–  有向グラフでは、入次数・出次数と区別する。

•  正則グラフでは全頂点の次数が同じ。

–  このときの次数をグラフの次数とする場合がある。

•  ハイパーキューブなど

•  グラフ全体を組織的に調べることを探索という。

–  ただし、単に頂点を訪問するだけ、かもしれない。

•  頂点数をｎとしたときの最大の辺の数ｍは、

•  辺の数が最大のものを完全グラフという。

•  辺の数が０でもグラフである。

•  密なグラフか、疎なグラフか。

–  次数がある程度以下なら疎と考える。

•  「ある程度」とは、問題に依存する。

•  ＣＣＣ（ＣｕｄｅＣｏｎｎｅｃｔｅｄＣｙｃｌｅ）なら次数は３。疎？

•  人工的なネットワークか、自然なネットワークか。

•  隣接行列

–  頂点から頂点への接続の有無や辺の重みを持つ

–  密なグラフにはいい

•  配列やＬｉｓｔやＳｅｔやＭａｐによる表現

–  正則グラフなら配列

–  二分探索木のような順序木のグラフならＬｉｓｔ

–  無向グラフならＬｉｓｔでもＳｅｔでもＭａｐでもいい

•  ＭａｐならＫｅｙを接続先の頂点、Ｖａｌｕｅを重みにするなど

•  計算で求める

–  配列上のヒープソートの、部分順序つき二分木

–  スパコン内部ネットワークなど

.３.２ａ

.３.２ｂ

• 木の辺（実線で表示）

• 逆辺（点線で表示）

• 連結グラフなら木が得られ、