广度优先搜索求无权图节点间距离

bicpotato

2021 年 06 月 12 日

385 次浏览

暂无评论

2151字数

编程

## 问题背景

在一个随机生成的无加权图（保证各节点连接）中，求任意一点到其他各点的最短距离。

## 问题分析与实现

最常用算法如Dijkstra算法的时间复杂度为$O(n^3)$，在某些特定情况不能满足需要；而在BFS中，我们考虑到，bfs记录的各节点的层次与各个节点与该节点的距离有对应关系，假设边的长度为1，那么节点层次即为距离。

为实现此算法，我们维护两个队列OPEN和CLOSED，以及一个二维数据distance，用于记录节点距离。实现过程如下图。

```flowchart
begin=>start: 开始
op1=>operation: 把节点送入OPEN表
cond=>condition: OPEN为空？
op2=>operation: 把Open表的第一个节点取出放入
Closed表，并记该节点为n
cond2=>condition: 节点n可扩展？
op3=>operation: 扩展节点n，将其不在Closed表和
Open表中的子节点(判重）放入Open表的尾
部，并为每一个子节点记录节点的层次
end0=>end: 退出
begin->op1
op1->cond
cond(yes)->op2
op2->cond2
cond2(yes)->op3
cond2(no)->cond
op3->cond
cond(no)->end0
```

代码实现如下

```python
class Node:
    def __init__(self, number):
        self.__number = number
        self.__nextinfo = []

def get_next(self):
        lst = []
        for number in self.__nextinfo:
            lst.append(number)
        return lst

class Map:
    def __init__(self, design: dict):
        self.xy = design["xy"]
        design = design["design"]
        self.N = len(design) # 节点数，增加代码可读性
        self.nodes = [Node(i) for i in range(self.N+2)]
        self.nodes[1].set_power(INIT_POWER_1, True)
        self.nodes[self.N].set_power(INIT_POWER_2, True)

for number in design.keys():
            for nextnumber in design[number].keys():
                self.nodes[number].set_connection(nextnumber)

def Breadth_First_Search(distance:list, map_info, node_index):
    open = collections.deque()
    close = collections.deque()
    self.distance[node_index][node_index] = 0
    while len(open) != 0:
        n = open.popleft()
        close.append(n)
        if map_info[n].get_next():
            for sub_node_index in map_info[n].get_next:
                if sub_node_index not in open or sub_node_index not in close:
                    distance[node_index][sub_node_index] = sub_node_index[node_index][n] + 1
    return distance

def ShortestPath():
    distance = [[-1 for j in range(1, map_info.N)] for i in range(1, map_info.N)]
    for i in range(map_info.N):
        Breadth_First_Search(distance,map_info, i)
    return distance
```

最后修改：2021 年 09 月 04 日