如何优化基于BFS的Agent出口路径阻断程序以提升效率？

需求概述 #

我正在开发一款基于**Breadth First Search（BFS）**算法的程序，用于切断连接链路，阻止Bobnet Agent从当前位置前往图中的出口网关。程序需输出需切断的链路信息。

输入格式说明 #

初始化输入：

• 第一行：3个整数N、L、E
  • N：关卡中的节点总数（包含网关）
  • L：关卡中的链路数量
  • E：出口网关的数量
• 接下来L行：每行2个整数（N1, N2），表示节点N1与N2间存在链路
• 接下来E行：每行1个整数EI，表示出口网关的节点索引

当前问题 #

当前程序逻辑为：每次检测Agent位置，切断其附近最可能的链路，但当前程序需39步完成阻断，存在更高效的实现方案。希望找出程序问题并优化其效率。

现有代码 #

import sys
from collections import deque

class Binder:
    
    def __init__(self, id, pre_binder):
        self.id = id
        self.pre_binder = pre_binder
        
class Game:

    def __init__(self):
        # n: the total number of nodes in the level, including the gateways
        # l: the number of links
        # e: the number of exit gateways
        n, l, e = [int(j) for j in input().split()]
        self.graph = {i: [] for i in range(n)}

        for _ in range(l):
            # n1: N1 and N2 defines a link between these nodes
            n1, n2 =  [int(j) for j in input().split()]
            self.graph[n1].append(n2)
            self.graph[n2].append(n1)

        self.exit_gateways = [int(input()) for _ in range(e)] # the index of a gateway node

    def breadth_first_search(self, root):
        print(f"Graph nodes: {self.graph}", file=sys.stderr)

        visited, queue = set(), deque([Binder(root, None)])
        visited.add(root)

        while queue:
            binder = queue.popleft()
            vertex = binder.id
            print(f"Bobnet Location: {self.graph[vertex]}", file=sys.stderr)

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    new_binder = Binder(neighbor, binder)
                    queue.append(new_binder)

                if neighbor in self.exit_gateways:
                    return Binder(neighbor, binder)
                            
def trace_and_cut_link(result_binder):
    current_binder = result_binder
    while current_binder.pre_binder is not None:
        previous_binder = current_binder.pre_binder
        link_to_cut = (previous_binder.id, current_binder.id)
        print(f'Cutting link: {link_to_cut}', file=sys.stderr)
        current_binder = previous_binder
    print(link_to_cut[0], link_to_cut[1])

game = Game()

while True:
    node_index = int(input())  # The index of the node on which the Bobnet agent is positioned this turn
    result_binder = game.breadth_first_search(node_index)
    trace_and_cut_link(result_binder)

运行示例 #

Game information:
Graph nodes: {0: [2, 10, 9, 5, 12, 11, 17, 7, 13, 14, 6, 3, 4, 15, 1, 16, 8], 
1: [2, 17, 0, 37], 
2: [0, 37, 1, 3, 35], 
3: [34, 0, 2, 4], 
4: [5, 33, 0, 3], 
5: [4, 0, 6], 
6: [5, 0, 7], 
7: [8, 0, 6], 
8: [7, 9, 0], 
9: [0, 10, 8], 
10: [0, 11, 9], 
11: [10, 0, 12], 
12: [0, 11, 13], 
13: [14, 0, 12], 
14: [13, 0, 15], 
15: [16, 14, 0], 
16: [17, 15, 0], 
17: [16, 0, 1], 
18: [26, 24, 23, 22, 27, 25, 21, 19, 20], 
19: [27, 20, 18], 
20: [19, 21, 18], 
21: [29, 22, 18, 20], 
22: [18, 23, 21, 36], 
23: [18, 24, 35, 22, 37], 
24: [18, 23, 25, 37], 
25: [26, 24, 18], 
26: [18, 25, 27], 
27: [19, 18, 26], 
28: [36, 32, 34, 31, 35, 29, 33, 30], 
29: [21, 30, 28, 36], 
30: [31, 29, 28], 
31: [30, 28, 32], 
32: [28, 33, 31], 
33: [32, 4, 34, 28], 
34: [3, 35, 28, 33], 
35: [37, 34, 23, 28, 36, 2], 
36: [28, 22, 35, 29], 
37: [35, 2, 23, 1, 24]}

Block the Agent!
Agent is at position 37

Standard Output Stream:
37 35
Game information:
Link [37-35] severed
Agent moved from 37 to 2

Standard Output Stream:
2 0
Game information:
Link [2-0] severed
Agent moved from 2 to 35

Standard Output Stream:
35 28
Game information:
Link [35-28] severed
Agent moved from 35 to 23

内容的提问来源于stack exchange，提问作者spoolito