在 Python 中查找是否有一条长度超过 k 的路径从源开始
pythonserver side programmingprogramming更新于 2025/10/10 10:52:17
假设我们有一个图,还有一个源顶点和一个数字 k。k 是图从源到目标的路径长度,我们必须检查是否可以找到一条从源开始并以任何其他顶点(作为目标)结束的简单路径(无循环)。该图显示在下面的 −

因此,如果输入为 Source = 0, k = 64,则输出将为 True,因为存在一条简单路径 0 到 7 到 1 到 2 到 8 到 6 到 5 到 3 到 4,此路径长度的总距离为 68,大于 64。
为了解决这个问题,我们将遵循以下步骤 −
使用邻接矩阵 adj 定义图,顺序节点 x 节点并用边成本填充
定义一个函数 solved() 。这将获取源、k、路径
如果 k <= 0,则
返回 True
i := 0
当 i 与 adj[source] 的大小不同时,执行
v := adj[source, i, 0]
w := adj[source, i, 1]
i := i + 1
如果 path[v] 为 True,则
进行下一次迭代
如果 w >= k,然后
返回 True
path[v] := True
如果solve(v, k-w, path)为真,则
返回 True
path[v] := False
返回 False
从主方法中,执行以下操作 −
path := 与节点大小相同的列表,然后用 false 值填充
path[source] := 1
返回 solve(source, k, path)
示例
让我们看看下面的实现以便更好地理解 −
class Graph: def __init__(self, nodes): self.nodes = nodes self.adj = [[] for i in range(nodes)] def insert_edge(self,u, v, w): self.adj[u].append([v, w]) self.adj[v].append([u, w]) def solve(self,source, k, path): if (k <= 0): return True i = 0 while i != len(self.adj[source]): v = self.adj[source][i][0] w = self.adj[source][i][1] i += 1 if (path[v] == True): continue if (w >= k): return True path[v] = True if (self.solve(v, k-w, path)): return True path[v] = False return False def is_there_any_path(self,source, k): path = [False]*self.nodes path[source] = 1 return self.solve(source, k, path) nodes = 9 g = Graph(nodes) g.insert_edge(0, 1, 5) g.insert_edge(0, 7, 9) g.insert_edge(1, 2, 9) g.insert_edge(1, 7, 12) g.insert_edge(2, 3, 8) g.insert_edge(2, 8, 3) g.insert_edge(2, 5, 5) g.insert_edge(3, 4, 10) g.insert_edge(3, 5, 15) g.insert_edge(4, 5, 11) g.insert_edge(5, 6, 3) g.insert_edge(6, 7, 2) g.insert_edge(6, 8, 7) g.insert_edge(7, 8, 8) source = 0 k = 64 print(g.is_there_any_path(source, k))
输入
nodes = 9 g = Graph(nodes) g.insert_edge(0, 1, 5) g.insert_edge(0, 7, 9) g.insert_edge(1, 2, 9) g.insert_edge(1, 7, 12) g.insert_edge(2, 3, 8) g.insert_edge(2, 8, 3) g.insert_edge(2, 5, 5) g.insert_edge(3, 4, 10) g.insert_edge(3, 5, 15) g.insert_edge(4, 5, 11) g.insert_edge(5, 6, 3) g.insert_edge(6, 7, 2) g.insert_edge(6, 8, 7) g.insert_edge(7, 8, 8) source = 0 k = 64
输出
True
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

