数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：判断无向图中顶点是否存在更低成本路径
假设我们给定一个加权无向图。我们必须实现一个函数`query`，该函数接收两个顶点和一个成本“限制”作为输入，并检查是否存在比输入成本更低的路径。如果存在路径，则返回`true`；否则，返回`false`。
因此，如果输入如下：
查询为 (0, 2, 10), (3, 1, 30), (4, 3, 30)。
则输出为：
False True True
第一个查询的结果为`False`，因为从顶点0到顶点2不存在成本为10的路径。
第二个查询的结果为`True`，因为从顶点3到顶点1存在成本为10的路径，小于30。
第三个查询的结果为`True`，因为从顶点4到顶点3存在成本为30的路径，等于30。
为了解决这个问题，我们将遵循以下步骤：
weights := 包含图中不同权重的列表
connections := 包含权重连接的列表
定义函数`query()`。它将接收p、q、limit。
index := weights中limit可以插入到左侧并保持排序顺序的位置。
如果index等于0，则
返回`False`
如果connections[index-1, p]等于connections[index-1, q]，则返回`True`
示例
让我们看看下面的实现以更好地理解：
import bisect
class Solution(object):
def __init__(self, n, edgeList):
def find(node):
if parent[node]!=node:
parent[node] = find(parent[node])
return parent[node]
def union(x,y):
parent[find(y)] = find(x)
return
parent = {i:i for i in range(n)}
edgeList.sort(key = lambda x:x[2])
self.connections = []
self.weights = []
for index,(i,j,weight) in enumerate(edgeList):
union(i,j)
if index!=len(edgeList)-1 and weight == edgeList[index+1][2]:
continue
self.weights.append(weight)
self.connections.append([find(i) for i in parent])
def query(self, p, q, limit):
index = bisect.bisect_left(self.weights,limit)
if index==0:
return False
return self.connections[index-1][p] == self.connections[index-1][q]
ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))输入
ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]]) print(ob.query(0, 2, 10)) print(ob.query(3, 1, 30)) print(ob.query(4, 3, 30))
输出
False True True
更新于：2021年10月8日
123 次浏览
广告