สมมติว่าเรามีกราฟ เราก็มีจุดยอดต้นทางและตัวเลข k ด้วย k คือความยาวเส้นทางของกราฟระหว่างต้นทางไปยังปลายทาง เราต้องตรวจสอบว่าเราสามารถหาเส้นทางธรรมดา (ไม่มีวงจร) ได้หรือไม่ โดยเริ่มจากต้นทางและสิ้นสุดที่จุดยอดอื่น (เป็นปลายทาง) กราฟแสดงดังต่อไปนี้ -
ดังนั้น ถ้าอินพุตเป็นเหมือน Source =0, k =64 เอาต์พุตจะเป็น True เนื่องจากมีเส้นทางง่ายๆ 0 ถึง 7 ถึง 1 ถึง 2 ถึง 8 ถึง 6 ถึง 5 ถึง 3 ถึง 4 ความยาวของเส้นทางนี้จะมีทั้งหมด ระยะทาง 68 ซึ่งมากกว่า 64.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดกราฟโดยใช้ adjacency matrix adj ของโหนดคำสั่ง x โหนดและเติมด้วยต้นทุนที่ขอบ
-
กำหนดฟังก์ชัน Solve() นี่จะใช้ source, k, path
-
ถ้า k <=0 แล้ว
-
คืนค่า True
-
-
ผม :=0
-
ในขณะที่ฉันไม่เหมือนกับขนาดของ adj[source] ให้ทำ
-
v :=adj[แหล่งที่มา, ผม, 0]
-
w :=adj[ที่มา, ผม, 1]
-
ผม :=ผม + 1
-
ถ้า path[v] เป็นจริง
-
ไปทำซ้ำต่อไป
-
-
ถ้า w>=k แล้ว
-
คืนค่า True
-
-
เส้นทาง[v] :=จริง
-
ถ้าการแก้ (v, k-w, เส้นทาง) เป็นจริงแล้ว
-
คืนค่า True
-
-
เส้นทาง[v] :=เท็จ
-
-
คืนค่าเท็จ
-
จากวิธีหลัก ให้ทำดังนี้ −
-
path :=รายการขนาดเท่ากับโหนด จากนั้นกรอกค่าเท็จ
-
เส้นทาง[แหล่งที่มา] :=1
-
คืนค่าแก้ (ต้นทาง, k, เส้นทาง)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
