โปรแกรม C++ ทำ Greedy Coloring บนกราฟ

บทนำ

นี่คือโปรแกรม C++ ทำ Greedy Coloring บนกราฟ

อัลกอริทึม

Begin
  รับจำนวนโหนดและเส้นเชื่อม
  สร้างฟังก์ชัน greedyColoring() กำหนดสีให้โหนด:
    A) กำหนดสีแรกให้โหนดแรก
    B) เริ่มต้นโหนดที่เหลือ
    C) ประกาศอาร์เรย์ชั่วคราวเก็บสีที่ว่าง
    D) กำหนดสีให้โหนดที่เหลือ
  พิมพ์คำตอบ
End

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

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

int n, e, i, j;
vector<vector<int> > g;
vector<int> color;
bool visit[1001];

void greedyColoring() {
    color[0] = 0;
    for (i = 1; i < n; i++)
        color[i] = -1;
    bool unuse[n];
    for (i = 0; i < n; i++)
        unuse[i] = 0;
    for (i = 1; i < n; i++) {
        for (j = 0; j < g[i].size(); j++)
            if (color[g[i][j]] != -1)
                unuse[color[g[i][j]]] = true;
        int cr;
        for (cr = 0; cr < n; cr++)
            if (unuse[cr] == false)
                break;
        color[i] = cr;
        for (j = 0; j < g[i].size(); j++)
            if (color[g[i][j]] != -1)
                unuse[color[g[i][j]]] = false;
    }
}

int main() {
    int a, b;
    cout << "Enter number of vertices and edges respectively:";
    cin >> n >> e;
    cout << "\n";
    g.resize(n);
    color.resize(n);
    memset(visit, 0, sizeof(visit));
    for (i = 0; i < e; i++) {
        cout << "\nEnter edge vertices of edge " << i + 1 << " :";
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    greedyColoring();
    for (i = 0; i < n; i++)
        cout << "Vertex " << i + 1 << " is coloured with " << color[i] + 1 << "\n";
    return 0;
}

ผลลัพธ์

Enter number of vertices and edges respectively: 7 6
Enter edge vertices of edge 1 : 4 5
Enter edge vertices of edge 2 : 2 3
Enter edge vertices of edge 3 : 1 1
Enter edge vertices of edge 4 : 1 4
Enter edge vertices of edge 5 : 6 7
Enter edge vertices of edge 6 : 2 2
Vertex 1 is coloured with 1
Vertex 2 is coloured with 1
Vertex 3 is coloured with 2
Vertex 4 is coloured with 2
Vertex 5 is coloured with 1
Vertex 6 is coloured with 1
Vertex 7 is coloured with 2