Python为x和y点创建可能的路径

Question

我有一个X和Y点的列表，将被导入到程序中。我想知道是否可以建立一个如何连接它们的目录？几乎像树图，但它不使用边，而是使用x和y点。

示例中的[0]将是起点，数字将是导入文件中的点。

例如

                           ----4------5
                           |
8------7-----6----[0]------1-------2-----3
       |
    9---

我找到了一个名为Breadth-first search的算法，如果给定一个起点和终点，它就能确定最佳路径。我知道该算法用于搜索可能的路径但不确定路径。如果给出上面例子中的点数..

point    X    Y
  0      0    0
  1      1    0
  2      2    0
  3      3    0
  4      1.5  0.5
  5      2.5  0.5
  6      -1   0
  7      -2   0
  8      -3   0
  9      -2.5 -0.5

我想上面的要点产生一个类似的目录..

graph = {
        '0': ['1', '6'],
        '1': ['2', '4'],
        '2': ['3'],
        '4': ['5'],
        '6': ['7'],
        '7': ['8','9']
        }

我为here找到了一个很好的例子Breadth-first Search，但它需要已经制作的目录结构。任何帮助或建议表示赞赏。

广度优先Search.py

def bfs(graph, start, end):
    queue = []
    queue.append([start])
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print(bfs(graph, '0', '5'))

Answer 1

假设您打算在结果中包含5作为键，您可以使用递归来创建所需的字典：

import math, collections
data = {0.0: [0.0, 0.0], 1.0: [1.0, 0.0], 2.0: [2.0, 0.0], 3.0: [3.0, 0.0], 4.0: [1.5, 0.5], 5.0: [2.5, 0.5], 6.0: [-1.0, 0.0], 7.0: [-2.0, 0.0], 8.0: [-3.0, 0.0], 9.0: [-2.5, -0.5]}
def group(d, start, seen = []):
   x, y = d[start]
   r = [a for a, [j, k] in d.items() if a != start and a not in seen and math.hypot(abs(x-j), abs(y-k)) <= 1]
   if not r:
     return {}
   result = {start:r}
   for i in r:
     result.update(group(d, i, seen+[start, *r]))
   return result

result = group(data, 0) 

输出：

{0: [1.0, 6.0], 1.0: [2.0, 4.0], 2.0: [3.0, 5.0], 4.0: [5.0], 5.0: [3.0], 6.0: [7.0], 7.0: [8.0, 9.0]}

---

将值转换为字符串：

new_result = {str(int(a)):list(map(str, map(int, b))) for a, b in result.items()}

输出：

{'0': ['1', '6'], '1': ['2', '4'], '2': ['3', '5'], '4': ['5'], '5': ['3'], '6': ['7'], '7': ['8', '9']}

Answer 2

如你所说，广度优先搜索不是一个算法，可以找到给定两个节点的最佳路径，它只会告诉你是否有连接它们的路径。如果你想要最好的路径，有三种着名的算法：Dijkstra，Bellman-Ford和Floyd-Warshall。在你的情况下，我相信Dijkstra将是最好的选择。

Python中有一个易于使用且很棒的库来处理图形，它被称为Networkx。几乎所有与图形相关的问题都有很多方法，包括我提到的算法。这是在这个库上实现的Dijkstra's algorithm的链接。