通过拥有迷宫房屋（二维）的列表，我如何使用字典创建有向图

Question

我只能做一个无向图。不知道如何制作定向的。

有什么想法吗？

Answer 1

对于冗长的帖子表示歉意。我有时间在火车上消磨时间。

我猜你想要的是一个有向图，表示远离起始位置的所有路径（而不是迷宫的图形表示，迷宫曾经可以用来解决任意开始/结束位置）。

（无意冒犯，但是）这听起来像是家庭作业，或者至少是一项非常适合家庭作业的任务。考虑到这一点，以下解决方案侧重于简单性而不是性能或优雅。

查找

一种直接的方法是首先以更易于导航的格式存储地图，然后从起始节点开始执行以下操作：

1. 每个
2. 邻居的邻居（顶部、底部、左侧、右侧）：
   • 如果不是可能的路径，则忽略
   • 如果我们之前处理过这个节点，则忽略
   • 否则，将此节点添加为边缘并将其推送到队列（不是堆栈，稍后会详细介绍）以进行进一步处理
3. 每个节点队列/堆栈中的节点，从步骤 1 开始重复。

（参见下面的示例实现）

此时，您将得到一个 有向无环图 (DAG)，起始节点位于树的顶部，结束节点作为叶子之一。此时解决这个问题很容易。请参阅有关解决以图形表示的迷宫的答案。

构建图表时可能的优化是一旦找到终点就停止。您最终会得到一个不完整的图表，但如果您只关心最终的解决方案，那么这并不重要。

堆栈还是队列？

请注意，使用堆栈（先进后出）意味着以 深度优先< /a> 方式，使用队列（先进先出）会导致 广度优先 方法。

您通常希望使用队列（如果目的是寻找最短路径，则广度优先。请考虑以下映射：

       START
########   ###### 
########   ######
### b    a ######  
###   ##   ######
###   ## e ######
### c    d ######
########   ######
########      END
#################

如果路径是深度优先遍历的并且在分支 a 处，您碰巧会采取a->e 之前的 a->b 路径，最终会得到图表：

 START
   |
   a
  / \
 b   e   <-- end, since d already visited
 |
 c
 |
 d
  \
   END

但是，使用广度优先方法，a->e e 路径会更早地遇到节点 d，从而产生更短的图形和更好的解决方案：

 START
   |
   a
  / \
 b   e 
 |   |
 c   d
     |
    END

示例代码

提供的示例输入：

..........
#########.
..........
.#########
......#...
#####...#.
##...####.
##.#......
...#######

e = (0,0)
s = (8,0)

免责声明：编写以下代码是为了清楚起见，而不是它没有经过充分测试，因此不能保证正确性，但它应该让您了解可能的情况。

为了简洁起见，我们假设输入文件的格式一致。

# regex to extract start/end positions
import re
re_sepos = re.compile("""
    ^([se])\s* # capture first char (s or e) followed by arbitrary spaces
    =\s*        # equal sign followed by arbitrary spaces
    \(          # left parenthesis
    (\d+),(\d+) # capture 2 sets of integers separated by comma
    \)          # right parenthesis
""", re.VERBOSE)

def read_maze(filename):
    """
    Reads input from file and returns tuple (maze, start, end)
      maze : dict holding value of each maze cell { (x1,y1):'#', ... }
      start: start node coordinage (x1,y1)
      end  : end node coordinate (x2,y2)
    """
    # read whole file into a list
    f = open(filename, "r")
    data = f.readlines()
    f.close()

    # parse start and end positions from last 2 lines
    pos = {}
    for line in data[-2:]: 
        match = re_sepos.match(line)
        if not match:
            raise ValueError("invalid input file")
        c,x,y = match.groups() # extract values
        pos[c] = (int(x),int(y))
    try:
        start = pos["s"]
        end   = pos["e"]
    except KeyError:
        raise ValueError("invalid input file")

    # read ascii maze, '#' for wall '.' for empty slor 
    # store as maze = { (x1,y1):'#', (x2,y2):'.', ... }
    # NOTE: this is of course not optimal, but leads to a simpler access later 
    maze = {}
    for line_num, line in enumerate(data[:-3]): # ignore last 3 lines
        for col_num, value in enumerate(line[:-1]): # ignore \n at end
            maze[(line_num, col_num)] = value

    return maze, start, end

def maze_to_dag(maze, start, end):
    """
    Traverses the map starting from start coordinate.
    Returns directed acyclic graph in the form {(x,y):[(x1,y1),(x2,y2)], ...}
    """
    dag = {}        # directed acyclic graph
    queue = [start] # queue of nodes to process

    # repeat till queue is empty
    while queue:
        x,y = queue.pop(0)      # get next node in queue
        edges = dag[(x,y)] = [] # init list to store edges

        # for each neighbour (top, bottom, left, right)
        for coord in ((x,y-1), (x,y+1), (x-1,y), (x+1,y)): 
            if coord in dag.keys(): continue   # visited before, ignore

            node_value = maze.get(coord, None) # Return None if outside maze
            if node_value == ".": # valid path found
                edges.append(coord) # add as edge
                queue.append(coord) # push into queue

                # uncomment this to stop once we've found the end point
                #if coord == end: return dag

    return dag

if __name__ == "__main__":
    maze,start,end = read_maze("l4.txt")
    dag = maze_to_dag(maze, start, end)
    print dag

Answer 2

此页面提供了一个关于使用 python 实现图形的很好的教程。从文章中，这是一个由字典表示的目录图的示例：

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

也就是说，您可能还想查看现有的图形库，例如 NetworkX 和 igraph。

Answer 3

由于您已经有了一个列表，请尝试创建邻接矩阵而不是字典。

list_of_houses = []
directed_graph = [][]
for i in xrange(len(list_of_houses)):
    for i in xrange(len(list_of_houses)):
        directed_graph[i][i] = 0

然后，对于从一栋房子到另一栋房子（或有连接）的任何新边缘

directed_graph[from_house][to_house] = 1

，您就完成了。如果从 house_a 到 house_b 存在一条边，则 directed_graph[house_a][house_b] == 1。