編程內(nèi)容及要求：

編寫程序，實現(xiàn)輸入圖G，基于韋爾奇·鮑威爾法對圖G的結(jié)點進行著色，輸出對應(yīng)的一個正常著色。

正常著色輸出格式示例(設(shè)圖G的結(jié)點為v1, v2, v3，顏色用1, 2, 3等數(shù)字代表):

------------------

v1:1,v2:2,v3:3

------------------

韋爾奇·鮑威爾法：

1)? 將圖 G 中的結(jié)點按度數(shù)遞減的次序進行排列(相同度數(shù)的結(jié)點的排列隨意)。?

2)? 用第一種顏色，對第一點著色，并按排列次序?qū)εc前面結(jié)點不相鄰的每一點著同樣的顏色。?

3)? 用第二種顏色對尚未著色的點重復(fù)第2 步, 直到所有的點都著上顏色為止。?

程序設(shè)計簡要描述：

首先輸入一個結(jié)點數(shù)v，在int型二維數(shù)組matrix（初始化為0）里輸入圖的鄰接矩陣，再調(diào)用getdegree()函數(shù)，在這個函數(shù)里面將矩陣每一行的列數(shù)據(jù)相加得到每個結(jié)點的度數(shù)并存儲于一個二維數(shù)組a中，a有兩行并初始化為0，第一行用來存儲所有結(jié)點的度數(shù)，第二行準(zhǔn)備用來存儲相應(yīng)結(jié)點的著色。接著調(diào)用sort()函數(shù)，用一個一維數(shù)組as（初始化為0），運用循環(huán)將a數(shù)組的第一行復(fù)制到as數(shù)組中，運用冒泡排序的思想依次獲取結(jié)點度數(shù)從大到小的數(shù)組下標(biāo)并存儲于一維數(shù)組ascend中，在main()函數(shù)中借助ascend中的下標(biāo)使用韋爾奇·鮑威爾法進行著色，將著色數(shù)據(jù)存儲于a數(shù)組的第二行。最后運用文件操作將結(jié)果輸出到graph.txt中。

輸出的字符文件graph.txt內(nèi)容（粘貼）：

------------------

v1:1,v2:3,v3:2,v4:2,v5:1,v6:3,v7:3,v8:2

------------------

#include <iostream> #include <fstream> using namespace std; #define Maxsize 100 int v, color = 1; int matrix[Maxsize][Maxsize]; int a[2][Maxsize] = { 0 }; int ascend[Maxsize] = { 0 }; void getdegree(); void sort(); int main() {cout << "請輸入要著色的圖G結(jié)點數(shù)：" << endl;cin >> v;cout << "請輸入圖G的鄰接矩陣：" << endl;for (int i = 0; i < v; i++)for (int j = 0; j < v; j++)cin >> matrix[i][j];getdegree();sort();//借助ascend中的下標(biāo)使用韋爾奇·鮑威爾法進行著色，將著色數(shù)據(jù)存儲于a數(shù)組的第二行for (int i = 0; i < v; i++){if (a[1][ascend[i]] == 0){a[1][ascend[i]] = color;for (int j = 0; j < v; j++){if (matrix[ascend[i]][j] == 0){if (a[1][j] == 0)a[1][j] = color;}}color++;}}//運用文件操作將結(jié)果輸出到graph.txt中ofstream ofs;ofs.open("graph.txt", ios::out);ofs << "------------------" << endl;for (int i = 0; i < v; i++){ofs << "v" << i + 1 << ":" << a[1][i];if (i != v - 1)ofs << ",";}ofs << endl << "------------------" << endl;ofs.close();return 0; } //將矩陣每一行的列數(shù)據(jù)相加得到每個結(jié)點的度數(shù)并存儲于一個二維數(shù)組a中 //a有兩行并初始化為0，第一行用來存儲所有結(jié)點的度數(shù)，第二行準(zhǔn)備用來存儲相應(yīng)結(jié)點的著色。 void getdegree() {for (int i = 0; i < v; i++)for (int j = 0; j < v; j++)a[0][i] += matrix[i][j]; } //獲取結(jié)點度數(shù)從大到小的數(shù)組下標(biāo)并存儲于一維數(shù)組ascend中 void sort() {int flag = 0;int as[Maxsize] = { 0 };for (int i = 0; i < v; i++)as[i] = a[0][i];for (int i = 0; i < v; i++){int temp = 0;for (int j = 0; j < v; j++){if (as[j] > temp){temp = as[j];flag = j;}}ascend[i] = flag;as[flag] = 0;} }

總結(jié)

以上是生活随笔為你收集整理的基于实现韦尔奇·鲍威尔法对图进行着色的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。