Download presentation
Presentation is loading. Please wait.
1
酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2012年7月12日
2
各種の連結性の判定 （２４９ページ） 連結の強さを表現する概念 無向グラフ 二重連結 二重連結成分 有向グラフ 強連結 強連結成分
3
二重連結 Ｆ Ａ Ｄ Ｇ Ｃ Ｂ Ｅ Ｈ Ｉ （２５０ページ） 図４.４.１ 二重連結グラフ グラフから１つの頂点と その頂点を端点とする
図４.４.１ 二重連結グラフ Ｇ グラフから１つの頂点と その頂点を端点とする すべての辺を除いて得られる グラフを考えたとき、どの頂点を 除いた場合でもグラフが連結 グラフであるとき、元のグラフは 二重連結であるという。 Ｃ Ｂ Ｅ 図４.４.２ 関節点と二重連結成分 Ｈ Ｉ 二重連結成分とは、二重 連結な部分グラフのこと。 取り除くと非連結になる 頂点を関節点という。
4
関節点検出のアルゴリズム 前提条件 場合分け 関節点が検出されなければ、二重連結。
（２５１ページ） 前提条件 関節点が検出されなければ、二重連結。 深さ優先探索の結果の木を仮定して、 子孫・祖先・部分木という言葉を使う。 場合分け 頂点が木の根の場合 子が２個以上ならその頂点は関節点である。 頂点が木の根ではない場合（次のページ） 着目する３頂点の位置で２つに場合分けする。 いずれもＡＢ間・ＢＣ間・ＣＡ間の道について考える。
5
ＢはＡの祖先、ＣはＡの子孫、 という位置関係の場合。 もしＡが関節点ならば、 以下の２つは同じことを言っている ＢＣ間の道が必ずＡを通ること
（図 ４.４.３ ａ） Ａ Ｂ Ｃ もしＡが関節点ならば、 以下の２つは同じことを言っている ＢＣ間の道が必ずＡを通ること Ｃを含む部分木の中にＡの祖先への 逆辺がないこと 図のように逆辺 （点線で表示）があれば、 Ａを経由せずにＢＣ間を移動できるので、 この場合はＡは関節点ではない。
6
ＢはＡの子孫、ＣもＡの子孫、 という位置関係の場合。
（図 ４.４.３ ｂ） Ａ Ｂ Ｃ 図のように、ＢとＣの双方が、Ａの祖先と Ａを経由せずに連絡できれば、Ａは 関節点ではない。この場合、Ａを経由 せずにＢとＣが連絡できる。 ＢとＣがＡを通らないと連絡できない のは、どちらかの部分木にＡより上の 祖先を指す逆辺がないからであり、 Ａが関節点になっている。
7
根の子が２個以上（順序数が２より大きい） ときは、根が関節点。
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); 隣接する未訪問の頂点に関しては、 深さ優先探索なので探索する。 その結果、訪問順が付けられる。 根の子が２個以上（順序数が２より大きい） ときは、根が関節点。 自分（ｎｏｄｅ）の子から、祖先への逆辺 がなければ、自分は関節点。 隣接する訪問済みの頂点に関しては、 より祖先へ向かう辺（逆辺含む）の先の 頂点の順序数を保持する。 深く探索していく過程で、より祖先寄りの祖先への逆辺を 調べながら進んでいる。
8
Ｈ Ｉ Ａ Ｂ Ｃ Ｅ Ｄ Ｆ Ｇ 図4.4.2 頂点Dは関節点 頂点Eは関節点 頂点Cは関節点
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); 図4.4.2 頂点Dは関節点 頂点Eは関節点 頂点Cは関節点
9
強連結 （２５５ページ） 部分グラフのうち、強連結であって、 しかもそれ以上頂点を追加すると 強連結でなくなるものを強連結成分という。
図４.４.５ 強連結グラフ 有向グラフの各頂点から任意の 頂点へ至る道が存在するとき、 この有向グラフを強連結であるという。 図４.４.６ 強連結成分への分割
10
強連結成分への分割アルゴリズム 有向グラフの深さ優先探索の応用である。 下降辺は強連結性に貢献しない。
（２５６ページ） 有向グラフの深さ優先探索の応用である。 下降辺は強連結性に貢献しない。 下降辺の両端の頂点について、祖先から子孫へ 木の辺から成る道がすでに存在する。 上昇辺の両端の頂点は同じ強連結成分に属す。 木の辺と上昇辺で閉路を作る。 木の辺で下降し、上昇辺で上昇して元に戻れる。 交差辺は、単純ではない。 強連結成分に属す・属さないの２種類がある。
11
図４.４.７ 深さ優先探索の木と強連結成分の関係 （木の辺だけを見たときは木）
深さ優先探索の木の上で強連結成分を表す。 実際は下降辺・上昇辺・交差辺も存在してて、 それらとともに強連結成分を作っている。 各強連結成分に最初に訪問した頂点 ＝その部分木の根。 部分木の根からその子孫に到達可能。 部分木が強連結成分なら、 木の辺を０回以上通った後で 上昇辺か交差辺を通って根に戻れる。 深さ優先探索の木の葉から、上昇辺 や交差辺を通ってその葉の祖先に たどり着くことができ、そういう祖先の うちで最も根に近いものを求める。 教科書のlowlink変数 強連結成分を見つけたら、 この辺を木からはずす。 図４.４.７ 深さ優先探索の木と強連結成分の関係 （木の辺だけを見たときは木）
12
そこからたどれる最も根に 近い頂点の訪問順を更新する。 訪問済みなので木の辺じゃない。
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); }} 訪問順ｓｅｑ 教科書のｌｏｗｌｉｎｋ 未訪問の場合は探索を進める。 隣の頂点が訪問済みの場合は、 そこからたどれる最も根に 近い頂点の訪問順を更新する。 訪問済みなので木の辺じゃない。 深さ優先探索し終わった後、 調べてみたら、 強連結成分の根だった （ｓｅｑ＝ｌｏｗｌｉｎｋ） 交差辺経由で探索されないようにする。 この根からつながる 強連結成分を取り出す。
13
Ｃ Ｅ Ａ Ｄ Ｂ Ｆ Ｉ Ｇ Ｈ 図4.4.9 I H G 図 ４.４.９ プログラムの実行例 C F D E B A
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); Ｃ Ｅ Ａ Ｄ Ｂ Ｆ Ｉ Ｇ Ｈ 図4.4.9 I H G C F D E B A 図 ４.４.９ プログラムの実行例 （実線は木の辺、点線はそれ以外の辺）
14
擬似コード （Ｐｓｅｕｄｏｃｏｄｅ） 擬似プログラムともいう。 アルゴリズムを既存のプログラミング言語に似せて書いたもの。
かつてはＰａｓｃａｌやＦｏｒｔｒａｎ、今はＪａｖａ？ 要点だけ書くのでそのまま動く保障はない。 教科書のコードはかなり完成度が高い。 Javaだと、どこでも動くコードを書きやすい。
15
期末試験 教室: Ｃ１０１ （いつものＡ１０７は使えません） 日時: ２０１２年７月３０日１６時３０分～１８時００分 持ち込み可 学生証必携
教室: Ｃ１０１ （いつものＡ１０７は使えません） 日時: ２０１２年７月３０日１６時３０分～１８時００分 入室限度: １６時５０分まで 退出可能: １７時００分より 持ち込み可 教科書・資料(自筆・コピー問わず)は持ち込み可 人間・パソコン・携帯電話・PHSなど持ち込み不可 学生証必携 持っていない場合は教務で発行してもらうこと
Similar presentations
