作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我的代码在计算图中可到达的顶点时遇到问题。
我有以下图表代码
class Vertices():
number = 0
def __init__(self):
Vertices.number += 1
self.number = Vertices.number
self.Reachable= []
我通过以下方式创建图表
a = Vertices()
a.Reachable = [1,2]
b = Vertices()
b.Reachable = [3]
c = Vertices()
c.Reachable= [3]
List = []
List.append(a)
List.append(b)
List.append(c)
因此,作为 a 的顶点 1 有一条到其自身和 b 的边。 b 和 c 的情况类似。
我们可以使用 List 在图上移动,即对于顶点 a,它可以到达 List[trans-1],其中 trans 指的是 a 的可到达列表(List[0] 和 List[1])
现在在这个图中,我必须计算每个顶点的可达性,即为每个顶点计算它可以到达的顶点。例如,a 可以到达 a、b 和 c
我读到可以使用集合在所有列表中进行深度优先搜索。您能为我提供一个如何继续的解决方案吗?
任何人都可以告诉我如何使用集合,因为我认为它对于这个问题来说非常理想,因为它具有与之相关的并集和差函数......PS:这不是学校作业......
最佳答案
使用 well-known solution 怎么样?解决你的问题吗?
首先,您需要一个图表的数据结构。您可以将其作为列表字典来执行,其中每个顶点表示为键,可到达的顶点是列表值。
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
如果您将图表示为如上所示,则查找 B 的相邻顶点将只是
neighbours_of_B = graph['B']
和(来自同一站点)找到所有没有循环的路径将是:
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
并运行它:
find_all_paths(graph, 'A', 'D')
希望有帮助。请通过上面的链接了解更多相关信息。
关于python - 查找图中顶点的可达顶点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4445112/
有点迷茫.. 在git community manual , 它说 The git log command can show lists of commits. On its own, it show
我是一名优秀的程序员,十分优秀!