[数据结构与算法]【数据结构基础C++】图论应用-用四种颜色对地图上的国家涂色

思想

1. 存储：国家之间只有相邻和不相邻两种关系。把国家看作顶点，用边表示两个国家相邻。考虑到每个国家都要考虑相邻关系，用邻接矩阵存储。
2. 四种色号编号为1,2,3,4；国家序号用 0…n 表示；
3. 用色号循环方式，给国家涂色。
4. 在涂色前，先判断与当前国家相邻的国家的涂色情况：若与之相邻的国家的色号与当前国家色号相同，则用下一个色号涂色；
5. 核心函数：graphColor（int k）；isSafe（int k，int color）； 掌握这两个函数就可以了！
   
   以这几个省份为例：
   
   抽象成顶点与边的关系：
   

代码

#pragma once
#include <iostream>
#include <cassert>
#include "DenseGraph.h"

using namespace std;

class colorMap {
private:
	int colorNum = 4;					//填色个数,默认四个颜色
	int* colored;
	DenseGraph& G;
	vector<vector<bool>> vec;

public:
	colorMap(DenseGraph& graph):G(graph) {
		//初始化填色数组,刚开始都没填色，初始化为0
		colored = new int[G.V()];
		//获取图的邻接矩阵
		this->vec = G.getMatrix();
		for (int i = 0; i <G.V(); ++i) {
			colored[i] = 0;	
		}

		//调用填色数组，为了简单，从0开始着色
		graphColor(0);
	}
	~colorMap() {
		delete[] colored;
		
	}
	//填色数组函数,为了简单，从0开始着色
	void graphColor(int k) {
		//颜色 1 2 3 4,每一个国家都从1号色开始填，成功，记录在colored数组
		for (int c = 1; c <= colorNum; ++c) {
			//
			if (isSafe(k, c)) {
				colored[k] = c;
				if (k + 1 < G.V())
					//若下一个顶点小于顶点总数，继续下一个顶点的着色
					graphColor(k + 1);
				else
					printColored(); return;
			}
		}
	}

	bool isSafe(int k, int c) {
		for (int i = 0; i < G.V(); ++i) {
			//若与k相邻的节点的着色与k相同，返回false，不能用这个色
			if (vec[k][i] == true && c == colored[i])
				return false;
		}
		return true;
	}
	//打印着色数组
	void printColored() {
		for (int i = 0; i < G.V();++i) {
			cout << i << ": " << colored[i] << endl;
		}
	}
};

测试

1. 顶点与边的信息存储在 map.txt 中；
2. 初始化无向无权图；
3. 引入着色头文件，涂色；

#include <iostream>
#include <fstream>
#include <string>
#include "DenseGraph.h"
#include "colorMap.h"
using namespace std;

int main() {
	string filename1 = "map.txt";
	DenseGraph DG(10, false);
	readGraph<DenseGraph> readDenseGraph(DG, filename1);
	DG.show();
	colorMap CM(DG);
	
	system("pause");
	return 0;
}