networkx图论Depth First Search广度优先搜索遍历DFS，基于栈，Python

转x33g5p2x  于2021-11-13 转载在 Python  
字(18.6k)|赞(0)|评价(0)|浏览(614)

（1）深度优先搜索遍历，通常使用栈来保存遍历搜索过的节点记录。当搜索到的节点没有子节点，意味着达到了尽头，开始回退。回退的过程其实就是把栈顶的节点弹出（删掉），然后再次在栈中读第一个元素（本例是列表实现的栈，即为0号元素）。

（2）每个节点用一个标志位标记当前节点是否已经访问过，如果访问过，压入栈顶。

（3）每次迭代独取当前顶点V时候，同时要把顶点V的子节点压入栈。

  1. import networkx as nx
  2. import matplotlib.pyplot as plt
  4. # 记录搜索路径
  5. search_path = []
  7. def my_graph():
  8.     # G = nx.gnm_random_graph(n=6, m=8)
  9.     # G = nx.balanced_tree(r=3, h=2)
  10.     G = nx.random_tree(20)
  12.     pos = nx.spring_layout(G)
  13.     nx.draw_networkx(G, pos,
  14.                      node_color='green',
  15.                      node_size=300,
  16.                      font_size=10,
  17.                      font_color='white',
  18.                      edge_color='gray',
  19.                      width=1,
  20.                      with_labels=True)
  22.     print('G.nodes(data=True)', G.nodes(data=True))
  24.     dfs(G)
  26.     plt.show()
  28. # 基于栈实深度优先遍历搜索
  29. def dfs(G):
  30.     for n in G.nodes():
  31.         G.nodes[n]['visited'] = False
  32.     print(G.nodes(data=True))
  33.     print(G.edges(data=True))
  35.     V = 0
  37.     stack = []  # 用列表当作一个栈，只在栈顶操作（数组的第1个位置）
  38.     stack.append(V)
  40.     while True:
  41.         if len(stack) == 0:
  42.             break
  44.         print('-----')
  45.         print('stack-', stack)
  47.         visit_node = stack[0]
  48.         G.nodes[visit_node]['visited'] = True
  49.         print('访问', visit_node)
  51.         neighbors = nx.neighbors(G, visit_node)
  53.         count = 0
  54.         for node in neighbors:
  55.             visited = G.nodes[node]['visited']
  56.             if (visited) or (node in stack) or (node in search_path):
  57.                 continue
  59.             stack.insert(0, node)
  60.             count = count + 1
  62.         print('nodes', G.nodes(data=True))
  64.         if count == 0:
  65.             print(visit_node, '走到尽头')
  66.             del (stack[0])
  67.             print('弹出', visit_node)
  68.             search_path.append(visit_node)
  70.         print('stack--', stack)
  72.     list.reverse(search_path)
  73.     print('search_path', search_path)
  75.     print('\n==对比深度搜索遍历结果==')
  76.     print('networkx dfs',list(nx.dfs_tree(G,V)))
  78. if __name__ == '__main__':
  79.     my_graph()

生成图：

日志输出：

  1. G.nodes(data=True) [(0, {}), (1, {}), (2, {}), (3, {}), (4, {}), (5, {}), (6, {}), (7, {}), (8, {}), (9, {}), (10, {}), (11, {}), (12, {}), (13, {}), (14, {}), (15, {}), (16, {}), (17, {}), (18, {}), (19, {})]
  2. [(0, {'visited': False}), (1, {'visited': False}), (2, {'visited': False}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': False}), (6, {'visited': False}), (7, {'visited': False}), (8, {'visited': False}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': False}), (18, {'visited': False}), (19, {'visited': False})]
  3. [(0, 7, {}), (1, 4, {}), (1, 10, {}), (1, 5, {}), (1, 19, {}), (2, 8, {}), (2, 17, {}), (3, 7, {}), (5, 17, {}), (6, 16, {}), (7, 8, {}), (8, 15, {}), (9, 18, {}), (9, 14, {}), (11, 15, {}), (12, 16, {}), (13, 18, {}), (14, 16, {}), (14, 17, {})]
  4. -----
  5. stack- [0]
  6. 访问 0
  7. nodes [(0, {'visited': True}), (1, {'visited': False}), (2, {'visited': False}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': False}), (6, {'visited': False}), (7, {'visited': False}), (8, {'visited': False}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': False}), (18, {'visited': False}), (19, {'visited': False})]
  8. stack-- [7, 0]
  9. -----
  10. stack- [7, 0]
  11. 访问 7
  12. nodes [(0, {'visited': True}), (1, {'visited': False}), (2, {'visited': False}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': False}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': False}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': False}), (18, {'visited': False}), (19, {'visited': False})]
  13. stack-- [8, 3, 7, 0]
  14. -----
  15. stack- [8, 3, 7, 0]
  16. 访问 8
  17. nodes [(0, {'visited': True}), (1, {'visited': False}), (2, {'visited': False}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': False}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': False}), (18, {'visited': False}), (19, {'visited': False})]
  18. stack-- [2, 15, 8, 3, 7, 0]
  19. -----
  20. stack- [2, 15, 8, 3, 7, 0]
  21. 访问 2
  22. nodes [(0, {'visited': True}), (1, {'visited': False}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': False}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': False}), (18, {'visited': False}), (19, {'visited': False})]
  23. stack-- [17, 2, 15, 8, 3, 7, 0]
  24. -----
  25. stack- [17, 2, 15, 8, 3, 7, 0]
  26. 访问 17
  27. nodes [(0, {'visited': True}), (1, {'visited': False}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': False}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': False})]
  28. stack-- [5, 14, 17, 2, 15, 8, 3, 7, 0]
  29. -----
  30. stack- [5, 14, 17, 2, 15, 8, 3, 7, 0]
  31. 访问 5
  32. nodes [(0, {'visited': True}), (1, {'visited': False}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': False})]
  33. stack-- [1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  34. -----
  35. stack- [1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  36. 访问 1
  37. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': False})]
  38. stack-- [19, 10, 4, 1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  39. -----
  40. stack- [19, 10, 4, 1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  41. 访问 19
  42. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': False}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  43. 19 走到尽头
  44. 弹出 19
  45. stack-- [10, 4, 1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  46. -----
  47. stack- [10, 4, 1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  48. 访问 10
  49. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': False}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  50. 10 走到尽头
  51. 弹出 10
  52. stack-- [4, 1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  53. -----
  54. stack- [4, 1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  55. 访问 4
  56. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  57. 4 走到尽头
  58. 弹出 4
  59. stack-- [1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  60. -----
  61. stack- [1, 5, 14, 17, 2, 15, 8, 3, 7, 0]
  62. 访问 1
  63. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  64. 1 走到尽头
  65. 弹出 1
  66. stack-- [5, 14, 17, 2, 15, 8, 3, 7, 0]
  67. -----
  68. stack- [5, 14, 17, 2, 15, 8, 3, 7, 0]
  69. 访问 5
  70. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': False}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  71. 5 走到尽头
  72. 弹出 5
  73. stack-- [14, 17, 2, 15, 8, 3, 7, 0]
  74. -----
  75. stack- [14, 17, 2, 15, 8, 3, 7, 0]
  76. 访问 14
  77. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': False}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  78. stack-- [9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  79. -----
  80. stack- [9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  81. 访问 9
  82. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': False}), (19, {'visited': True})]
  83. stack-- [18, 9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  84. -----
  85. stack- [18, 9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  86. 访问 18
  87. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': False}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  88. stack-- [13, 18, 9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  89. -----
  90. stack- [13, 18, 9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  91. 访问 13
  92. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  93. 13 走到尽头
  94. 弹出 13
  95. stack-- [18, 9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  96. -----
  97. stack- [18, 9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  98. 访问 18
  99. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  100. 18 走到尽头
  101. 弹出 18
  102. stack-- [9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  103. -----
  104. stack- [9, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  105. 访问 9
  106. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': False}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  107. 9 走到尽头
  108. 弹出 9
  109. stack-- [16, 14, 17, 2, 15, 8, 3, 7, 0]
  110. -----
  111. stack- [16, 14, 17, 2, 15, 8, 3, 7, 0]
  112. 访问 16
  113. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': False}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  114. stack-- [12, 6, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  115. -----
  116. stack- [12, 6, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  117. 访问 12
  118. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': False}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  119. 12 走到尽头
  120. 弹出 12
  121. stack-- [6, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  122. -----
  123. stack- [6, 16, 14, 17, 2, 15, 8, 3, 7, 0]
  124. 访问 6
  125. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  126. 6 走到尽头
  127. 弹出 6
  128. stack-- [16, 14, 17, 2, 15, 8, 3, 7, 0]
  129. -----
  130. stack- [16, 14, 17, 2, 15, 8, 3, 7, 0]
  131. 访问 16
  132. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  133. 16 走到尽头
  134. 弹出 16
  135. stack-- [14, 17, 2, 15, 8, 3, 7, 0]
  136. -----
  137. stack- [14, 17, 2, 15, 8, 3, 7, 0]
  138. 访问 14
  139. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  140. 14 走到尽头
  141. 弹出 14
  142. stack-- [17, 2, 15, 8, 3, 7, 0]
  143. -----
  144. stack- [17, 2, 15, 8, 3, 7, 0]
  145. 访问 17
  146. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  147. 17 走到尽头
  148. 弹出 17
  149. stack-- [2, 15, 8, 3, 7, 0]
  150. -----
  151. stack- [2, 15, 8, 3, 7, 0]
  152. 访问 2
  153. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': False}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  154. 2 走到尽头
  155. 弹出 2
  156. stack-- [15, 8, 3, 7, 0]
  157. -----
  158. stack- [15, 8, 3, 7, 0]
  159. 访问 15
  160. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': False}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  161. stack-- [11, 15, 8, 3, 7, 0]
  162. -----
  163. stack- [11, 15, 8, 3, 7, 0]
  164. 访问 11
  165. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': True}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  166. 11 走到尽头
  167. 弹出 11
  168. stack-- [15, 8, 3, 7, 0]
  169. -----
  170. stack- [15, 8, 3, 7, 0]
  171. 访问 15
  172. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': True}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  173. 15 走到尽头
  174. 弹出 15
  175. stack-- [8, 3, 7, 0]
  176. -----
  177. stack- [8, 3, 7, 0]
  178. 访问 8
  179. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': False}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': True}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  180. 8 走到尽头
  181. 弹出 8
  182. stack-- [3, 7, 0]
  183. -----
  184. stack- [3, 7, 0]
  185. 访问 3
  186. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': True}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': True}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  187. 3 走到尽头
  188. 弹出 3
  189. stack-- [7, 0]
  190. -----
  191. stack- [7, 0]
  192. 访问 7
  193. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': True}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': True}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  194. 7 走到尽头
  195. 弹出 7
  196. stack-- [0]
  197. -----
  198. stack- [0]
  199. 访问 0
  200. nodes [(0, {'visited': True}), (1, {'visited': True}), (2, {'visited': True}), (3, {'visited': True}), (4, {'visited': True}), (5, {'visited': True}), (6, {'visited': True}), (7, {'visited': True}), (8, {'visited': True}), (9, {'visited': True}), (10, {'visited': True}), (11, {'visited': True}), (12, {'visited': True}), (13, {'visited': True}), (14, {'visited': True}), (15, {'visited': True}), (16, {'visited': True}), (17, {'visited': True}), (18, {'visited': True}), (19, {'visited': True})]
  201. 0 走到尽头
  202. 弹出 0
  203. stack-- []
  204. search_path [0, 7, 3, 8, 15, 11, 2, 17, 14, 16, 6, 12, 9, 18, 13, 5, 1, 4, 10, 19]
  206. ==对比深度搜索遍历结果==
  207. networkx dfs [0, 7, 3, 8, 15, 11, 2, 17, 14, 16, 6, 12, 9, 18, 13, 5, 1, 4, 10, 19]

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/zhangphil/article/details/121202546

内容来源于网络，如有侵权，请联系作者删除！

python算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com