資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告