? ? 地圖染色問題的實質就是用深搜去一一枚舉，然后得到所有的染色方案。

? ? 下面這個例子就是用鄰接矩陣實現的：

#include <iostream>using namespace std; int **a;//鄰接矩陣 int *b;//每個方案的具體染色細節(jié) int total = 0;//總的染色方案數量 int n;//地圖中的國家數量void readData();//讀取數據 void dfs(int x);//深搜 void del();//釋放內存void readData() {cin >> n;a = new int*[n + 1];for(int i = 0 ; i < n + 1 ; i++){a[i] = new int[n + 1];}b = new int[n + 1];for(int i = 1; i < n + 1; i++){for(int j = 1; j < n + 1; j++){cin >> a[i][j];}} }void dfs(int t) {if(t > n) //染色方案+1{total++;for(int i = 1; i <= n; i++){cout << b[i] << " ";}cout << endl;return;}for(int i = 1; i <= 4; i++)//四種顏色{bool xxx = true;for(int j = 1; j < t; j++){if(a[j][t] == 1 && b[j] == i)xxx = false;}if(xxx == true)//可以染色{b[t] = i;dfs(t + 1);//繼續(xù)深搜}} }void del(){delete[]b;for(int i = 0 ; i < n + 1 ; i++){delete[]a[i];}}int main() {readData();dfs(1);del();cout << total << endl;return 0; }

總結

以上是生活随笔為你收集整理的地图染色问题——四色问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。