#include?
#include?
#include
#define?Max?50
using?namespace?std;

class?Graph??//圖的類
{
public:
	int?n;//頂點
	int?e;//邊
????string?vex[Max];??//頂點信息
	int?Edge[Max][Max];//頂點與頂點之間的聯系
	Graph（int?n0int?e0）{n=n0;e=e0;}//構造函數
	void?Input（）;??//圖的輸入
	int?IsEdge（int?v1int?v2）;//判斷v1v2之間是否有邊
	int?check（string?a）;
};

class?color_greedy;
class?subset??//子集類
{
public:
	friend?class?color_greedy;?//char-greedy是其友元類
	int?*newclr;//指向子集所包含的各個結點序號
	int?n;????//子集中結點個數
	int?color;//該子集所賦給的顏色值

	subset（int?newcolor=0int?m=Max）;//構造函數
	~subset（）{delete?newclr;}//析構函數
};

class?color_greedy
{
public:
	Graph?g;//要著色的圖
	subset?*u;//子集集合
	int?*x;?//各結點的著色值向量
	int?n?;??//圖的結點個數
	int?m?;?//可選的m?種顏色
	color_greedy（int?n0int?m0int?e0）;//構造函數
	~color_greedy（）{delete?x;?delete?[]u;}//析構函數
	void?greedy（subset?&y?）;//貪心法找子集y中包含的結點
	void?Coloring?（）;//產生圖的著色方案
};
/*************************Graph.cpp*****************/
int?Graph::check（string?a）
{
	for（int?i=0;i		if（vex[i]==a）
			return?i;
	return?-1;
}
void?Graph::Input（）???//地圖的輸入
{
	ifstream?fin（“ChinaMapColoring.txt“）;
	if（!fin）
	{
		cerr<<“文件打開失敗“;
		exit（1）;	
	}
	cout<	system（“pause“）;
	system（“cls“）;
	cout<<“中國地圖共有有23個省、5個自治區、4個直轄市、2個特別行政區.........“<	for（int?i=0;i		fin>>vex[i];
	cout<<“這些省份分別是:“<	for（i=0;i	{
		cout<		if（（i+1）%7==0）
			cout<	}
	cout<	system（“pause“）;
	system（“cls“）;
	cout<	system（“pause“）;
	system（“cls“）;
	int?pq;
	string?ab;
	for（i=0;i		for（int?j=0;j			Edge[i][j]=0;

	cout<	cout<<“這些相鄰關系分別為:“<
	for（i=0;i	{
		fin>>a;
		fin>>b;
		p=check（a）;
		q=check（b）;
		Edge[p][q]=Edge[q][p]=1;//矩陣存儲
		cout<		if（（i+1）%3==0）
			cout<	}
	cout<	fin.close（）;
}
int?Graph::IsEdge（int?v1int?v2）
{
	if（Edge[v1][v2]>0）
		return?1;
	else?return?0;
}

/*******************************subset.cpp***********************/
subset::subset（int?newcolorint?m）
{
	n=m;
	if（n>0）
		newclr=new?int[n];
	else?
		newclr=0;
	color=newcolor;
}

/*****************************color_greedy.cpp********************/
color_greedy::color_greedy（int?n0int?m0int?e0）:g（n0e0）
{
	n=n0;
	m=m0;
	x=new?int[n];//創建x?向量
	for（int?i=0;i		x[i]=0;//初始化向量x
	u=new?subset[m];//創建m個子集
	g.Input（）;
}
void?color_greedy::greedy（subset?&y）
{
	int?vp=0q=1w;
	for（int?i=0;i		if（x[i]==0）
		{
			v=i;
			break;
		}
	y.newclr[0]=v;//將結點v加入新的顏色值子集
	x[v]=y.color;//將結點v賦給新的顏色值
	for（i=0;i	{
		if（x[i]==0）
		{
			v=i;//找圖中未著色的結點v
			p=q-1;//q為當前子集中包含的結點個數
			while（p>=0）
			{
				w=y.newclr[p];//取子集中一個結點w
				if（g.IsEdge（vw））break;//若v和w鄰接，則v不能賦給該新顏色值
				els

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2011-03-28?13:56??地圖著色\
?????目錄???????????0??2011-03-28?13:56??地圖著色\貪心法\
?????文件?????????908??2010-09-14?20:29??地圖著色\貪心法\ChinaMapColoring.txt
?????目錄???????????0??2011-03-28?13:56??地圖著色\貪心法\Debug\
?????文件???????91136??2010-09-16?14:17??地圖著色\貪心法\Debug\vc60.idb
?????文件??????110592??2010-09-16?14:17??地圖著色\貪心法\Debug\vc60.pdb
?????文件??????577619??2010-09-16?14:17??地圖著色\貪心法\Debug\圖著色初做.exe
?????文件??????829116??2010-09-16?14:17??地圖著色\貪心法\Debug\圖著色初做.ilk
?????文件??????297525??2010-09-16?14:17??地圖著色\貪心法\Debug\圖著色初做.obj
?????文件?????2165364??2010-09-15?19:30??地圖著色\貪心法\Debug\圖著色初做.pch
?????文件?????1156096??2010-09-16?14:17??地圖著色\貪心法\Debug\圖著色初做.pdb
?????文件????????4539??2010-09-16?14:17??地圖著色\貪心法\圖著色初做.cpp
?????文件????????3451??2010-09-16?14:17??地圖著色\貪心法\圖著色初做.dsp
?????文件?????????545??2010-09-16?14:18??地圖著色\貪心法\圖著色初做.dsw
?????文件???????50176??2010-09-16?14:18??地圖著色\貪心法\圖著色初做.ncb
?????文件???????48640??2010-09-16?14:18??地圖著色\貪心法\圖著色初做.opt
?????文件?????????766??2010-09-16?14:17??地圖著色\貪心法\圖著色初做.plg
?????目錄???????????0??2011-03-28?13:56??地圖著色\遞歸回溯法\
?????文件?????????908??2010-09-14?20:29??地圖著色\遞歸回溯法\ChinaMapColoring.txt
?????目錄???????????0??2011-03-28?13:56??地圖著色\遞歸回溯法\Debug\
?????文件???????82944??2010-09-17?19:59??地圖著色\遞歸回溯法\Debug\vc60.idb
?????文件??????118784??2010-09-15?22:38??地圖著色\遞歸回溯法\Debug\vc60.pdb
?????文件??????577623??2010-09-17?19:59??地圖著色\遞歸回溯法\Debug\圖著色初做.exe
?????文件??????828436??2010-09-17?19:59??地圖著色\遞歸回溯法\Debug\圖著色初做.ilk
?????文件??????294612??2010-09-17?19:59??地圖著色\遞歸回溯法\Debug\圖著色初做.obj
?????文件?????2165364??2010-09-15?19:26??地圖著色\遞歸回溯法\Debug\圖著色初做.pch
?????文件?????1156096??2010-09-15?22:38??地圖著色\遞歸回溯法\Debug\圖著色初做.pdb
?????文件????????3633??2010-09-15?22:24??地圖著色\遞歸回溯法\圖著色初做.cpp
?????文件????????3451??2010-09-17?19:59??地圖著色\遞歸回溯法\圖著色初做.dsp
?????文件?????????545??2010-09-17?20:08??地圖著色\遞歸回溯法\圖著色初做.dsw
?????文件???????41984??2010-09-17?20:08??地圖著色\遞歸回溯法\圖著色初做.ncb
............此處省略2個文件信息