グラフのはなし・その7

ちょっと今日は趣向を変えて, プログラムで語ってみます.

昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます.

ソースコード

こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG になっていますね? なのでこれは半順序を表してるものと見れます.

0 -> 1 -> 3
 |     `-> 4
  `-> 2 -> 5
       `-> 6

これを Python で書くと次のようになります.

# -*- coding: utf-8 -*-                                                                                                                                         
class Node(object):
    def __init__(self, value=0):
        self.value = value
        self.checked = False
        self.children = []

# 点の準備                                                                                                                                                      
node0 = Node(0)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

# 矢印の準備                                                                                                                                                    
node0.children = [node1, node2]
node1.children = [node3, node4]
node2.children = [node5, node6]


# 分かれ道にきたらこの手順を踏む                                                                                                                                
def dfs(node):
    print('-> {0.value}'.format(node))
    if node.checked:
	print(u'チェック済み')
        print('<- {0.value}'.format(node))
        return

    node.checked = True
    for child in node.children:
        dfs(child) # さらに分かれ道にきたら同じ手順を繰り返す                                                                                                   
    else:
        print(u'引き返す')
    print('<- {0.value}'.format(node))


if __name__ == '__main__':
    dfs(node0)

Python2.7 で動くことを確認しています.

出力はこんな感じになりました.

-> 0
-> 1
-> 3
引き返す
<- 3
-> 4
引き返す
<- 4
引き返す
<- 1
-> 2
-> 5
引き返す
<- 5
-> 6
引き返す
<- 6
引き返す
<- 2
引き返す
<- 0

このプログラムではグラフの様子は固定になっていますが,「点の準備」と「矢印の準備」と書かれている部分を修正して, 色々試してみてください.

どうでしたか? 深さ優先探索の様子が分かったでしょうか?

あとがき

「やっつけな雰囲気が漂うが大丈夫か?」「大丈夫だ, 問題ない」

すみません, やっつけはやっつけです.

ただ昨日は言葉で説明しただけなので, 厳密な形で説明しなくてはいけませんでした. そこで Python という比較的ソースが読みやすい言語で書いてみました.

また, プログラムが分かる人にはこっちの方が理解が早いんじゃないかと思って, ちょっと寄り道してやってみました.

それでは, お休みなさい.