python-3.x - DFS/BFS 实现:有向图
问题描述
尝试在有向图中显示所有节点时,会显示不正确的节点!
是什么,我在这里做错了吗?另外,如何使用图形字典而不是定义所有边,有没有办法使用字典?
预期成绩:
1 --> Node(s): ['2', '4']
2 --> Node(s): ['3', '5', '7']
3 --> Node(s): ['1', '6']
4 --> Node(s): ['6']
5 --> Node(s): ['7', '8']
6 --> Node(s): ['8']
7 --> Node(s): ['8', '9']
8 --> Node(s): ['9']
实际结果:
1 --> Node(s): [2, 3, 4]
2 --> Node(s): [1, 3, 5, 7]
3 --> Node(s): [1, 2, 6]
4 --> Node(s): [1, 6]
5 --> Node(s): [2, 7, 8]
6 --> Node(s): [3, 4, 8]
7 --> Node(s): [2, 5, 8, 9]
8 --> Node(s): [5, 6, 7, 9]
9 --> Node(s): [7, 8]
如果将图形字典用作:
graph = {'1': ['2','4'], '2': ['3', '5', '7'], '3': ['1','6'], '4': ['6'],
'5': ['7','8'], '6': ['8'], '7': ['8', '9'], '8': ['9']}
代码:
n_nodes = {}
# Search for all nodes and create an empty array for each node
def add_nodes(node_array):
for node in node_array:
if node not in n_nodes:
n_nodes[node] = []
def add_edge(edge):
u, v = edge
if (v not in n_nodes[u]) and (u not in n_nodes[v]):
n_nodes[u].append(v)
if (u != v):
n_nodes[v].append(u)
add_nodes([i+1 for i in range(9)])
add_edge((1,2))
add_edge((1,4))
add_edge((2,3))
add_edge((2,5))
add_edge((2,7))
add_edge((3,1))
add_edge((3,6))
add_edge((4,6))
add_edge((5,7))
add_edge((5,8))
add_edge((6,8))
add_edge((7,8))
add_edge((7,9))
add_edge((8,9))
# Print All Nodes
for key in sorted(n_nodes):
print (key, " --> Node(s):",sorted(n_nodes[key]))
解决方案
您的代码将边视为无向边:它们总是在两个方向上添加。所以只需删除在相反方向添加边缘的代码。
改变这个:
if (v not in n_nodes[u]) and (u not in n_nodes[v]):
n_nodes[u].append(v)
if (u != v):
n_nodes[v].append(u)
...到:
if v not in n_nodes[u]:
n_nodes[u].append(v)
推荐阅读
- webpack - (多错误)找不到模块:错误:无法解析“babel/loader”
- c - 使用 SAR ADC 进行相位角测量
- python - 运行随机森林分类器时出错
- sqlite - system.missingmethodexception: '方法未找到:void sqlite.sqliteconnection..ctor(string,sqlite.sqliteopenflags,bool,object)'
- ansible - 退出 Ansible 循环
- vue.js - 右对齐 v-list-item-content
- tensorflow - 如何在 Keras 中分别优化多个损失函数?
- python - VSCode Python 交互窗口 - 如何停止 Jupyter 服务器?
- javascript - 记录时如何将布尔值记录为未定义的复选框?
- c# - 如何将字符串格式化为特定模式?