地圖著色課程設(shè)計(jì)

1、算法分析與設(shè)計(jì)課程設(shè)計(jì)說明書地圖著色學(xué) 院： 計(jì)算機(jī)與控制工程學(xué)院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名：xxxxx 學(xué)號(hào)： 成績(jī) 學(xué)生姓名：xxxxx 學(xué)號(hào)： 成績(jī) 指導(dǎo)教師： 內(nèi) 容 提 要此題為地圖著色問題，由地圖著色問題很容易想到圖的著色問題，因此可以把地圖抽象為無(wú)向圖來(lái)解決地圖的著色問題。對(duì)地圖的抽象相當(dāng)于對(duì)圖的抽象，即以鄰接矩陣來(lái)實(shí)現(xiàn)地圖的區(qū)域相鄰的描繪，而對(duì)地圖的區(qū)域數(shù)即以圖的頂點(diǎn)數(shù)來(lái)描繪。設(shè)計(jì)說明書的內(nèi)容包括需求分析，概要設(shè)計(jì)，詳細(xì)設(shè)計(jì)，代碼實(shí)現(xiàn)，后期測(cè)試等內(nèi)容，需求分析是對(duì)此問題所需要實(shí)現(xiàn)的功能的介紹，概要設(shè)計(jì)是對(duì)所需要實(shí)現(xiàn)功能的模塊劃分，以及初步的實(shí)現(xiàn)思想，詳細(xì)設(shè)計(jì)通過編寫

2、大致的代碼來(lái)實(shí)現(xiàn)功能，代碼實(shí)現(xiàn)則是具體的解決問題，解決此問題設(shè)計(jì)了兩個(gè)算法，貪心，回溯，在程序的測(cè)試階段，回溯算法對(duì)同一個(gè)問題的解決速率高于貪心算法，但是結(jié)果都是以最少的顏色數(shù)來(lái)染色。課題實(shí)現(xiàn)的環(huán)境是在window環(huán)境下的eclipse中，通過在其中輸入地圖的區(qū)域數(shù)，圖的連接情況，來(lái)選擇相應(yīng)的算法來(lái)實(shí)現(xiàn)染色，本次課題所采用的數(shù)據(jù)結(jié)構(gòu)主要是二維數(shù)組來(lái)抽象圖的鄰接矩陣。目 錄1引言（或緒論）12 需求分析22.1 問題分析 22.3問題解決22.3 運(yùn)行環(huán)境及開發(fā)工具32.4 功能需求 32.4.1 地圖的抽象及輸入 32.4.2 地圖著色的算法設(shè)計(jì) 32.4.3 界面設(shè)計(jì) 32.4.4 輸出設(shè)計(jì)

3、 32.5任務(wù)分配 43概要設(shè)計(jì) 43.1 數(shù)據(jù)定義 43.2 功能模塊定義 43.2.1 地圖的抽象輸入模塊 43.2.2 輸出模塊 43.2.3 地圖染色模塊 43.2.4 界面設(shè)計(jì)模塊 53.2.5 主模塊 53.3 程序流程圖 64 詳細(xì)設(shè)計(jì) 74.1 地圖輸入模塊 74.1.1 數(shù)據(jù)類型 74.1.2 具體實(shí)現(xiàn) 74.2 界面設(shè)計(jì)模塊 74.2.1 數(shù)據(jù)類型 74.2.2 具體實(shí)現(xiàn) 74.3 算法設(shè)計(jì)模塊 9 4.3.1 回溯法過程9 4.3.2 貪心法過程.105 程序設(shè)計(jì)模塊115.1 界面設(shè)計(jì)代碼115.2 染色實(shí)現(xiàn)模塊156 程序測(cè)試196.1 運(yùn)行結(jié)果196.2 貪心、回溯

4、著色結(jié)果及分析197 算法時(shí)間、空間復(fù)雜度分析227.1 遞歸回溯227.2 貪心算法228 課設(shè)總結(jié) 228.1 已實(shí)現(xiàn)功能及不足228.2 心得體會(huì)22參考文獻(xiàn)241 引言（或緒論）此次課程設(shè)計(jì)的要求是已知某地圖（如中國(guó)地圖），對(duì)各區(qū)域進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少。此問題就是經(jīng)典的地圖著色問題，地圖著色問題與四色定理是緊密相關(guān)的。地圖著色問題與著名四色定理：四色定理是一個(gè)著名的數(shù)學(xué)定理：如果在平面上劃出一些鄰接的有限區(qū)域，那么可以用四種顏色來(lái)給這些區(qū)域染色，使得每?jī)蓚€(gè)鄰接區(qū)域染的顏色都不一樣；另一個(gè)通俗簡(jiǎn)潔的說法是：每個(gè)地圖都可以用不多于四種顏色來(lái)染色，而

5、且不會(huì)有兩個(gè)鄰接的區(qū)域顏色相同。這就是著名的四色定理，由四色定理可以想到只需要四種顏色就可以為一個(gè)區(qū)域的地圖著上顏色，而且相鄰區(qū)域的顏色不相同。2 需求分析2.1 問題分析：地圖著色問題是一個(gè)抽象的圖形學(xué)問題，用程序?qū)崿F(xiàn)對(duì)各個(gè)區(qū)域進(jìn)行著色，并且相鄰省所用的顏色不同，同時(shí)保證顏色的總數(shù)最少，那么就是如何將這些抽象的進(jìn)行數(shù)據(jù)化。如何將程序所需要的功能模擬著色在計(jì)算機(jī)中編程實(shí)現(xiàn)。2.2 問題解決：計(jì)算機(jī)中，圖主要可以用兩種方法表示：鄰接矩陣和鄰接鏈表。N個(gè)頂點(diǎn)的鄰接矩陣是一個(gè)N*N的布爾矩陣，圖中的每一個(gè)頂點(diǎn)都由一行或者一列來(lái)表示，如果從第i個(gè)頂點(diǎn)和第j個(gè)頂點(diǎn)之間有邊連接，則矩陣第i行，第j列的元素

6、等于1，如果沒有邊連接，則等于0.這就是圖的鄰接矩陣表示那么地圖也可以抽象為一個(gè)圖，其可以用鄰接矩陣來(lái)進(jìn)行模擬：對(duì)于每一個(gè)地圖， 我們可以把每一個(gè)區(qū) 區(qū)域或國(guó)家) 看作一個(gè)點(diǎn)， 而區(qū)與區(qū)之間的鄰接關(guān)系看作點(diǎn)與點(diǎn)之間的連線。從而將地圖抽象為一個(gè)圖，然后就可以用鄰接矩陣抽象。如下圖：其鄰接矩陣為：ABCDEA 01100B10111C11001D01001E011112.3運(yùn)行環(huán)境及開發(fā)工具：運(yùn)行環(huán)境：windows系統(tǒng)開發(fā)工具：eclipse編程工具2.4 功能需求：2.4.1：地圖的抽象及輸入：給定一個(gè)地圖，要求畫出繪制出其圖的形式，并在計(jì)算機(jī)上用鄰接矩陣實(shí)現(xiàn)。相應(yīng)的頂點(diǎn)為0，則表示兩點(diǎn)鄰接，

7、否則，就不鄰接，為1.2.4.2：地圖著色的算法設(shè)計(jì)：回溯法：本題可采用回溯法進(jìn)行著色。當(dāng)t=1時(shí)，對(duì)當(dāng)前第t個(gè)頂點(diǎn)開始著色：若t>n，則已求得一個(gè)解，輸出著色方案即可。否則，依次對(duì)頂點(diǎn)t著色1-m， 若t與所有其它相鄰頂點(diǎn)無(wú)顏色沖突，則繼續(xù)為下一頂點(diǎn)著色；否則，回溯，測(cè)試上一顏色?；厮莘ǖ闹饕褪沁x擇各種顏色，直到把此點(diǎn)著完色為止。貪心法：選擇一種顏色，以任意頂點(diǎn)作為開始頂點(diǎn)，依次考察圖中的未被著色的每個(gè)頂點(diǎn)，如果一個(gè)頂點(diǎn)可以用顏色1著色，換言之，該頂點(diǎn)的鄰接點(diǎn)都還未被著色，則用顏色1為該頂點(diǎn)著色，當(dāng)沒有頂點(diǎn)能以這種顏色著色時(shí)，選擇顏色2和一個(gè)未被著色的頂點(diǎn)作為開始頂點(diǎn)，用第二種顏色為

8、盡可能多的頂點(diǎn)著色，如果還有未著色的頂點(diǎn)，則選取顏色3并為盡可能多的頂點(diǎn)著色，依此類推，直到所有頂點(diǎn)都著上顏色。貪心法就是選擇一種顏色，最大化的將圖中的各點(diǎn)都用這種顏色著上。2.4.3：界面設(shè)計(jì)：地圖著色的軟件界面設(shè)計(jì)，選擇何種算法，以及選擇幾種顏色來(lái)為相應(yīng)的地圖桌上顏色。2.4.4：輸出設(shè)計(jì)按要求輸出動(dòng)態(tài)的著色過程以及最終的染色結(jié)果，同時(shí)輸出最終的著色結(jié)果，以及最少顏色數(shù)，在輸出框里面輸出。2.5 任務(wù)分配：xxx：貪心法算法設(shè)計(jì)，界面設(shè)計(jì)xxx：回溯法算法設(shè)計(jì)3概要設(shè)計(jì)3.1 數(shù)據(jù)定義：int cn+1n+1：鄰接矩陣的中的數(shù)據(jù)只為0.1int color n+1:存取對(duì)對(duì)應(yīng)的點(diǎn)的顏色，顏

9、色用1,2，3,4表示int n:定義對(duì)應(yīng)的點(diǎn)數(shù)int N 著色的顏色數(shù)3.2功能模塊定義：3.2.1 地圖的抽象輸入模塊：按操作者要求輸入相應(yīng)地圖對(duì)應(yīng)圖的點(diǎn)數(shù)，以及相應(yīng)點(diǎn)與其他點(diǎn)的連接情況，此輸入在界面輸入，其中點(diǎn)數(shù)表示某個(gè)區(qū)域的地區(qū)數(shù)，而連接情況表示各區(qū)域的相鄰情況，用此來(lái)抽象地圖。 3.2.2 輸出模塊：按操作者輸入的數(shù)據(jù)，執(zhí)行相應(yīng)的算法，并且在界面上顯示出來(lái)最終的結(jié)果，輸出的有圖的鄰接矩陣，著色方案，還有圖的著色的最少顏色數(shù)。3.2.3 地圖的染色模塊：利用貪心算法以及回溯算法來(lái)為地圖進(jìn)行著色，即判斷相應(yīng)的點(diǎn)應(yīng)該著那種顏色?；厮莘ㄋ惴ㄟ^程：設(shè)數(shù)組colorn+1表示各頂點(diǎn)的著色情況，其

10、中n表示相應(yīng)的點(diǎn)數(shù)，回溯法： 1將數(shù)組colorn初始化為0；2s=1;3while (s<=n)3.1 依次考察每一種顏色，若頂點(diǎn)s的著色與其他頂點(diǎn)的著色不發(fā)生沖突，則轉(zhuǎn)步驟3.2；否則，搜索下一個(gè)顏色；3.2 若頂點(diǎn)已全部著色，則輸出數(shù)組colorn+1，以及數(shù)組colorn+1返回；3.3 否則， 3.3.1 若頂點(diǎn)s是一個(gè)合法著色，則s=s+1，轉(zhuǎn)步驟3處理下一個(gè)頂點(diǎn)； 3.3.2 否則，重置頂點(diǎn)k的著色情況，換第二種顏色給頂點(diǎn)k著色，轉(zhuǎn)步驟3。主要函數(shù)：hscolor（）貪心法算法過程：設(shè)數(shù)組colorn+1表示各頂點(diǎn)的著色情況，算法如下：1m=0,sum=0; /m著色的最少

11、顏色數(shù)，sum已經(jīng)著色的頂點(diǎn)數(shù)頂點(diǎn)12.while(sum<n)3m=m+14. for (i=1; i<=n; i+)5.尋找可以著顏色1的第一個(gè)點(diǎn)，找到就終止此循環(huán)6for (i=2; i<=n; i+)7循環(huán)用顏色m為盡量多的未著色頂點(diǎn)著色， 7.1 如果判斷的點(diǎn)能著顏色m，則colori=m，sum+ 7.2 如果判斷的點(diǎn)不能著此顏色，則找尋下一個(gè)能著此顏色得點(diǎn) 8.跳回第三步，直到sum>=n5輸出colorn,已經(jīng)最少的顏色數(shù)主要函數(shù)：txcolor3.2.4 界面設(shè)計(jì)模塊：按題目要求在界面上輸入地圖的區(qū)域數(shù)，各區(qū)域的連接情況以及選擇何種算法來(lái)進(jìn)行著色。結(jié)果

12、輸出在結(jié)果框。3.2.5 主模塊：利用以上設(shè)計(jì)的各個(gè)模塊來(lái)進(jìn)行調(diào)用，其中要選擇相應(yīng)的算法（回溯，貪心）來(lái)實(shí)現(xiàn)著色，從而完成地圖著色，并且直觀的結(jié)果在屏幕上顯示出來(lái)。3.3 程序流程圖開始輸入?yún)^(qū)域數(shù)n按鈕?選擇算法輸入chscolor()txcolor()輸出結(jié)果結(jié)束貪心算法回溯算法4 詳細(xì)設(shè)計(jì)4.1 地圖輸入模塊4.1.1數(shù)據(jù)類型：int n； 頂點(diǎn)數(shù)int cn+1n+1; 鄰接矩陣String data;地圖中各點(diǎn)的鄰接連接情況，用0.1表示4.1.2 具體實(shí)現(xiàn)： n = textField.getText();/將定義的textField中的數(shù)據(jù)給n String data = text

13、Area1.getText().split(" ");/將textArea1中的0.1數(shù)組給data for (int i = 1; i < n+1; i+) for (int j = 1; j < n+1; j+) Array_1.cij = data(i-1)*Array_1.n+j-1 /將data一維數(shù)組賦值給c二維數(shù)組4.2 界面設(shè)計(jì)模塊4.2.1 數(shù)據(jù)類型 public JTextField textField = new JTextField();public JTextArea textArea1 = new JTextArea();/設(shè)置文本域

14、public Jbutton button;/設(shè)置按鈕 public static JTextArea textArea3 = new JTextArea();/文本域 private JLabel label_1;/輸入文本標(biāo)簽private JPanel contentPane;/整個(gè)界面4.2.2 具體實(shí)現(xiàn)*設(shè)計(jì)主面板*setTitle("圖的著色");/設(shè)置名字 setBounds(100, 100, 604, 380); /設(shè)置大小 contentPane = new JPanel(); setContentPane(contentPane); contentPa

15、ne.setBackground(Color.GREEN); /設(shè)置顏色 *設(shè)計(jì)結(jié)束*文本域1*JLabel label = new JLabel("請(qǐng)輸入地圖的區(qū)域數(shù)"); label.setFont(new Font("微軟雅黑", Font.BOLD, 15); label.setBounds(23, 10, 166, 34); contentPane.add(label);textField.setBounds(23, 42, 192, 34); textField.setText("5");/設(shè)置初始值 contentPan

16、e.add(textField); textField.setColumns(10); *設(shè)計(jì)結(jié)束* *文本域2* label_1 = new JLabel("請(qǐng)輸入各區(qū)域連接情況"); label_1.setFont(new Font("微軟雅黑", Font.BOLD, 13); label_1.setBounds(23, 86, 166, 30); contentPane.add(label_1); JScrollPane scrollPane = new JScrollPane(); scrollPane.setBounds(23, 125, 1

17、92, 147); contentPane.add(scrollPane); textArea1.setText("0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1");/設(shè)置文本域二的初始值 scrollPane.setViewportView(textArea1);*設(shè)計(jì)結(jié)束* *按鈕設(shè)計(jì)* JButton button = new JButton("貪心法"); button.setFont(new Font("微軟雅黑", Font.BOLD, 14); button.setB

18、ounds(23, 282, 92, 34); button.addActionListener(new MyEvent(); contentPane.add(button); JButton button = new JButton("回溯法");/設(shè)置按鈕名字 button.addActionListener(new MyEvent(); button.setFont(new Font("微軟雅黑", Font.BOLD, 14); button.setBounds(140, 282, 92, 34); contentPane.add(button)

19、; *設(shè)計(jì)結(jié)束*結(jié)果文本域* JLabel label = new JLabel("染色結(jié)果"); label.setFont(new Font("微軟雅黑", Font.BOLD, 15); label.setBounds(369, 20, 84, 15); contentPane.add(label); JScrollPane scrollPane = new JScrollPane(); scrollPane.setBounds(248, 42, 321, 273); contentPane.add(scrollPane); scrollPane.

20、setViewportView(textArea3); *設(shè)計(jì)結(jié)束* 4.3 算法設(shè)計(jì)模塊 4.3.1 回溯法主要代碼 int i;int N=4;/設(shè)計(jì)顏色數(shù)為4，但是并不是用這么多顏色，程序最終的結(jié)果是最優(yōu)的，即輸出來(lái)的顏色數(shù)肯定最少，因?yàn)樗纳ɡ?if(s>n)/遞歸出口,遞歸的最終出口 output();/輸出結(jié)果 else for(i=1;i<=N;i+)/對(duì)每一種色彩逐個(gè)測(cè)試 colors=i;if(colorsame(s)=0)/當(dāng)測(cè)試這個(gè)顏色i=1為某個(gè)點(diǎn)著色不合格時(shí)，用第二種顏色著色，i=2進(jìn)行判斷，合格進(jìn)行遞歸調(diào)用，不合格就使用第三種顏色，即i=3 trycol

21、or(s+1);/進(jìn)行下一塊的著色 break;/停止回溯，因?yàn)橐呀?jīng)著色成功 4.3.2 貪心法主要代碼while(sum< n)/最終的判定條件，即將所有點(diǎn)著色完畢 m+;/第一次循環(huán)，m=1，m即為顏色數(shù) for(int i=1;i<=n;i+)/此循環(huán)用來(lái)查找第一個(gè)為著色的并且可以著色m的點(diǎn) if(colori=0) j=i;/j=1 colorj=m; sum+; break;/結(jié)束當(dāng)前循環(huán) for(int i=j+1;i<=n;i+)/i=2 if(colori!=0) continue;/colori的起始值為零，false，不執(zhí)行continue,表示沒有著色，

22、因此執(zhí)行下一步，否則起始值不為0，則表示已經(jīng)成功著上顏色。 if (ok(i,m) continue;/ok(i，m)，如果返回值為ture，表明有顏色與此點(diǎn)將要著的顏色相同，則執(zhí)行continue，即不將i著色為m，結(jié)束本次循環(huán)，此點(diǎn)在之后著色。 else /點(diǎn)i可以著色為m，記錄colori=m colori=m; sum+; 5 程序設(shè)計(jì)模塊5.1 界面設(shè)計(jì)代碼（Graph.java）import java.lang.System;import java.awt.Color;import java.awt.EventQueue;import javax.swing.JFrame;impo

23、rt javax.swing.JPanel;import javax.swing.JLabel;import javax.swing.JTextField;import javax.swing.JTextArea;import javax.swing.JButton;import java.awt.Font;import javax.swing.JScrollPane;import java.awt.event.ActionListener;import java.awt.event.ActionEvent;/*類Graph*public class Graph extends JFrame

24、private static final long serialVersionUID = 1L;public static long startTime = 0; public static long estimatedTime = 0;private JPanel contentPane; public JTextField textField = new JTextField(); public JTextArea textArea1 = new JTextArea(); public static JTextArea textArea3 = new JTextArea(); privat

25、e JLabel label_1;/*主函數(shù)*public static void main(String args) EventQueue.invokeLater(new Runnable() public void run() try Graph frame = new Graph(); frame.setVisible(true); catch (Exception e) e.printStackTrace(); ); /*主函數(shù)結(jié)束*/*鼠標(biāo)事件* class MyEvent implements ActionListener public void actionPerformed(A

26、ctionEvent e) Array_1.n = Integer.parseInt(textField.getText(); System.out.println(Array_1.n); String data = textArea1.getText().split(" "); System.out.println(textArea1.getText(); Array_1.c = new int(Array_1.n)+1(Array_1.n)+1; for (int i = 1; i < (Array_1.n)+1; i+) for (int j = 1; j &l

27、t; (Array_1.n)+1; j+) Array_1.cij = Integer.parseInt(data(i-1)*Array_1.n+j-1); Array_1.color=new intArray_1.n+1; for(int i=0;i<=Array_1.n;i+) Array_1.colori=0;/初始化 if (e.getActionCommand().equals("貪心法") Array_1.text_temp = Array_1.text_temp+"貪心詳細(xì)的著色過程：" Array_1.text_temp = Arr

28、ay_1.text_temp+"n"startTime = System.nanoTime();Array_1.graphcolor(); if (e.getActionCommand().equals("回溯法") Array_1.text_temp = Array_1.text_temp+"回溯詳細(xì)的著色過程：" Array_1.text_temp = Array_1.text_temp+"n"startTime = System.nanoTime(); Array_1.trycolor(1); /*事件結(jié)束*

29、/*界面設(shè)計(jì)*public Graph() setTitle("圖的著色"); setBounds(100, 100, 604, 380); contentPane = new JPanel(); setContentPane(contentPane); contentPane.setLayout(null); contentPane.setBackground(Color.GREEN); JLabel label = new JLabel("請(qǐng)輸入地圖的區(qū)域數(shù)"); label.setFont(new Font("微軟雅黑", Fo

30、nt.BOLD, 15); label.setBounds(23, 10, 166, 34); contentPane.add(label); textField.setBounds(23, 42, 192, 34); textField.setText("5"); contentPane.add(textField); textField.setColumns(10); label_1 = new JLabel("請(qǐng)輸入各區(qū)域連接情況"); label_1.setFont(new Font("微軟雅黑", Font.BOLD, 13

31、); label_1.setBounds(23, 86, 166, 30); contentPane.add(label_1); JButton button = new JButton("貪心法"); button.setFont(new Font("微軟雅黑", Font.BOLD, 14); button.setBounds(23, 282, 92, 34); button.addActionListener(new MyEvent(); contentPane.add(button); JScrollPane scrollPane = new J

32、ScrollPane(); scrollPane.setBounds(23, 125, 192, 147); contentPane.add(scrollPane); textArea1.setText("0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1"); scrollPane.setViewportView(textArea1); JButton button = new JButton("回溯法"); button.addActionListener(new MyEvent(); button.s

33、etFont(new Font("微軟雅黑", Font.BOLD, 14); button.setBounds(140, 282, 92, 34); contentPane.add(button); JLabel label = new JLabel("染色結(jié)果"); label.setFont(new Font("微軟雅黑", Font.BOLD, 15); label.setBounds(369, 20, 84, 15); contentPane.add(label); JScrollPane scrollPane = new

34、JScrollPane(); scrollPane.setBounds(248, 42, 321, 273); contentPane.add(scrollPane); scrollPane.setViewportView(textArea3); /*設(shè)計(jì)完畢*/*類Graph結(jié)束*5.2 染色實(shí)現(xiàn)模塊（Array_1.java）/*Array_1類*public class Array_1 public static int n ; public static int c ; public static int color ; public static String text_temp=n

35、ew String("");/*回溯求解*public static int colorsame(int s) int j,flag=0; for(j=1;j<s;j+) if(cjs=1&&colorj=colors) flag=1;break; return flag;public static void output()text_temp = text_temp +"n" System.out.printf("區(qū)域的鄰接矩陣為：n"); text_temp = text_temp +"區(qū)域的鄰接矩

36、陣為："+"n" for(int k=1;k<n+1;k+) for(int m=1;m<n+1;m+) System.out.print(ckm+" "); text_temp = text_temp + Integer.toString(ckm)+ " " System.out.print("n"); text_temp = text_temp +"n" text_temp = text_temp +"n" System.out.printf(&qu

37、ot;著色方案:n");text_temp = text_temp +"著色方案:"+"n"for(int i=1;i<=n;i+) System.out.print(colori+" "); text_temp = text_temp +"第"+Integer.toString(i)+"個(gè)區(qū)域著色："+ Integer.toString(colori) + " "+"n" int j=color1; for(int k=2;k<=n

38、;k+) if(j<=colork) j=colork; System.out.print("n"); text_temp = text_temp+"n" System.out.println("能著的最少顏色數(shù)為："); text_temp = text_temp + "能著的最少顏色數(shù)為："+"n" System.out.println(j); text_temp = text_temp + Integer.toString(j)+"n" ; text_temp =

39、 text_temp +"運(yùn)行時(shí)間：" + Graph.estimatedTime+"毫微秒（ns）" text_temp = text_temp +"n" Graph.textArea3.setText(text_temp);public static void trycolor(int s) int i; int N=4; if(s>n) Graph.estimatedTime = System.nanoTime() - Graph.startTime; output(); else for(i=1;i<=N;i+)

40、colors=i; if(colorsame(s)=0) System.out.println("顏色"+i+"能為區(qū)域"+s+"著色"); text_temp = text_temp +"顏色"+Integer.toString(i)+"能為區(qū)域"+Integer.toString(s)+"著色" text_temp=text_temp+"n" trycolor(s+1);break; else System.out.println("顏色&q

41、uot;+i+"不能為第"+s+"點(diǎn)著色"); text_temp = text_temp +"顏色"+Integer.toString(i)+"不能為區(qū)域"+Integer.toString(s)+"著色" text_temp=text_temp+"n" /*回溯完畢*/*貪心求解*public static boolean same(int k,int r)/判斷頂點(diǎn)k的著色是否發(fā)生沖突 for(int i=1;i< n;i+) if(colori!=r) cont

42、inue; if(cki=1&&colori=r ) return true; return false;public static void graphcolor() int j=1,m=0,sum=0; while(sum< n) m+;/第一次循環(huán)，m=1 for(int i=1;i<=n;i+) if(colori=0)/color1=0 j=i;/j=1 colorj=m;/color1=1 System.out.println("顏色"+m+"能為第"+j+"點(diǎn)著色"); text_temp =

43、 text_temp +"顏色"+Integer.toString(m)+"能為區(qū)域"+Integer.toString(j)+"著色" text_temp=text_temp+"n" sum+; break; for(int i=j+1;i<=n;i+) if(colori!=0) continue; if (same(i,m) System.out.println("顏色"+m+"不能為第"+i+"點(diǎn)著色"); text_temp = text_

44、temp +"顏色"+Integer.toString(m)+"不能為區(qū)域"+Integer.toString(i)+"著色" text_temp=text_temp+"n" continue; else colori=m; System.out.println("顏色"+m+"能為第"+i+"點(diǎn)著色"); text_temp = text_temp +"顏色"+Integer.toString(m)+"能為區(qū)域"+

45、Integer.toString(i)+"著色" text_temp=text_temp+"n" sum+; Graph.estimatedTime = System.nanoTime() - Graph.startTime; text_temp = text_temp +"n" System.out.printf("區(qū)域的鄰接矩陣為：n"); text_temp = text_temp +"區(qū)域的鄰接矩陣為："+"n" for(int k=1;k<n+1;k+) for(int l=1;l<n+1;l+) System.out.print(ckl+" "); text_temp = text_temp + Integer.toString(ckl)+ " " System.ou