連通圖著色問題

1、沈陽航空航天大學(xué)課課 程程 設(shè)設(shè) 計計 報報 告告課程設(shè)計名稱：軟件綜合課程設(shè)計課程設(shè)計題目：連通圖著色問題院（系）：計算機學(xué)院專 業(yè)：計算機科學(xué)與技術(shù)班 級：7401104學(xué) 號：200704011110姓 名：武 林指導(dǎo)教師：劉香芹沈陽航空航天大學(xué)課程設(shè)計報告 目目 錄錄1 需求分析需求分析.21.1 題目的內(nèi)容與要求.21.11 題目的內(nèi)容.21.12 題目的要求.21.2 題目理解與程序解讀.22 總體設(shè)計總體設(shè)計.42.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計.42.2 數(shù)據(jù)結(jié)構(gòu)類型與函數(shù).43 詳細設(shè)計詳細設(shè)計.63.1 子函數(shù)流程圖.63.1.1 memset_子函數(shù).63.1.2sort 子函數(shù).73

2、.1.3 brush_sort 子函數(shù) .83.2 主程序流程圖.94 調(diào)試分析調(diào)試分析.104.1 調(diào)試時遇到的問題.104.2 解決方案.104.3 調(diào)試結(jié)果及說明.11參考文獻參考文獻.12源程序（清單）源程序（清單）.13沈陽航空航天大學(xué)課程設(shè)計報告 11 需求分析需求分析1.11.1 題目的內(nèi)容與要求題目的內(nèi)容與要求1.111.11 題目的內(nèi)容題目的內(nèi)容輸入一個無向圖到適當(dāng)?shù)拇鎯Y(jié)構(gòu)中，給圖上的每一個結(jié)點標(biāo)記一種顏色，在保證任何相鄰結(jié)點顏色不同的同時，求解出該圖所需要的最少顏色數(shù)，并給出每個結(jié)點的具體顏色。1.121.12 題目的要求題目的要求1）完成系統(tǒng)需求分析；2）開發(fā)工具可以選

3、擇 C 語言或面向?qū)ο蟮?C+等；3）界面友好，操作方便；4）按照課程設(shè)計規(guī)范書寫課程設(shè)計報告。1.21.2 題目理解題目理解與程序解讀與程序解讀本次課設(shè)與離散數(shù)學(xué)當(dāng)中圖的部分有密切的聯(lián)系，連通圖的著色問題，涉及到圖的連通性和圖的著色問題。當(dāng)圖的結(jié)點之間存在通路，則此圖是連通的，在此基礎(chǔ)之上對他進行著色。重要之處在于每個進店標(biāo)記一種顏色，但要求的是相鄰的結(jié)點要著上不同的顏色，要求所使用的顏色數(shù)最少即是所要求的。解決此題的算法是韋爾奇.鮑威爾的著色理論，算法如下：（1）將圖的結(jié)點按照度數(shù)的遞減順序進行排列， （這種排列可能不是唯一的，因為有些點有相同的度數(shù)） 。（2）用第一種顏色對第一個結(jié)點進行

4、著色，并且按排列次序，對于前面著色點不相鄰的每一個結(jié)點著上同樣的顏色。（3）用第二種顏色對尚未著色的點重復(fù)第二個步驟，用第三種顏色繼續(xù)這沈陽航空航天大學(xué)課程設(shè)計報告 2種做法，直到所有的點全部著上色為止。 所以源程序就是對韋爾奇鮑威爾算法演示。首先輸入結(jié)點個數(shù)和邊的個數(shù)，結(jié)點結(jié)構(gòu)體內(nèi)包含結(jié)點編號，度數(shù)，結(jié)點的顏色和狀態(tài)。邊的結(jié)構(gòu)體當(dāng)中包含結(jié)點結(jié)構(gòu)體變量，用來指示邊起始節(jié)點和終止結(jié)點，同時還包含邊的編號。 對輸入的圖用關(guān)聯(lián)矩陣來表示，對著色的顏色用整型的數(shù)字來表示，所以我們規(guī)定數(shù)字 15 分別表示為紅色，黃色，藍色，綠色和黑色。 初始化顏色為紅色，即是為數(shù)字 1.顏色個數(shù)變量初始化為 0 個。沈

5、陽航空航天大學(xué)課程設(shè)計報告 32 總體設(shè)計總體設(shè)計2.12.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計結(jié)點和邊分別用結(jié)構(gòu)體來存儲，結(jié)點的結(jié)構(gòu)體為： typedef struct Node/結(jié)點int v;int deg;int color;bool flag;Node;其中 v 標(biāo)示結(jié)點的編號，deg 標(biāo)示每個結(jié)點的度數(shù)，color 標(biāo)示對每個結(jié)點著上的顏色，flag 標(biāo)示此時結(jié)點的狀態(tài)。這里我們申請最多可以輸入 50 個結(jié)點的空間，Node50。邊的結(jié)構(gòu)體為：typedef struct Edgeint e0;Node e1;Node e2;Edge;這里 e0 標(biāo)示邊的編號，e1 和 e2 則代表邊的起

6、始節(jié)點和終止結(jié)點。這里我們也申請了最多 50 條邊的空間，Edge50。對每個結(jié)點的度數(shù)進行排序，呈遞減順序，將結(jié)點的編號按排好的順序存放到數(shù)組 downnotem中，這里的 m 表示輸入結(jié)點個數(shù)的變量。從數(shù)組 downnotem中的第一個元素開始，根據(jù)韋爾奇鮑威爾算法對圖進行著色，最后確定著色的個數(shù)。2.22.2 數(shù)據(jù)結(jié)構(gòu)類型與函數(shù)數(shù)據(jù)結(jié)構(gòu)類型與函數(shù)函數(shù)名稱函數(shù)原型功能描述mainvoid main(void);系統(tǒng)主程序沈陽航空航天大學(xué)課程設(shè)計報告 4initevoid inite(int m,int n);初始化無相連通圖memset_void memset_(int m,int n)；

7、求出關(guān)聯(lián)矩陣以及各點的度數(shù)sortvoid sort(int m,int n); 對度數(shù)進行排序brush_colorvoid brush_color(int m,int n); 進行著色表表 2.12.1 函數(shù)列表函數(shù)列表沈陽航空航天大學(xué)課程設(shè)計報告 53 詳細設(shè)計詳細設(shè)計3.13.1 子函數(shù)流程圖子函數(shù)流程圖3.1.13.1.1 memset_memset_子函數(shù)子函數(shù)此部分為求關(guān)聯(lián)矩陣表示，以及求出每個結(jié)點相應(yīng)的度數(shù)。開始初始化關(guān)聯(lián)矩陣數(shù)組從第一個結(jié)點開始尋找相鄰結(jié)點對所有邊循環(huán)尋找如果此結(jié)點的編號與邊的起始節(jié)點或終止結(jié)點相同關(guān)聯(lián)矩陣數(shù)組相應(yīng)位置置1，并且此結(jié)點的度數(shù)加1 判斷下一條邊是

8、否為最后一條邊判斷下一個結(jié)點是否為最后一個結(jié)點顯示關(guān)聯(lián)矩陣數(shù)組，各點的度數(shù)結(jié)束NYYYNN圖 3.1 memset_函數(shù)沈陽航空航天大學(xué)課程設(shè)計報告 63.1.2sort3.1.2sort 子函數(shù)子函數(shù)此部分是將各個結(jié)點的度數(shù)按遞減的順序進行排列。開始初始化數(shù)組downnote以第一個結(jié)點為基準點如果基準點的度數(shù)小于第i個結(jié)點的度數(shù)，并且它的狀態(tài)為flase將第i個結(jié)點重新賦為基準點是否為最后的結(jié)點將選出的結(jié)點的編號送到數(shù)組downnote中,并將他的狀態(tài)改變是否已經(jīng)排序完成顯示度數(shù)呈遞減順序結(jié)束YYYNNN圖 3.2 子函數(shù) sort沈陽航空航天大學(xué)課程設(shè)計報告 73.1.33.1.3 br

9、ush_sortbrush_sort 子函數(shù)子函數(shù)此部分是本程序中最重要的部分，即為結(jié)點進行著色。 開始在數(shù)組downnote的元素對應(yīng)的度數(shù)找出相應(yīng)的結(jié)點，按遞減順序從第一個結(jié)點開始判斷判斷此結(jié)點是否著色對此結(jié)點進行第一種顏色的著色找出與此結(jié)點相鄰的結(jié)點，并將這些結(jié)點的狀態(tài)該為假循環(huán)所有結(jié)點，找出狀態(tài)為真，且沒有著色的結(jié)點這些節(jié)點是否相鄰將找出的第一個結(jié)點著上剛才的與它不相鄰的結(jié)點的顏色，并將其余的結(jié)點的狀態(tài)重新改為真將著色的顏色改為第二種，并將儲存的顏色數(shù)加1是否都已經(jīng)著色完成顯示各點的顏色，并顯示顏色個數(shù)結(jié)束判斷下一個結(jié)點YNYY將他們都著上與第一種顏色相同的色NN圖 3.3 子函數(shù) b

10、rush_color沈陽航空航天大學(xué)課程設(shè)計報告 83.23.2 主程序流程圖主程序流程圖開始輸入結(jié)點個數(shù)和邊的個數(shù)順序調(diào)用初始化子程序、關(guān)聯(lián)矩陣陳程序、排序程序和著色子程序再次輸入結(jié)點和邊的個數(shù)，以及相應(yīng)的子程序是否繼續(xù)結(jié)束YN圖 3.4 主函數(shù)沈陽航空航天大學(xué)課程設(shè)計報告 94 調(diào)試分析調(diào)試分析4.14.1 調(diào)試時遇到的問題調(diào)試時遇到的問題調(diào)試的時候主要遇到一下幾個問題：1：當(dāng)給度數(shù)最大的結(jié)點上第一種顏色，并與他不相鄰的結(jié)點著上相同的顏色，這時在著上色的結(jié)點當(dāng)中出現(xiàn)了相鄰的結(jié)點之間著上的是相同的顏色。2：在排序函數(shù)中，假如出現(xiàn)了度數(shù)相等的情況時，則不能保證將正確的順序存放到數(shù)組 downn

11、ote 中，也就是說有的結(jié)點沒有存放進去。 3：當(dāng)輸出有幾種顏色時，出現(xiàn)了大于 5 種以上的情況，我們知道韋爾奇鮑威爾算法針對連通圖著色最多有 5 種情況，保證顏色數(shù)最少，多于 5 種的就不符合要求。4.24.2 解決方案解決方案1：出現(xiàn)這個錯誤非常嚴重，因為這不符合本題的根本要求。當(dāng)給第一個結(jié)點上色完成后，對與它不相鄰的結(jié)點也上同樣的顏色，這時就需要在這些不相鄰的結(jié)點之間也要求彼此不相鄰，才能上色，只要出現(xiàn)相鄰就要將后者狀態(tài)改為假，并且不予以著色。2：針對第二個問題，經(jīng)過調(diào)試發(fā)現(xiàn)，沒有考慮相等的度數(shù)的情況，以至于出現(xiàn)相等就跳過。首先將相等且度數(shù)最大的這些結(jié)點存放到數(shù)組中，他們之間可以沒有順序

12、，然后度數(shù)次之的按同樣的方式存儲，檢查各個結(jié)點的狀態(tài)，如果還有沒有存儲的結(jié)點，這肯定是度數(shù)最少的直接存放到數(shù)組的末尾。3：針對第三個問題，我們發(fā)現(xiàn)存儲顏色個數(shù)的變量 count_是全局變量，每次運行完保存當(dāng)前值，下次運行時從當(dāng)前值開始累加，這就造成顏色數(shù)有時候大于 5 的情況，所以在下次運行之前要將此變量初始化。沈陽航空航天大學(xué)課程設(shè)計報告 104.34.3 調(diào)試結(jié)果及說明調(diào)試結(jié)果及說明 1. 說明（1） 本程序的運行環(huán)境為 VC；（2） 進入演示程序后即顯示提示信息： 輸入結(jié)點數(shù) m; 輸入邊數(shù) n： 輸入第一條邊： 輸入第二條邊： 輸入第 n 條邊： 輸入完畢后即顯示出關(guān)聯(lián)矩陣，以及度數(shù)排

13、列順序，給點的著色以及有幾種顏色。2 測試結(jié)果當(dāng)輸入 3 各結(jié)點，3 條邊時，即是三角形這樣的簡單的例子，各點的度都為 2，所以需要上三種顏色。沈陽航空航天大學(xué)課程設(shè)計報告 11參考文獻參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu) （C 語言版）M.北京:清華大學(xué)出版,2007 年 2 朱站立，張選平.數(shù)據(jù)結(jié)構(gòu)M.西安：西安交通大學(xué)出版社，2007 年3 耿素云，屈婉玲.離散數(shù)學(xué)M.北京：高等教育出版社，2003 年沈陽航空航天大學(xué)課程設(shè)計報告 12源程序（清單）源程序（清單）#include #include iomanipusing namespace std;typedef struct Nod

14、e/結(jié)點int v;/結(jié)點號int deg;/度int color;/顏色(0 表示無色)bool flag;/是否著色Node;Node node20;typedef struct Edge/邊int e0;/邊號Node e1;/起始點Node e2;/終止點Edge;Edge edge50;int node_edge5050;/關(guān)聯(lián)矩陣int downnote20;/排序角標(biāo)int count_1=0;/統(tǒng)計顏色int draw_color=1;/初始顏色void inite(int m,int n);/ 初始化邊和結(jié)點void memset_(int m,int n);/設(shè)置關(guān)聯(lián)矩陣及

15、各結(jié)點的度void sort(int m,int n);/讀書排序void brush_color(int m,int n);/將各點的度著色void inite(int m,int n)int i,j，a,b;for (i=0;im;i+)nodei.v=i;nodei.deg=0;nodei.color=0;nodei.flag=false;for (j=0;jn;j+)cout輸入第j條邊ab;cout第 ej邊為：(va,vb)endl;edgej.e0=j;沈陽航空航天大學(xué)課程設(shè)計報告 13edgej.e1.v=a;edgej.e2.v=b;void memset_(int m,in

16、t n)int i,j;for (i=0;im;i+)for (j=0;jn;j+)node_edgeij=0;if (nodei.v=edgej.e1.v)|(nodei.v=edgej.e2.v)node_edgeij=node_edgeij+1;nodei.deg=nodei.deg+1;cout關(guān)聯(lián)矩陣表示如下：endl;for (i=0;im;i+)coutsetw(3);for (j=0;jn;j+)coutnode_edgeijsetw(3);coutendl;cout各個結(jié)點的度數(shù)如下：endl;for (i=0;im;i+)cout第 vi個結(jié)點的度為：nodei.degen

17、dl;void sort(int m,int n)int i,j,temp;for(i=0;im;i+)downnotei=0;nodei.flag=true;j=0;while (jm)temp=0;for (i=0;im;i+)沈陽航空航天大學(xué)課程設(shè)計報告 14if (nodetemp.deg=nodei.deg)&(nodei.flag!=false)temp=i;nodetemp.flag=false;downnotej=temp;j+;for (i=0;im;i+)if (nodei.flag!=false)nodei.flag=false;downnotem-1=i;cou

18、t度數(shù)重新排列呈遞減順序：endl;for (j=0;jm;j+)cout第 vdownnotej個結(jié)點的度數(shù)：nodedownnotej.degendl;void brush_color(int m,int n)int i,j,k,p,q,t;for (i=0;im;i+)nodei.flag=true;for (i=0;im;i+)for (j=0;jm;j+)if (downnotei=nodej.v)if (nodej.color!=0)break;elsenodej.color=draw_color;for (k=0;kn;k+)if(nodej.v=edgek.e1.v)q=edg

19、ek.e2.v;nodeq.flag=false;沈陽航空航天大學(xué)課程設(shè)計報告 15else if (nodej.v=edgek.e2.v)q=edgek.e1.v;nodeq.flag=false;for (k=0;km;k+)if (nodek.flag=1&nodek.color=0)nodek.color=draw_color;for (t=0;tn;t+)if (nodek.v=edget.e1.v)q=edget.e2.v;if (nodeq.flag!=0)nodeq.flag=0;if (nodek.v=edget.e2.v)q=edget.e1.v;if(nodeq.

20、flag!=0)nodeq.flag=0;for (t=0;tm;t+)if (nodet.flag=1&nodet.color=0)nodet.color=draw_color;draw_color=draw_color+1;count_1=count_1+1;break;for (p=0;pm;p+)nodep.flag=true;cout此圖共有count_1種顏色，即是count_1色無向連通圖endl;沈陽航空航天大學(xué)課程設(shè)計報告 16cout各結(jié)點對應(yīng)的顏色是：endl;for (i=0;im;i+)cout第 vi個結(jié)點的顏色是：;switch(nodei.color)case 1:coutsetw(2)1紅色endl;break;case 2:coutsetw(2)2黃色endl;break;case 3:coutsetw(2)3藍色endl;break;case 4:coutsetw(2)4綠色endl;break;case 5:coutsetw(2)5黑色endl;break;void main(void)int m,n;/結(jié)點和邊cout輸入結(jié)點個數(shù)：m;cout輸入邊的個數(shù)：n;inite(m,n);memset_(m,n);sort(m,n);brush_color(m,n);ch