Chương trình tìm hiểu xem một đỉnh trong đồ thị vô hướng có đường dẫn chi phí thấp hơn bằng Python hay không

Giả sử, chúng ta được cho một đồ thị có trọng số, vô hướng. Chúng ta phải triển khai một truy vấn hàm lấy hai đỉnh và 'giới hạn' chi phí làm đầu vào và kiểm tra xem có tồn tại một đường dẫn chi phí thấp hơn chi phí đã cho làm đầu vào hay không. Chúng tôi trả về true nếu tồn tại một đường dẫn hoặc nếu không, chúng tôi trả về false.

Vì vậy, nếu đầu vào giống như

và các truy vấn là (0, 2, 10), (3, 1, 30), (4, 3, 30).

thì đầu ra sẽ là

 FalseTrueTrue 

Kết quả của truy vấn đầu tiên là Sai vì không có đường dẫn nào giữa đỉnh 0 đến 2 của chi phí 10.

Kết quả của truy vấn thứ hai là True vì có một đường dẫn từ đỉnh 3 đến đỉnh 1 của giá 10, nhỏ hơn 30.

Kết quả của truy vấn thứ ba là True vì có một đường đi giữa đỉnh 4 đến đỉnh 3 của giá trị 30, bằng 30.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• weights:=danh sách chứa các trọng số khác nhau trong biểu đồ

• kết nối:=một danh sách chứa các kết nối cho các trọng số

• Xác định truy vấn hàm (). Điều này sẽ mất p, q, giới hạn

  • index:=vị trí tính theo trọng số giới hạn ở đây có thể được chèn vào bên trái của việc duy trì thứ tự đã sắp xếp

  • nếu chỉ mục giống 0, thì

    • trả về Sai

  • trả về True nếu các kết nối [index-1, p] giống với các kết nối [index-1, q]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

 import bisectclass Giải pháp (đối tượng):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. truy vấn (4, 3, 30)) 

Đầu vào

 ob =Lời giải (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))  
 Đầu ra 
 
 FalseTrueTrue