幅優先探索プログラムにクラスの概念を導入した

graph_module.py

from collections import deque
from typing import List, Dict, Optional


class Graph:
    def __init__(self, data: List[Dict]):
        """初期化時にグラフを構築する"""
        self.graph = self._build_graph(data)

    def _build_graph(self, data: List[Dict]) -> Dict[int, List[int]]:
        """元データからグラフを構築する"""
        graph = {}
        for edge in data:
            n1, n2 = edge['node1'], edge['node2']
            direction = edge['direction']

            if direction == 1:  # 片方向
                graph.setdefault(n1, []).append(n2)
                graph.setdefault(n2, [])  # 孤立ノードも確保
            elif direction == 2:  # 双方向
                graph.setdefault(n1, []).append(n2)
                graph.setdefault(n2, []).append(n1)
        return graph

    def bfs_shortest_path(self, start: int, goal: int) -> Optional[List[int]]:
        """幅優先探索で最短経路を返す"""
        queue = deque([[start]])
        visited = set()

        while queue:
            path = queue.popleft()
            node = path[-1]

            if node == goal:
                return path

            if node not in visited:
                visited.add(node)
                for neighbor in self.graph.get(node, []):
                    queue.append(path + [neighbor])
        return None

    def show_graph(self):
        """内部のグラフ構造を出力する"""
        from pprint import pprint
        pprint(self.graph)

main.py

from graph_module import Graph

data = [
    {'node1': 1000, 'node2': 1050, 'direction': 1, 'load': 1, 'unload': 0},
    {'node1': 1050, 'node2': 1200, 'direction': 2, 'load': 1, 'unload': 0},
    {'node1': 1200, 'node2': 1250, 'direction': 1, 'load': 0, 'unload': 1},
    {'node1': 1250, 'node2': 1300, 'direction': 1, 'load': 1, 'unload': 0},
    {'node1': 1100, 'node2': 1000, 'direction': 1, 'load': 0, 'unload': 1},
    {'node1': 1100, 'node2': 1250, 'direction': 1, 'load': 1, 'unload': 0},
]

g = Graph(data)

print("🔹 グラフ構造:")
g.show_graph()

start_node = 1000
goal_node = 1200

print(f"\n🚩 最短経路（{start_node} → {goal_node}）:")
path = g.bfs_shortest_path(start_node, goal_node)
print(path)

出力結果

🔹 グラフ構造:
{1000: [1050],
 1050: [1200],
 1100: [1000, 1250],
 1200: [1050, 1250],
 1250: [1300],
 1300: []}

🚩 最短経路（1000 → 1200）:
[1000, 1050, 1200]