如何用字典从二维迷宫房屋列表创建有向图

Question

我只能画一个无向图，完全不知道怎么画有向图。

有没有什么建议？

Answer 1

这个页面提供了一个很好的教程，教你如何用Python实现图形结构。在文章中，有一个用字典表示的目录图的例子：

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

另外，你可能还想看看一些现成的图形库，比如NetworkX和igraph。

Answer 2

既然你已经有了一个列表，不妨试试创建一个邻接矩阵，而不是用字典。

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。

Answer 3

抱歉这篇文章有点长。我在火车上有时间。

我猜您想要的是一个有向图，表示从起始位置出发的所有路径（而不是用来解决任意起点和终点的迷宫图）。

（没有冒犯的意思，但）这听起来像是作业，或者至少是一个非常适合作业的任务。考虑到这一点，下面的解决方案更注重简单，而不是性能或优雅。

方法

一种简单的方法是先将地图存储为更易于导航的格式，然后从起始节点开始，执行以下步骤：

查找邻居（上、下、左、右）
对于每个邻居：
- 如果这不是一条可行的路径，就忽略它
- 如果我们之前处理过这个节点，也忽略它
- 否则，将这个节点添加为边，并将其放入队列（不是栈，稍后会详细说明）以便进一步处理
对队列中的每个节点，重复第1步。

（请参见下面的示例实现）

到此为止，您将得到一个有向无环图（DAG），起始节点在树的顶部，结束节点是其中一个叶子节点。此时解决问题会很简单。请参见这个关于将迷宫表示为图形的解答。

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

栈还是队列？

请注意，使用栈（后进先出）会以深度优先的方式构建图，而使用队列（先进先出）则会导致广度优先的方法。

通常，如果您的目的是寻找最短路径，您会想使用队列（广度优先）。考虑以下地图：

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

如果按照深度优先遍历路径，在分支处，您先走了 >b的路径，而不是>e，最终得到的图是：

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

然而，使用广度优先的方法，>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

如何用字典从二维迷宫房屋列表创建有向图

3 个回答

方法

栈还是队列？

示例代码

撰写回答