Week 11 (2025/7/4)¶

今週の目的

グラフのデータを探索する。

今週のキーワード

キューを用いた幅優先探索の実装
最短パスの発見
スタックを用いた深さ優先探索の実装

今回はグラフの探索プログラムとして、幅優先探索と深さ優先探索を実装する。幅優先探索は、グラフの各点において、隣接する未訪問点全てを連続して訪問していく探索である。一方、深さ優先探索は、隣接する未訪問点を一つ選び、前進操作を繰り返していく探索である。

課題1：幅優先探索で全てのノードを辿る¶

前々回実装したGraphクラスを継承して、あるノードから全てのノードを幅優先探索で探索するsearch_with_BFSメソッドを備えたGraphSearchクラスを定義せよ。

GraphSearchクラスの仕様は、以下の通りである。

GraphSearchクラス

class GraphSearch() Graphクラスのサブクラス
グラフ上のノードを探索することができるクラス

インスタンス変数

busstops: バス停情報を格納するための辞書データ（key: バス停ID、value: Stopインスタンス）

search_with_BFS(start)
指定されたノードから幅優先探索で全ノードを探索し最長パスを出力するメソッド

パラメータ

start: 幅優先探索の開始ノードのID（文字列）

trace_longest_path(parents)
最長のパスを表示するメソッド

パラメータ

parents: 前進操作の出発点のノードと辿ったエッジを格納するための辞書データ（key: 前進操作の目的地のノード、value: 前進操作の出発地のノードと辿ったエッジのタプル）

また、GraphSearchクラスには、バス停IDとバス停名を関連付けられるように、全てのバス停のStopインスタンスを格納するリストをインスタンス変数(変数名：busstops)として追加せよ。最後に、バスの路線データ（kyotocitybus_line.dat）とバス停データ（kyotocitybus_stop.dat）を読み込んでGraphSearchインスタンスを作成し、このインスタンスを用いてED01_1914から全ノードを幅優先探索して、最長（最大ホップ数）のパスを出力せよ。

プログラム実行例

week11_1.py
# 穴埋め問題用のプログラム
from def_graph import Graph  # Graphクラスの読み込み
from def_queue_stack import Stack, Queue  # StackクラスおよびQueueクラスの読み込み
from def_stop import Stop  # Stopクラスの読み込み

class GraphSearch(Graph):
    def __init__(self):
        super().__init__()  # Graphクラスから継承したインスタンス変数の初期化
        self.busstops = {}  # バス停情報を格納するための辞書データ（key: バス停ID、value: Stopオブジェクト）

    def search_with_BFS(self, start):
        queue = [____]  # 幅優先探索用のキューを作成
        parents = {start: None}  # 訪問したノードの一つ前のノードとエッジを格納（key: 訪問ノード、value: 一つ前のノードとエッジのタプル）
        visited = [start]  # 訪問済みリストにstartを追加
        queue.[____](start)  # キューに訪問済みのノードを追加
        while not queue.is_empty():  # キューが空でない限り以下を繰り返す
            current = queue.[____]()  # 訪問済みノードを取り出し現在位置に設定
            if current not in self.node_list:  # 訪問中ノードが存在しなければ
                print('{}のノードがグラフ上に存在しません。'.format(current))
                return
            neighbors = self.[____](current)  # 現在位置の隣接ノードを取得
            for neighbor in neighbors:  # 隣接ノードがある限り以下を繰り返す
                if neighbor.id not in [____]:  # 訪問先候補が未訪問であれば
                    parents[neighbor.id] = (current, neighbor.label)  # 現在位置を訪問先候補の一つ前のノードに設定
                    visited.append(neighbor.id)  # 訪問先候補を訪問済みリストに追加
                    queue.[____](neighbor.id)  # 訪問済みノードをキューに追加
        self.trace_longest_path(parents)  # 最長パスを表示

    def trace_longest_path(self, parents):  # 最長のパスを表示するメソッド
        max_hops = 0  # 最長パスのホップ数
        longest_path = ''  # 最長パスの経路
        furthest_dest = ''  # 最長パスの目的地
        for dest in parents:  # 各ノードを目的地として以下の処理を繰り返す
            current = dest  # 目的地を現在位置とする
            path = self.busstops[current].name  # 現在位置のバス停名を取得
            hops = 0  # 目的地までの距離（ホップ数）を初期化
            parent = parents[current]  # 現在位置の一つ前のバス停と接続するエッジのラベルを取得
            while parent is not None:  
            # 現在位置の一つ前のバス停がある限り（現在位置がスタート地点でない限り）以下を繰り返す
                current = parent[0]  # 現在位置を一つ前のバス停に移動
                path = self.busstops[current].name + ' --[' + parent[1] + ']--> ' + path  
                # 一つ前のバス停とたどったエッジのラベル（路線）をpathに連結
                hops += 1  # ホップ数をインクリメント
                parent = parents[current]  # 現在位置の一つ前のバス停と接続するエッジのラベルを取得
            if hops > max_hops:  # 仮の最大ホップ数を超えれば
                max_hops = hops  # 仮の最大ホップ数を更新
                longest_path = path  # 仮の最長パスを更新
                furthest_dest = dest  # 仮の最長パスの目的地を更新
        print('{}まで{}ホップ：{}'.format(self.busstops[furthest_dest].name, max_hops, longest_path))


if __name__ == '__main__':  # モジュールとしてインポートされるときは実行しない
    fi = open('kyotocitybus_line.dat', 'r', encoding='utf-8')
    bus_network = GraphSearch()
    lines = fi.readlines()
    for line in lines:
        line = line.rstrip()
        items = line.split(' ')  # 1行を半角スペースで区切ってitemsリストに代入
        bus_network.add_undirected_edge(items[0], items[1], items[3])  # 無向エッジを追加

    fi2 = open('kyotocitybus_stop.dat', 'r', encoding='utf-8')
    lines = fi2.readlines()
    for line in lines:
        line = line.rstrip()
        items = line.split(' ') # 1行を半角スペースで区切ってitemsリストに代入
        bus_network.busstops[items[0]] = Stop(items[0], items[1], items[2], items[3], items[4:])

    bus_network.search_with_BFS('ED01_1914')
    fi.close()
    fi2.close()

府道横大路まで37ホップ：立命館大学前 --[快速202号系統]--> 小松原児童公園前 --[快速202号系統]--> 衣笠校前 --[快速202号系統]--> 北野白梅町 --[快速202号系統]--> 西ノ京円町 --[快速202号系統]--> 西大路御池 --[快速202号系統]--> 西大路三条 --[11号系統]--> 西大路四条 --[快速202号系統]--> 西大路五条 --[快速202号系統]--> 西大路七条 --[快速202号系統]--> 西大路駅前 --[快速202号系統]--> 羅城門 --[特18号系統]--> 唐戸町 --[特18号系統]--> 千本十条 --[42号系統]--> 市民防災センター前 --[19号系統]--> 上鳥羽 --[19号系統]--> 鳥羽大橋北詰 --[19号系統]--> 城南宮 --[19号系統]--> 国道赤池 --[19号系統]--> 下鳥羽城ノ越町 --[19号系統]--> 国道下鳥羽 --[22号系統]--> 国道大手筋 --[20号系統]--> 八丁畷 --[22号系統]--> 羽束師志水町 --[22号系統]--> 菱川 --[南2号系統]--> 樋爪口 --[南2号系統]--> 免許試験場前 --[20号系統]--> 上樋爪 --[20号系統]--> 樋爪町 --[20号系統]--> 水垂町 --[20号系統]--> 宮前橋西詰 --[20号系統]--> 納所町 --[20号系統]--> 納所北城堀 --[20号系統]--> 納所岸ノ下 --[20号系統]--> 富ノ森 --[20号系統]--> 南横大路 --[20号系統]--> 洛水高校前 --[20号系統]--> 府道横大路

課題2：最短パスを見つける¶

課題1で作成したGraphSearchクラスに、スタート地点から目的地までの最短パスを見つけるfind_shortest_pathメソッドを追加せよ。

find_shortest_pathメソッドの仕様は、以下の通りである。

find_shortest_pathメソッド

find_shortest_path(start, goal)
指定されたノードから目的地への最短パスを出力するメソッド

パラメータ

start: 開始ノードのID（文字列）
goal: 目的地ノードのID（文字列）

最後に、kyotocitybus_line.datとkyotocitybus_stop.datのデータを読み込んだGraphSearchインスタンスを用いて、ED01_1914からED01_4089までの最短パスを出力せよ。

ヒント

幅優先探索は、スタート地点から１ホップで行ける全てのノード、２ホップで行ける全てのノード、．．．というように近いノードから網羅的に訪問していく探索である。したがって、指定した目的地までの最短パスを求めるには、目的地を見つけるまで幅優先探索を行えばよい。

実行例

京都駅前まで12ホップ：立命館大学前 --[M1号系統]--> 桜木町 --[臨号系統]--> わら天神前 --[臨号系統]--> 北大路バスターミナル --[臨号系統]--> 出町柳駅前 --[203号系統]--> 河原町今出川 --[102号系統]--> 堀川今出川 --[101号系統]--> 堀川丸太町 --[快速9号系統]--> 堀川御池 --[快速9号系統]--> 四条堀川 --[快速9号系統]--> 堀川五条 --[快速9号系統]--> 七条堀川 --[快速9号系統]--> 京都駅前

課題3：深さ優先探索で全ノードを辿る¶

課題1で作成したGraphSearchクラスに、あるノードから全部のノードを深さ優先探索で探索するsearch_with_DFSメソッドを追加せよ。

search_with_DFSメソッドの仕様は、以下の通りである。

search_with_DFSメソッド

search_with_DFS(start)
指定されたノードから深さ優先探索で全ノードを探索し最長パスを出力するメソッド

パラメータ

start: 深さ優先探索の開始ノードのID（文字列）

最後に、kyotocitybus_line.datとkyotocitybus_stop.datのデータを読み込んだGraphSearchインスタンスを用いて、ED01_1914から全ノードを深さ優先で探索し、最長（最大ホップ数）のパスを出力せよ。課題１と結果が異なることに注意せよ。

ヒント

深さ優先探索は、後退操作でどのノードに戻ればいいか記憶するために、前進操作時にスタックに出発地のノードを格納する必要がある。

実行例

中桂まで237ホップ：立命館大学前 --[快速202号系統]--> 小松原児童公園前 --[快速202号系統]--> 衣笠校前 --[快速202号系統]--> 北野白梅町 --[10号系統]--> 府立体育館前 --[10号系統]--> 等持院道 --[10号系統]--> 等持院南町 --[10号系統]--> 妙心寺北門前 --[10号系統]--> 京福妙心寺駅前 --[10号系統]--> 御室仁和寺 --[10号系統]--> 福王子 --[10号系統]--> 鳴滝本町 --[10号系統]--> 宇多野病院前 --[10号系統]--> ユースホステル前 --[10号系統]--> 山越 --[10号系統]--> 山越中町 --[11号系統]--> 山越東町 --[11号系統]--> 太秦開日町 --[11号系統]--> 広沢御所ノ内町 --[11号系統]--> 嵯峨中学前 --[11号系統]--> 嵯峨嵐山駅前 --[11号系統]--> 嵯峨瀬戸川町 --[11号系統]--> 嵯峨小学校前 --[11号系統]--> 野々宮 --[11号系統]--> 嵐山天龍寺前 --[11号系統]--> 嵐山 --[11号系統]--> 角倉町 --[11号系統]--> 下嵯峨 --[11号系統]--> 車折神社前 --[11号系統]--> 有栖川 --[11号系統]--> 生田口 --[11号系統]--> 帷子ノ辻 --[11号系統]--> 太秦開町 --[11号系統]--> 太秦広隆寺前 --[11号系統]--> 太秦東口 --[11号系統]--> 蚕ノ社 --[11号系統]--> 庚申前 --[11号系統]--> 山ノ内 --[11号系統]--> 西大路三条 --[11号系統]--> 西大路四条 --[11号系統]--> 四条御前通 --[11号系統]--> 四条中新道 --[11号系統]--> 壬生寺道 --[11号系統]--> 四条大宮 --[11号系統]--> 四条堀川 --[11号系統]--> 四条西洞院 --[11号系統]--> 四条烏丸 --[100円循環]--> 烏丸三条 --[100円循環]--> 烏丸御池 --[100円循環]--> 堺町御池 --[100円循環]--> 京都市役所前 --[100円循環]--> 河原町三条 --[100円循環]--> 四条河原町 --[11号系統]--> 四条京阪前 --[11号系統]--> 三条京阪前 --[5号系統]--> 役所前 --[10号系統]--> 河原町丸太町 --[10号系統]--> 裁判所前 --[10号系統]--> 烏丸丸太町 --[10号系統]--> 府庁前 --[10号系統]--> 堀川丸太町 --[10号系統]--> 丸太町智恵光院 --[10号系統]--> 千本丸太町 --[10号系統]--> 千本出水 --[10号系統]--> 千本中立売 --[10号系統]--> 千本今出川 --[206号系統]--> 千本上立売 --[206号系統]--> 乾隆校前 --[206号系統]--> 千本鞍馬口 --[206号系統]--> ライトハウス前 --[206号系統]--> 千本北大路 --[北8号系統]--> 佛教大学前 --[北8号系統]--> 旭ヶ丘 --[北8号系統]--> 紫野泉堂町 --[北8号系統]--> 常徳寺前 --[北8号系統]--> 下緑町 --[北8号系統]--> 上堀川 --[特37号系統]--> 東高縄町 --[特37号系統]--> 下鳥田町 --[特37号系統]--> 北大路堀川 --[特37号系統]--> 北大路新町 --[特37号系統]--> 北大路バスターミナル --[臨号系統]--> 出町柳駅前 --[203号系統]--> 百万遍 --[206号系統]--> 京大正門前 --[206号系統]--> 近衛通 --[206号系統]--> 熊野神社前 --[206号系統]--> 東山二条 --[206号系統]--> 東山仁王門 --[206号系統]--> 東山三条 --[206号系統]--> 知恩院前 --[206号系統]--> 祇園 --[207号系統]--> 東山安井 --[207号系統]--> 清水道 --[207号系統]--> 五条坂 --[207号系統]--> 馬町 --[207号系統]--> 東山七条 --[臨号系統]--> 博物館三十三間堂前 --[臨号系統]--> 七条京阪前 --[臨号系統]--> 七条河原町 --[臨号系統]--> 京都駅前 --[特81号系統]--> 塩小路高倉 --[特81号系統]--> 京都駅八条口アバンティ前 --[特81号系統]--> 大石橋 --[特81号系統]--> 札ノ辻 --[特81号系統]--> 十条竹田街道 --[特81号系統]--> 勧進橋 --[特81号系統]--> 深草下川原町 --[特81号系統]--> 竹田久保町 --[特81号系統]--> 竹田出橋 --[特81号系統]--> 七瀬川町 --[特81号系統]--> 竹田城南宮道 --[特81号系統]--> 西墨染通 --[特81号系統]--> 棒鼻 --[特81号系統]--> 住吉 --[特81号系統]--> 西丹波橋 --[特81号系統]--> 西板橋 --[特81号系統]--> 肥後町 --[特81号系統]--> 西大手筋 --[特81号系統]--> 京橋 --[特81号系統]--> 中書島 --[特81号系統]--> 下三栖 --[特81号系統]--> 横大路車庫前 --[南8号系統]--> 国道大手筋 --[南8号系統]--> 三栖公園前 --[南3号系統]--> 伏見警察署前 --[南3号系統]--> 油小路丹波橋 --[南3号系統]--> 城南宮東口 --[特南2号系統]--> パルスプラザ前 --[特南2号系統]--> 国道赤池 --[特南2号系統]--> 赤池 --[特南2号系統]--> 上鳥羽塔ノ森 --[特南2号系統]--> 久我 --[南1号系統]--> 菱妻神社前 --[南1号系統]--> 久我石原町 --[特13号系統]--> 東土川橋 --[特13号系統]--> 国道東土川 --[特13号系統]--> 久世殿城町 --[特13号系統]--> 下久世 --[特南1号系統]--> 久世大薮町 --[特南1号系統]--> 久世工業団地前 --[78号系統]--> 築山 --[13号系統]--> 久世橋西詰 --[特13号系統]--> 久世橋東詰 --[特18号系統]--> 石原団地前 --[特18号系統]--> 吉祥院嶋高町 --[特18号系統]--> 上鳥羽馬廻 --[特18号系統]--> 吉祥院池田町 --[特18号系統]--> 吉祥院蒔絵町 --[特18号系統]--> 上鳥羽村山町 --[特18号系統]--> 上ノ町 --[特18号系統]--> 五丁橋 --[特18号系統]--> 千本十条 --[特18号系統]--> 唐戸町 --[特18号系統]--> 羅城門 --[特18号系統]--> 東寺南門前 --[特18号系統]--> 九条大宮 --[特18号系統]--> 東寺東門前 --[特18号系統]--> 七条大宮 --[特33号系統]--> 七条堀川 --[特33号系統]--> 下京区総合庁舎前 --[16号系統]--> 八条油小路 --[16号系統]--> 八条大宮 --[16号系統]--> 六孫王神社前 --[16号系統]--> 東寺西門前 --[16号系統]--> 御土居 --[16号系統]--> 八条中学前 --[16号系統]--> 西寺前 --[16号系統]--> 洛陽工業高校前 --[208号系統]--> 西大路九条 --[208号系統]--> 西大路駅前 --[特13号系統]--> 西大路八条 --[特13号系統]--> 西大路七条 --[特33号系統]--> 月読橋 --[特33号系統]--> 大門町 --[特33号系統]--> 川勝寺 --[特33号系統]--> 桂大橋 --[特33号系統]--> 桂離宮前 --[特33号系統]--> 下桂 --[特南1号系統]--> 桂消防署前 --[特南1号系統]--> 桂高校前 --[特南1号系統]--> 莚田町 --[特南1号系統]--> 自衛隊前 --[特南1号系統]--> 川島六ノ坪町 --[特南1号系統]--> 高田町 --[西4号系統]--> 物集女 --[西4号系統]--> 第二回生病院前 --[西4号系統]--> 北福西町一丁目 --[西5号系統]--> 京都明徳高校前 --[西8号系統]--> 三ノ宮街道 --[西6号系統]--> 桂イノベーションパーク前 --[西6号系統]--> 京大桂キャンパス前 --[西6号系統]--> 桂御陵坂 --[西6号系統]--> 東桂坂 --[西6号系統]--> 峰ヶ堂町三丁目 --[西6号系統]--> 桂坂センター前 --[西5号系統]--> 桂坂口 --[西5号系統]--> 国道沓掛口 --[西5号系統]--> 新林池公園 --[西8号系統]--> 新林センター前 --[西8号系統]--> 新林公団住宅前 --[西8号系統]--> 東新林町 --[特西3号系統]--> 洛西バスターミナル --[西8号系統]--> 境谷大橋 --[特33号系統]--> 小畑川公園北口 --[特33号系統]--> 国道中山 --[特33号系統]--> 三ノ宮 --[特33号系統]--> 公会堂前 --[特33号系統]--> 樫原 --[69号系統]--> 月見ヶ丘 --[69号系統]--> 千代原口 --[73号系統]--> 平和台町 --[73号系統]--> 上桂前田町 --[73号系統]--> 上桂御正町 --[73号系統]--> 西大橋西詰 --[73号系統]--> 西京極 --[80号系統]--> 西京極運動公園前 --[80号系統]--> 光華女子学園前 --[84号系統]--> 葛野大路高辻 --[84号系統]--> 四条葛野大路 --[臨号系統]--> 京都外大前 --[臨号系統]--> 南広町 --[臨号系統]--> 日新電機前 --[臨号系統]--> 梅津段町 --[臨号系統]--> 長福寺道 --[臨号系統]--> 梅津西浦町 --[臨号系統]--> 梅ノ宮神社前 --[臨号系統]--> 松尾橋 --[29号系統]--> 松尾大社前 --[29号系統]--> 松室北河原町 --[29号系統]--> 苔寺道 --[29号系統]--> 松尾大利町 --[69号系統]--> 上桂駅前 --[69号系統]--> 上桂西居町 --[69号系統]--> 上野橋 --[70号系統]--> 上桂東ノ口 --[70号系統]--> 桂徳大寺 --[70号系統]--> 中桂