ตรวจสอบว่ามี Path ยาวกว่า k จาก Source ในกราฟ (Python)

โจทย์: กราฟไม่มีทิศทาง กำหนด source vertex และ k หาว่ามี simple path (ไม่ซ้ำโหนด) จาก source ยาว ≥ k หรือไม่

ตัวอย่าง: กราฟ 9 โหนด, source=0, k=64 → มี path 0-7-1-2-8-6-5-3-4 ความยาว 68 ≥ 64 → True

อัลกอริทึม DFS + Backtracking

1. DFS จาก source พร้อมเก็บ visited path
2. ถ้า edge weight ≥ k ที่เหลือ → คืน True ทันที (pruning)
3. วนลูปเพื่อนบ้าน: ถ้ายังไม่ visited → mark visited, recurse ด้วย k - weight
4. Backtrack: unmark visited
5. เจอ path ใด path หนึ่งที่ยาวพอ → True

ตัวอย่างโค้ด

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for _ 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
        for v, w in self.adj[source]:
            if path[v]:
                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] = True
        return self.solve(source, k, path)

# สร้างกราฟตัวอย่าง
nodes = 9
g = Graph(nodes)
edges = [(0,1,5),(0,7,9),(1,2,9),(1,7,12),(2,3,8),(2,8,3),(2,5,5),
         (3,4,10),(3,5,15),(4,5,11),(5,6,3),(6,7,2),(6,8,7),(7,8,8)]
for u,v,w in edges:
    g.insert_edge(u, v, w)

print(g.is_there_any_path(0, 64))  # True

ผลลัพธ์

True

สรุป: DFS backtracking O(V+E) worst-case แต่ pruning ด้วย w ≥ k ช่วยลดการค้นหา ใช้ได้กับกราฟขนาดเล็ก-กลาง