นี่คือโปรแกรม C++ ที่สาธิตการนำปัญหา 4 สี (4-Color Problem) มาใช้งาน
อัลกอริทึม
เริ่มต้น พัฒนาฟังก์ชัน issafe() เพื่อตรวจสอบว่าการกำหนดสีปัจจุบัน ปลอดภัยสำหรับจุด v หรือไม่ คือ ตรวจสอบว่าขอบมีอยู่หรือไม่ ถ้ามีอยู่ ตรวจสอบต่อว่าสีที่จะเติมในจุดใหม่ ถูกใช้โดยจุดติดกันแล้วหรือไม่ จบ เริ่มต้น ฟังก์ชัน graphColoringtil(bool graph[V][V], int m, int col[], int v) แก้ปัญหาการระบายสี 4 สี: ที่นี่ g[V][V] = อาร์เรย์ 2 มิติ ที่ V คือจำนวนจุดในกราฟ m = จำนวนสีสูงสุดที่ใช้ได้ col[] = อาร์เรย์สีที่ควรมีตัวเลข 1 ถึง m ถ้า v == V คืนค่า true สำหรับ c = 1 ถึง m ถ้า (isSafe(v, g, col, c)) col[v] = c ถ้า (graphColoringtil (g, k, col, v+1) == true) คืนค่า true col[v] = 0 คืนค่า false จบ เริ่มต้น ฟังก์ชัน graphColor(): ใช้ graphColoringUtil() หลักในการแก้ปัญหา คืนค่า false ถ้าไม่สามารถกำหนด m สีได้ มิฉะนั้น คืนค่า true จบ
ตัวอย่างโค้ด
#include <iostream> #include <cstdio> #define V 5 using namespace std; bool isSafe (int v, bool graph[V][V], int col[], int C) { for (int i = 0; i < V; i++) if (graph[v][i] && C == col[i]) return false; return true; } bool graphColoringtil(bool g[V][V], int k, int col[], int v) { if (v == V) //ถ้าจุดทั้งหมดถูกกำหนดสีแล้ว return true; for (int c = 1; c <= k; c++) { //พิจารณาจุด v และลองสีต่างๆ if (isSafe(v, g, col, c)) { //ตรวจสอบว่าการกำหนดสี c ให้ v ถูกต้องหรือไม่ col[v] = c; if (graphColoringtil (g, k, col, v+1) == true) //เรียกซ้ำเพื่อกำหนดสีให้จุดที่เหลือ return true; col[v] = 0; //ถ้าการกำหนดสี c ไนำไปสู่คำตอบ ให้ลบออก } } return false; } void solution(int color[]) { cout<<"The assigned colors are: \n"; for (int i = 0; i < V; i++) cout<<color[i]; cout<<"\n"; } bool graphColor(bool graph[V][V], int k) { int *color = new int[V]; //กำหนดค่าสีทั้งหมดเป็น 0 เริ่มต้น for (int i = 0; i < V; i++) color[i] = 0; if (graphColoringtil(graph, k, color, 0) == false) { cout<<"Solution does not exist"; return false; } solution(color); return true; } int main() { bool g[V][V] = { {0, 0, 1, 0,1}, {1, 1, 1, 0,0}, {1, 1, 0, 0,1}, {0, 1, 1, 0,0} }; int k= 4; graphColor(g, k); return 0; }
ผลลัพธ์
The assigned colors are: 1 2 3 1 1
