สมมติว่าเราได้รับกราฟที่ถ่วงน้ำหนักและไม่มีทิศทาง เราต้องใช้แบบสอบถามฟังก์ชันที่ใช้จุดยอดสองจุดและ 'จำกัด' ต้นทุนเป็นอินพุต และตรวจสอบว่ามีเส้นทางต้นทุนที่ต่ำกว่าต้นทุนที่ระบุเป็นอินพุตหรือไม่ เราคืนค่า จริง หากมีเส้นทางอยู่ หรือคืนค่าเท็จ
ดังนั้นหากอินพุตเป็นแบบ
และข้อความค้นหาคือ (0, 2, 10), (3, 1, 30), (4, 3, 30)
แล้วผลลัพธ์ที่ได้จะเป็น
FalseTrueTrue
ผลลัพธ์ของการค้นหาแรกเป็น False เนื่องจากไม่มีเส้นทางระหว่างจุดยอด 0 ถึง 2 ของราคา 10
ผลลัพธ์ของแบบสอบถามที่สองเป็นจริงเนื่องจากมีเส้นทางระหว่างจุดยอด 3 ถึง 1 ของต้นทุน 10 ซึ่งน้อยกว่า 30
ผลลัพธ์ของแบบสอบถามที่สามเป็นจริงเนื่องจากมีเส้นทางระหว่างจุดยอด 4 ถึง 3 ของราคา 30 ซึ่งเท่ากับ 30
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
weights :=รายการน้ำหนักต่างๆ ในกราฟ
-
การเชื่อมต่อ :=รายการที่มีการเชื่อมต่อสำหรับตุ้มน้ำหนัก
-
กำหนดฟังก์ชัน query() นี่จะใช้เวลา p, q, จำกัด
-
ดัชนี :=ตำแหน่งในน้ำหนักที่นี่ จำกัด สามารถแทรกทางด้านซ้ายของการรักษาลำดับการเรียงลำดับ
-
ถ้าดัชนีเท่ากับ 0 แล้ว
-
คืนค่าเท็จ
-
-
คืนค่าเป็น True หากการเชื่อมต่อ[index-1, p] เหมือนกับการเชื่อมต่อ[index-1, q]
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
นำเข้า bisectclass Solution(object):def __init__(self, n, edgeList):def find(node):if parent[node]!=node:parent[node] =find(parent[node]) return parent[ โหนด] 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 =[] สำหรับ index,(i,j,weight) ใน enumerate(edgeList):union(i,j) if index!=len(edgeList)-1 and weight ==edgeList [index+1][2]:ทำต่อ 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) ถ้า 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]])พิมพ์( ob.query(0, 2, 10)) พิมพ์ (ob.query(3, 1, 30)) พิมพ์ (ob. ข้อความค้นหา(4, 3, 30)) อินพุต
ob =โซลูชัน (5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])พิมพ์(ob.query(0, 2, 10))พิมพ์(ob.query(3, 1, 30))พิมพ์(ob.query(4, 3, 30))ผลลัพธ์
FalseTrueTrue
