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

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

2012 年 7 月 12 日

酒居敬一 ([email protected])

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

1

各種の連結性の判定

（２４９ページ）

•   連結の強さを表現する概念

•   無向グラフ

–   二重連結

–   二重連結成分

•   有向グラフ

–   強連結

–   強連結成分

2

Ｈ Ｉ

図４ . ４ . １ 二重連結グラフ

図４ . ４ . ２ 関節点と二重連結成分

二重連結

（２５０ページ）

グラフから１つの頂点と その頂点を端点とする

すべての辺を除いて得られる グラフを考えたとき、どの頂点を 除いた場合でもグラフが連結 グラフであるとき、元のグラフは 二重連結であるという。

Ａ

Ｃ Ｂ Ｅ

Ｄ

Ｆ

Ｇ

•  二重連結成分とは、二重  連結な部分グラフのこと。

•  取り除くと非連結になる

 頂点を関節点という。 ³

関節点検出のアルゴリズム

（２５１ページ）

•   前提条件

–   関節点が検出されなければ、二重連結。

–   深さ優先探索の結果の木を仮定して、

子孫・祖先・部分木という言葉を使う。

•   場合分け

–   頂点が木の根の場合

•   子が２個以上ならその頂点は関節点である。

–   頂点が木の根ではない場合（次のページ）

•   着目する３頂点の位置で２つに場合分けする。

–  いずれもＡＢ間・ＢＣ間・ＣＡ間の道について考える。 ⁴

Ａ Ｂ

Ｃ

ＢはＡの祖先、ＣはＡの子孫、

という位置関係の場合。

（図 ４ . ４ . ３ ａ）

•  もしＡが関節点ならば、

以下の２つは同じことを言っている 1.   ＢＣ間の道が必ずＡを通ること

2.   Ｃを含む部分木の中にＡの祖先への 逆辺がないこと

•  図のように逆辺 （点線で表示）があれば、

 Ａを経由せずにＢＣ間を移動できるので、

 この場合はＡは関節点ではない。

5

Ａ

Ｂ

Ｃ

ＢはＡの子孫、ＣもＡの子孫、

という位置関係の場合。

（図 ４ . ４ . ３ ｂ）

•  図のように、ＢとＣの双方が、Ａの祖先と  Ａを経由せずに連絡できれば、Ａは

関節点ではない。この場合、Ａを経由 せずにＢとＣが連絡できる。

•  ＢとＣがＡを通らないと連絡できない  のは、どちらかの部分木にＡより上の  祖先を指す逆辺がないからであり、

 Ａが関節点になっている。

6

public class Biconnected<E> { private int sequence;

private int visit(Node<E> node){

node.setSequence(++this.sequence);

int min = this.sequence;

for(Node<E> neighbor: node.getEdges()){

if(neighbor.getSequence() == 0){

int m = visit(neighbor);

min = Math.min(min, m);

boolean artic;

if (node.getSequence() == 1) {

artic = (neighbor.getSequence() != 2);

} else {

artic = (m >= node.getSequence());

}

if(artic) System.out.println("

" + node.getValue() + "

");

} else if (neighbor.getSequence() < min){

min = neighbor.getSequence();

} }

return min;

}

public void search(Node<E> start){

this.sequence = 0;

visit(start);

}

} ⁷

根の子が２個以上（順序数が２より大きい）

ときは、根が関節点。

隣接する未訪問の頂点に関しては、

深さ優先探索なので探索する。

その結果、訪問順が付けられる。

自分（ｎｏｄｅ）の子から、祖先への逆辺 がなければ、自分は関節点。

隣接する訪問済みの頂点に関しては、

より祖先へ向かう辺（逆辺含む）の先の 頂点の順序数を保持する。

深く探索していく過程で、より祖先寄りの祖先への逆辺を

調べながら進んでいる。

public static void main(String[] args) { System.out.println("

4.4.2");

for(Node<Character> node: test_data2){

node.reset();

}

nodeA.connect(nodeC);

nodeA.connect(nodeD);

nodeB.connect(nodeC);

nodeB.connect(nodeD);

nodeC.connect(nodeE);

nodeD.connect(nodeF);

nodeD.connect(nodeG);

nodeF.connect(nodeG);

nodeE.connect(nodeH);

nodeE.connect(nodeI);

new Biconnected<Character>().search(nodeA);

}

8

図4.4.2

頂点Dは関節点 頂点Eは関節点 頂点Eは関節点 頂点Cは関節点

Ｈ Ｉ

Ａ

Ｃ Ｂ Ｅ

Ｄ

Ｆ

Ｇ

図４ . ４ . ５ 強連結グラフ

図４ . ４ . ６ 強連結成分への分割

強連結

（２５５ページ）

有向グラフの各頂点から任意の 頂点へ至る道が存在するとき、

この有向グラフを強連結であるという。

部分グラフのうち、強連結であって、

しかもそれ以上頂点を追加すると

強連結でなくなるものを強連結成分という。

9

強連結成分への分割アルゴリズム

（２５６ページ）

ü  有向グラフの深さ優先探索の応用である。

ü  下降辺は強連結性に貢献しない。

ü  下降辺の両端の頂点について、祖先から子孫へ 木の辺から成る道がすでに存在する。

ü  上昇辺の両端の頂点は同じ強連結成分に属す。

ü  木の辺と上昇辺で閉路を作る。

ü  木の辺で下降し、上昇辺で上昇して元に戻れる。

ü  交差辺は、単純ではない。

ü  強連結成分に属す・属さないの２種類がある。

10

図４ . ４ . ７ 深さ優先探索の木と強連結成分の関係

（木の辺だけを見たときは木）

•  深さ優先探索の木の上で強連結成分を表す。

•  実際は下降辺・上昇辺・交差辺も存在してて、

 それらとともに強連結成分を作っている。

•  各強連結成分に最初に訪問した頂点   ＝その部分木の根。

•  部分木の根からその子孫に到達可能。

•  部分木が強連結成分なら、

 木の辺を０回以上通った後で

 上昇辺か交差辺を通って根に戻れる。

•  深さ優先探索の木の葉から、上昇辺  や交差辺を通ってその葉の祖先に  たどり着くことができ、そういう祖先の  うちで最も根に近いものを求める。

•  教科書の lowlink 変数

強連結成分を見つけたら、

この辺を木からはずす。 ¹¹

public class StrongComponent<E> { private int sequence;

private Stack<Node<E>> stack = new Stack<Node<E>>();

private int visit(Node<E> node){

node.setSequence(++this.sequence);

int min = this.sequence;

stack.push(node);

for(Node<E> neighbor: node.getEdges()){

int m;

if(neighbor.getSequence() == 0) m = visit(neighbor);

else m = neighbor.getSequence();

min = Math.min(min, m);

}

if(min == node.getSequence()){

Node<E> component;

do {

component = stack.pop();

System.out.print(component.getValue() + " ");

component.setSequence(Integer.MAX_VALUE);

} while (component != node);

System.out.println();

}

return min;

}

public void search(Collection<Node<E>> graph){

this.sequence = 0; this.stack.clear();

for(Node<E> node: graph) if(node.getSequence() == 0) visit(node);

}}

12

訪問順ｓｅｑ

この根からつながる

強連結成分を取り出す。

隣の頂点が訪問済みの場合は、

そこからたどれる最も根に

近い頂点の訪問順を更新する。

訪問済みなので木の辺じゃない。

未訪問の場合は探索を進める。

深さ優先探索し終わった後、

調べてみたら、

強連結成分の根だった

（ｓｅｑ＝ｌｏｗｌｉｎｋ）

教科書のｌｏｗｌｉｎｋ

交差辺経由で探索されないようにする。

public static void main(String[] args) { System.out.println("

4.4.9");

for(Node<Character> node: test_data2){

node.reset();

}

nodeA.connectTo(nodeB);

nodeA.connectTo(nodeC);

nodeB.connectTo(nodeE);

nodeB.connectTo(nodeF);

nodeC.connectTo(nodeF);

nodeC.connectTo(nodeG);

nodeD.connectTo(nodeA);

nodeE.connectTo(nodeD);

nodeE.connectTo(nodeH);

nodeF.connectTo(nodeE);

nodeG.connectTo(nodeH);

nodeH.connectTo(nodeI);

nodeI.connectTo(nodeH);

new StrongComponent<Character>().search(test_data2);

}

13

図4.4.9 I H G

C F D E B A

Ｃ

Ｅ

Ａ

Ｄ

Ｂ

Ｆ

Ｉ

Ｇ

Ｈ

図 ４ . ４ . ９ プログラムの実行例

（実線は木の辺、点線はそれ以外の辺）

擬似コード

（Ｐｓｅｕｄｏｃｏｄｅ）

•   擬似プログラムともいう。

•   アルゴリズムを既存のプログラミング言語に 似せて書いたもの。

–   かつてはＰａｓｃａｌやＦｏｒｔｒａｎ、今はＪａｖａ？

•   要点だけ書くのでそのまま動く保障はない。

–   教科書のコードはかなり完成度が高い。

–   Java だと、どこでも動くコードを書きやすい。

14

期末試験


•   教室 : Ｃ１０１ （いつものＡ１０７は使えません）

•   日時 : ２０１２年７月３０日１６時３０分〜１８時００分

–   入室限度 : １６時５０分まで –   退出可能 : １７時００分より

•   持ち込み可

–   教科書・資料 ( 自筆・コピー問わず ) は持ち込み可 –   人間・パソコン・携帯電話・ PHS など持ち込み不可

•   学生証必携

–   持っていない場合は教務で発行してもらうこと

15