ตรวจสอบว่ามี Path ยาวกว่า k จาก Source ในกราฟ C++

แนวคิด

กำหนดกราฟ, จุดยึด (source vertex), และจำนวน k (ความยาว path) ตรวจสอบว่ามี Simple Path (ไม่มี Cycle) เริ่มจาก source จบที่โหนดไหนก็ได้ ที่มีความยาว > k หรือไม่

ตัวอย่าง

กราฟ 9 โหนด (ดูภาพ)
Source s = 0, k = 64 → True (มี path 0→7→1→2→8→6→5→3→4 ความยาว 68)
Source s = 0, k = 70 → False (Longest path = 69)

เหตุผลที่ BFS/DFS ธรรมดาไม่ได้

เลือก Edge หนักสุดทีละขั้น (Greedy) ไม่ได้ เพราะ Edgeเบาๆ อาจนำไปสู่ Path ยาวกว่าได้

แนวทาง: Backtracking

1. เริ่มจาก Source, สำรวจทุก Path
2. เก็บระยะทางสะสมจาก Source
3. ถ้าระยะทาง > k → คืนค่า True
4. ถ้า Path ไหนไม่ได้ผล → Backtrack (ย้อนกลับ)
5. ใช้ Boolean Array path[] ติดตามโหนดใน Path ปัจจุบัน ป้องกัน Cycle

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

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> iPair;

class Graph {
    int V1;
    list<iPair> *adj1;
    bool pathMoreThanKUtil(int src1, int k, vector<bool>& path1);
public:
    Graph(int V1);
    void addEdge(int u1, int v1, int w1);
    bool pathMoreThanK(int src1, int k);
};

bool Graph::pathMoreThanK(int src1, int k) {
    vector<bool> path1(V1, false);
    path1[src1] = true;
    return pathMoreThanKUtil(src1, k, path1);
}

bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>& path1) {
    if (k <= 0) return true;
    
    for (auto i = adj1[src1].begin(); i != adj1[src1].end(); ++i) {
        int v1 = (*i).first;
        int w1 = (*i).second;
        
        if (path1[v1]) continue;  // Cycle
        if (w1 >= k) return true;  // Edge เองก็เกิน k แล้ว
        
        path1[v1] = true;
        if (pathMoreThanKUtil(v1, k - w1, path1))
            return true;
        path1[v1] = false;  // Backtrack
    }
    return false;
}

Graph::Graph(int V1) {
    this->V1 = V1;
    adj1 = new list<iPair>[V1];
}

void Graph::addEdge(int u1, int v1, int w1) {
    adj1[u1].push_back(make_pair(v1, w1));
    adj1[v1].push_back(make_pair(u1, w1));
}

int main() {
    int V1 = 9;
    Graph g(V1);
    
    g.addEdge(0, 1, 5);  g.addEdge(0, 7, 9);
    g.addEdge(1, 2, 9);  g.addEdge(1, 7, 12);
    g.addEdge(2, 3, 8);  g.addEdge(2, 8, 3);  g.addEdge(2, 5, 10);
    g.addEdge(3, 4, 10); g.addEdge(3, 5, 15);
    g.addEdge(4, 5, 11); g.addEdge(5, 6, 3);
    g.addEdge(6, 7, 2);  g.addEdge(6, 8, 7);
    g.addEdge(7, 8, 8);
    
    int src1 = 0;
    int k = 70;
    g.pathMoreThanK(src1, k) ? cout << "Yes\n" : cout << "No\n";
    
    k = 68;
    g.pathMoreThanK(src1, k) ? cout << "Yes\n" : cout << "No\n";
    
    return 0;
}

ผลลัพธ์

No
Yes