ตรวจสอบว่ากราฟแบบไม่มีทิศทางมีเซตอิสระขนาดที่กำหนดหรือไม่ใน C++

แนวคิด

สำหรับกราฟแบบไม่มีทิศทางที่กำหนด ให้ตรวจสอบว่ามีเซตอิสระ (independent set) ขนาด l หรือไม่ หากมีให้พิมพ์ 'Yes' มิฉะนั้นพิมพ์ 'No' เซตอิสระในกราฟหมายถึงเซตของจุดยอดที่ไม่มีการเชื่อมต่อโดยตรงระหว่างกัน

อินพุต

L = 4, graph = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 1, 0], [0, 0, 1, 0, 1]]

เอาต์พุต

Yes

กราฟข้างต้นมีเซตอิสระขนาด 4 (จุดยอด 0, 1, 3, 4 ไม่ได้เชื่อมต่อโดยตรงกัน) ดังนั้นผลลัพธ์คือ 'Yes'

อินพุต

L = 4, graph = [[1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 1, 0], [0, 0, 1, 0, 1]]

เอาต์พุต

No

จากแผนภาพ กราฟนี้ไม่มีเซตอิสระขนาด 4 ดังนั้นผลลัพธ์คือ 'No'

วิธีการ

• เริ่มต้นตัวแปร sol ด้วยค่า boolean false
• หาชุดจุดยอดที่เป็นไปได้ทั้งหมดขนาด L จากกราฟที่กำหนด
• หากพบเซตอิสระขนาด l ให้เปลี่ยนค่า sol เป็น true และคืนค่า
• มิฉะนั้น ตรวจสอบชุดอื่นๆ ที่เป็นไปได้ต่อไป
• สุดท้าย หาก sol เป็น true ให้พิมพ์ 'Yes' มิฉะนั้นพิมพ์ 'No'

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

// โค้ด C++ ตรวจสอบว่ากราฟที่กำหนดมีเซตอิสระขนาด k หรือไม่
#include <bits/stdc++.h>
using namespace std;

// โพรโทไทป์ฟังก์ชัน
bool check1(int[][5], vector<int>&, int);

// ฟังก์ชันสร้างเซตขนาด l ที่กำหนด
bool func(int graph1[][5], vector<int>& arr1, int l, int index1, bool sol1[]) {
    // ตรวจสอบว่าเซตที่เลือกเป็นอิสระหรือไม่
    // ใช้เปลี่ยนค่า sol เป็น true และคืนค่าหากเป็นอิสระ
    if (l == 0) {
        if (check1(graph1, arr1, arr1.size())) {
            sol1[0] = true;
            return true;
        }
    } else {
        // เซตขนาด l สามารถสร้างได้แม้ไม่รวมจุดยอดที่ดัชนีปัจจุบัน
        if (index1 >= l) {
            vector<int> newvec(arr1.begin(), arr1.end());
            newvec.push_back(index1);
            return (func(graph1, newvec, l - 1, index1 - 1, sol1) or
                    func(graph1, arr1, l, index1 - 1, sol1));
        }
        // เซตขนาด l ไม่สามารถสร้างได้หากไม่รวมจุดยอดที่ดัชนีปัจจุบัน
        else {
            arr1.push_back(index1);
            return func(graph1, arr1, l - 1, index1 - 1, sol1);
        }
    }
}

// ฟังก์ชันตรวจสอบว่าเซตที่กำหนดเป็นอิสระหรือไม่
// arr --> เซตขนาด l (มีดัชนีของจุดยอดที่รวม)
bool check1(int graph1[][5], vector<int>& arr1, int n1) {
    // ตรวจสอบว่าแต่ละจุดยอดเชื่อมต่อกับจุดยอดอื่นในเซตหรือไม่
    for (int i = 0; i < n1; i++)
        for (int j = i + 1; j < n1; j++)
            if (graph1[arr1[i]][arr1[j]] == 1)
                return false;
    return true;
}

// โค้ดหลัก
int main() {
    int graph1[][5] = {{1, 0, 1, 0, 0}, {0, 1, 1, 0, 0}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 0}, {0, 0, 1, 0, 1}};
    int l = 4;
    vector<int> arr1; // เซตว่าง
    bool sol1[] = {false};
    int n1 = sizeof(graph1) / sizeof(graph1[0]);
    func(graph1, arr1, l, n1 - 1, sol1);
    if (sol1[0])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

เอาต์พุต

Yes