我正在实现一个图形类,并想编写一个函数来确定给定路径是否存在。
我的图表示为 {a:{b:c}},其中 a 和 b 是相互连接的顶点,c 是边的权重。 这是一个无向图。我想为无向图实现 does_path_exist() 函数。它目前的计算方式就好像我的图是有向的。
给定:
{0: {1: 5.0, 2: 10.0}, 1: {3: 3.0, 4: 6.0}, 3: {2: 2.0, 4: 2.0, 5: 2.0}, 4: {6: 6.0}, 5: {6: 2.0}, 7: {9: 1.0}, 8: {7: 2.0, 9: 4.0}}
存在从顶点 2 到 3 的路径。由于我的函数是面向方向的,因此它返回 False。
class Graph:
def __init__(self, n):
"""
Constructor
:param n: Number of vertices
"""
self.order = n
self.size = 0
self.vertex = {}
def insert_edge(self, u, v, w): #works fine
if u in self.vertex and v < self.order:
if not v in self.vertex[u]:
self.vertex[u][v] = w
self.size += 1
elif u not in self.vertex and u < self.order and v < self.order:
self.vertex[u] = {}
self.vertex[u][v] = w
self.size += 1
else:
raise IndexError
def does_path_exist(self, u, v): #works for directed graph, but not non-directed graph
if u >= self.order or v >= self.order:
raise IndexError
if u == v:
return True
stac = []
stac.append(u)
visited = []
while len(stac) != 0:
u = stac.pop(0)
if u not in visited:
if u == v:
return True
visited.append(u)
if u in self.vertex:
t = self.vertex[u]
else:
break
a = t.keys()
for u in a:
if u not in visited:
stac.append(u)
return False
我的主要功能:
def main():
g = Graph(10)
g.insert_edge(0,1,5.0)
g.insert_edge(0,2,10.0)
g.insert_edge(1,3,3.0)
g.insert_edge(1,4,6.0)
g.insert_edge(3,2,2.0)
g.insert_edge(3,4,2.0)
g.insert_edge(3,5,2.0)
g.insert_edge(4,6,6.0)
g.insert_edge(5,6,2.0)
g.insert_edge(7,9,1.0)
g.insert_edge(8,7,2.0)
g.insert_edge(8,9,4.0)
print(g.vertex)
print(g.does_path_exist(2,3)) #returns False but should return True
if __name__ == '__main__':
main()
最佳答案
您的循环仅检查传出边缘。如果您给它 u=2
,它找不到来自 2
的传出边缘,因此它会在一次迭代后结束。
您需要:
- 在
insert_edge()
中添加双向有向边。insert_edge()
需要做更多的工作,并且需要更多的内存使用。 - 在顶点字典中搜索循环中的后向边和前向边。
does_edge_exist()
中的计算量显着增加。
关于python - 深度优先搜索中的意外结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55661124/