图论DFS(Depth First Search)Algorithm深度优先搜索遍历空间平面图选择路径，networkx，Python

朴灿烈づ我的快乐病毒、 2023-10-02 14:51 1阅读 0赞

**图论DFS(Depth First Search)Algorithm深度优先搜索遍历空间平面图选择路径，networkx，Python**

程序初始代码是模式0，即随机生成最多20个障碍物点，验证算法的效果。打红色X点表示此路不通。出发点是（1，1），终点是（5，7）。最终红色的点即为选出的路径，并用红色的粗线连起来。

import random
    
    import networkx as nx
    import matplotlib.pyplot as plt
    
    WALKABLE = 'walkable'
    PARENT = 'parent'
    VISITED = 'visited'
    
    
    def my_graph():
        M = 7
        N = 9
        G = nx.grid_2d_graph(m=M, n=N)
        pos = nx.spring_layout(G, iterations=100)
    
        nx.draw_networkx(G, pos=pos,
                         # labels=labels, #labels = dict(((i, j), 'Phil') for i, j in G.nodes())
                         font_size=8,
                         font_color='white',
                         node_color='green',
                         node_size=500,
                         width=1)
    
        START = (1, 1)
        GOAL = (M - 1 - 1, N - 1 - 1)
    
        # 0,随机生成障碍物点
        # 1,精心挑选的障碍物构成陷阱
        obstacle_mode = 0
        road_closed_nodes = []
        if obstacle_mode == 0:
            obstacle = 20  # 障碍物（断点、不可达点）数量
            road_closed_nodes = obstacle_nodes(G, START, GOAL, obstacle, M, N)
        elif obstacle_mode == 1:
            road_closed_nodes = dummy_nodes(G)
    
        nx.draw_networkx_nodes(
            G, pos,
            nodelist=road_closed_nodes,
            node_size=500,
            node_color="red",
            node_shape="x",
            # alpha=0.3,
            label='x'
        )
    
        dfs(G, START, GOAL)
        path = find_path_by_parent(G, START, GOAL)
        print('path', path)
    
        nx.draw_networkx_nodes(
            G, pos,
            nodelist=path,
            node_size=400,
            node_color="red",
            node_shape='o',
            # alpha=0.3,
            # label='NO'
        )
    
        # nx.draw_networkx_nodes(
        #     G, pos,
        #     nodelist=path,
        #     node_size=100,
        #     node_color="yellow",
        #     node_shape='*',
        #     # alpha=0.3,
        #     # label='NO'
        # )
    
        path_edges = []
        for i in range(len(path)):
            if (i + 1) == len(path):
                break
            path_edges.append((path[i], path[i + 1]))
    
        print('path_edges', path_edges)
    
        # 把path着色加粗重新描边
        nx.draw_networkx_edges(G, pos,
                               edgelist=path_edges,
                               width=8,
                               alpha=0.5,
                               edge_color="r")
    
        plt.axis('off')
        plt.show()
    
    
    # 基于栈实深度优先遍历搜索
    def dfs(G, START, GOAL):
        for n in G.nodes():
            G.nodes[n]['visited'] = False
    
        stack = []  # 用列表当作一个栈，只在栈顶操作（数组的第1个位置）
        stack.append(START)
    
        close_list = []
    
        while True:
            if len(stack) == 0:
                break
    
            print('-----')
            print('stack-', stack)
    
            visit_node = stack[0]
            G.nodes[visit_node]['visited'] = True
            print('访问', visit_node)
    
            if visit_node == GOAL:
                break
    
            close_list.append(visit_node)
    
            count = 0
            neighbors = nx.neighbors(G, visit_node)
            for node in neighbors:
                visited = G.nodes[node][VISITED]
                try:
                    walkable = G.nodes[node][WALKABLE]
                except:
                    walkable = True
    
                if (visited) or (node in stack) or (node in close_list) or (not walkable):
                    continue
    
                G.nodes[node][PARENT] = visit_node
                stack.append(node)
                count = count + 1
    
            if count == 0:
                print(visit_node, '尽头')
                del (stack[0])
                print('弹出', visit_node)
    
            print('stack--', stack)
    
        return stack
    
    
    def find_path_by_parent(G, START, GOAL):
        t = GOAL
        path = [t]
        is_find = False
        while not is_find:
            for n in G.nodes(data=True):
                if n[0] == t:
                    parent = n[1][PARENT]
                    path.append(parent)
    
                    if parent == START:
                        is_find = True
                        break
    
                    t = parent
    
        list.reverse(path)
        return path
    
    
    # 障碍物点
    def obstacle_nodes(G, START, GOAL, obstacle, M, N):
        road_closed_nodes = []
        for i in range(obstacle):
            n = (random.randint(0, M - 1), random.randint(0, N - 1))
            if n == START or n == GOAL:
                continue
            if n in road_closed_nodes:
                continue
    
            G.nodes[n][WALKABLE] = False
            road_closed_nodes.append(n)
    
        return road_closed_nodes
    
    
    def dummy_nodes(G):
        fun_nodes = []
    
        n0 = (1, 2)
        G.nodes[n0][WALKABLE] = False
        fun_nodes.append(n0)
    
        n1 = (1, 3)
        G.nodes[n1][WALKABLE] = False
        fun_nodes.append(n1)
        n2 = (1, 4)
        G.nodes[n2][WALKABLE] = False
        fun_nodes.append(n2)
        n3 = (1, 5)
        G.nodes[n3][WALKABLE] = False
        fun_nodes.append(n3)
        n4 = (1, 6)
        G.nodes[n4][WALKABLE] = False
        fun_nodes.append(n4)
        n5 = (2, 6)
        G.nodes[n5][WALKABLE] = False
        fun_nodes.append(n5)
        n6 = (3, 6)
        G.nodes[n6][WALKABLE] = False
        fun_nodes.append(n6)
        n7 = (4, 6)
        G.nodes[n7][WALKABLE] = False
        fun_nodes.append(n7)
        n8 = (5, 6)
        G.nodes[n8][WALKABLE] = False
        fun_nodes.append(n8)
        n9 = (5, 5)
        G.nodes[n9][WALKABLE] = False
        fun_nodes.append(n9)
        n10 = (5, 4)
        G.nodes[n10][WALKABLE] = False
        fun_nodes.append(n10)
        n11 = (5, 3)
        G.nodes[n11][WALKABLE] = False
        fun_nodes.append(n11)
        n12 = (5, 2)
        G.nodes[n12][WALKABLE] = False
        fun_nodes.append(n12)
    
        return fun_nodes
    
    
    if __name__ == '__main__':
        my_graph()

算法选路效果：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

由于代码中对于随机生成的障碍物点限制不多（不等于出发点和终点即可），那么极大概率生成的点集把出发点到终点之间的路线堵死，最终选路选不出来，出于简单代码说明算法的目的，程序对这些情况未增加代码量规避处理。

现在，使用障碍物模式1，

obstacle_mode = 1

故意生成一组精心挑选的点，这些点形成一个凹形的围墙，围墙正面对出发点，同时把出发点改成(2,2)，

START = (2, 2)

看看算法的表现：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

算法走出的路线很聪明，机智的以捷径绕过围墙。

[图论BFS(Breath First Search)Algorithm广度优先搜索遍历空间平面网格图路径选择，networkx，Python\_Zhang Phil-CSDN博客][BFS_Breath First Search_Algorithm_networkx_Python_Zhang Phil-CSDN]

[networkx图论Dijkstra Algorithm最短路径实现，Python\_Zhang Phil-CSDN博客][networkx_Dijkstra Algorithm_Python_Zhang Phil-CSDN]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f713ae4cbcf646d19b607e2ad227cde6.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAemhhbmdwaGls,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b599a14d3fef4d3c9cc1f3e7c5ef9091.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAemhhbmdwaGls,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/26aff62e55c847d887f5340dbbca5e96.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAemhhbmdwaGls,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/647c389c11144fbc82600c9ce23d3b48.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAemhhbmdwaGls,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/bf85a63c63634c699d60057ebb6ba6d4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAemhhbmdwaGls,size_20,color_FFFFFF,t_70,g_se,x_16
[BFS_Breath First Search_Algorithm_networkx_Python_Zhang Phil-CSDN]: https://zhangphil.blog.csdn.net/article/details/121267357
[networkx_Dijkstra Algorithm_Python_Zhang Phil-CSDN]: https://zhangphil.blog.csdn.net/article/details/121171499