實(shí)驗(yàn)4 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)四動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)姓名 xxxxxxx 學(xué)號(hào) xxxxxxxx 班級(jí) xxxxxxxx時(shí)間：xxxxxx地點(diǎn)：xxxx同組人：無(wú)指導(dǎo)教師：xxxxxx實(shí)驗(yàn)?zāi)康恼莆談?dòng)態(tài)規(guī)劃法算法設(shè)計(jì)的一般原理和方法。理解動(dòng)態(tài)規(guī)劃向前處理和向后處理的思想，掌握遞推公式的求解方法。掌握多段圖、每對(duì)結(jié)點(diǎn)之間最短路徑的計(jì)算算法。能用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法求解一般問(wèn)題。實(shí)驗(yàn)內(nèi)容設(shè)計(jì)求解多段圖問(wèn)題的動(dòng)態(tài)規(guī)劃程序，上機(jī)調(diào)試通過(guò)。設(shè)計(jì)求解每對(duì)結(jié)點(diǎn)之間最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序，上機(jī)調(diào)試通過(guò)。準(zhǔn)備幾個(gè)多段圖和幾個(gè)道路交通圖的數(shù)據(jù)。輸入求解多段圖問(wèn)題的動(dòng)態(tài)規(guī)劃程序，并用準(zhǔn)備的數(shù)據(jù)調(diào)試通過(guò)。輸入每對(duì)結(jié)點(diǎn)之間最短

2、路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序，并用準(zhǔn)備的數(shù)據(jù)調(diào)試通過(guò)。實(shí)驗(yàn)環(huán)境硬件：Intel(R) Pentium(R) CPU RAM:4G軟件：Myeclipse2013編程語(yǔ)言：Java實(shí)驗(yàn)前準(zhǔn)備1、算法設(shè)計(jì):一、多段圖問(wèn)題與其向前處理法V2VI9732V3V4V5331011411552一個(gè)5段圖的例子FGRAPH(E, k, n, P) 多段圖的向前處理算法/real COST(n), integer D(n-1),P(k), r, j, k, nCOST(n)0forlineprocedure4設(shè)r是一個(gè)這樣的結(jié)點(diǎn)，j,rE且使取最小值。5COST (j)c(j, r)+COST(r)6D(j) r7

3、repeat8P(1) 1;P(k) n9for j2 to k-1 do10P(j) D(P(j-1)11repeat12endFGRAPHjnT to 1 by -1 doc(j, r)+COST(r)123456789101112二、求每對(duì)結(jié)點(diǎn)之間最短路徑長(zhǎng)度問(wèn)題的算法lineprocedure ALL-PATHS(COST, A, n) integer i, j, k, n; real COST(n, n), A(n, n) for i1 to n dofor j 1 to n doA(i,j) COST(i,j) repeat repeat for k1 to n do for i

4、1 to n do for j 1 to n doA k(i,j) minA k-1(i,j), A k-1(i,k)+A k-1(k,j) repeat repeat repeat13 endALL-PATHS1、程序設(shè)計(jì)：見(jiàn)附1實(shí)驗(yàn)步驟1、準(zhǔn)備實(shí)驗(yàn)數(shù)據(jù)。準(zhǔn)備幾個(gè)多段圖和幾個(gè)道路交通圖的數(shù)據(jù)。多段圖的實(shí)驗(yàn)數(shù)據(jù)和道路交通圖的數(shù)據(jù)均可利用程序生成 (ReadEdgeData.java 的 randMultGraph 和 radomDirectedGraph)；其中多段圖的生成原則是n個(gè)結(jié)點(diǎn)分為k段，且每段大約為4到5個(gè)結(jié)點(diǎn)， 第一個(gè)和最后一個(gè)結(jié)點(diǎn)要和相鄰段所有結(jié)點(diǎn)相連，中間段的結(jié)點(diǎn)與相鄰段的結(jié)點(diǎn)

5、 至少要有一個(gè)結(jié)點(diǎn)相鄰，每條邊的成本隨機(jī)生成。道路交通圖至少則是生成有圖的方式，n個(gè)結(jié)點(diǎn)有(n*n)*4/5使邊數(shù)不至 于多，也不至于少。將生成的邊以數(shù)對(duì)的形式存于文本文件中，如下圖，其中第一行分別為結(jié)點(diǎn) 數(shù)和邊數(shù)。剩下的若干行表示每條表的兩個(gè)結(jié)點(diǎn)和成本。在需要的時(shí)間通過(guò)讀取 文本文件來(lái)獲取數(shù)據(jù)。Mu tGraohLtxt -記事本回2文件舊宏輯(E)格式。查者凹幫助(H)24 645 61 2 11 4 101 3 9 TOC o 1-5 h z 6 78 32 7 112 10 59 109 98 84 10 64 7 24 11 119 78 69 108 515 212 67 14 1

6、116 114 312 98 15 28 13 616 1116 313 12、多段圖問(wèn)題的動(dòng)態(tài)規(guī)劃程序根據(jù)算法設(shè)計(jì)的多段圖向前處理法的sparks語(yǔ)言，寫(xiě)出相應(yīng)的java程序，并調(diào)試驗(yàn)證通過(guò)。其中邊是以鄰接表的形式表現(xiàn)出來(lái)更方便顯示點(diǎn)之間的鄰接關(guān)系。/*=1 j)(int minCost=Graph.MAXCOSTint r=1LinkedLi costList= G.getCostList()jfor (Edge edge : costList) /找到U j 之后的一個(gè)點(diǎn) r， 使 edge.cost+COSTr取最小值，并將最小值賦給minCostint v=edge.v /edge.

7、cost 代表 j 至U v 的權(quán)值 if(vj &edge.cost+COSTvminCost)=v rminC=dtge . cost+COST vCOT=minCost 將從j到最后一個(gè)結(jié)點(diǎn)的最短路徑的權(quán)值賦給COSTj D=r1=1 /第一個(gè)結(jié)點(diǎn)?k=n /最后一個(gè)結(jié)點(diǎn)for (int j=2 jk j+) / /找路徑上的第j個(gè)結(jié)點(diǎn)j=DPj 1將課本上的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行計(jì)算得到結(jié)果如下，其結(jié)果與書(shū)的最短路徑一致。3、最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序根據(jù)最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序算法的sparks語(yǔ)言寫(xiě)出對(duì)應(yīng)的java程序， 并調(diào)試驗(yàn)證通過(guò)，對(duì)比相同數(shù)據(jù)下的用求單源點(diǎn)最短路徑算法求解每對(duì)結(jié)點(diǎn)之

8、間最短路徑得出的結(jié)果相同/*計(jì)算每對(duì)結(jié)點(diǎn)之間的最短路徑長(zhǎng)度param COST r個(gè)結(jié)點(diǎn)的鄰接矩陣param A Aij是從i到j(luò)的最短路徑的成本param n結(jié)點(diǎn)個(gè)數(shù)*/public static void ALL_PATHS(int COST, int A, int n) for (int i = 0 i = n i+) /將 COSTij 復(fù)制到 Aij中 for (int j = 0 j = n j+) i j = COSTijfor (int k = 1 k = n k+) /對(duì)最高下標(biāo)為k的結(jié)點(diǎn)的路徑 for (int i = 1 i = n i+) /對(duì)于所有可能的結(jié)點(diǎn)對(duì)for

9、(int j = 1 j (Aik + Akj)ij = Aik + Akj 輸出結(jié)點(diǎn)如下圖，且結(jié)果與實(shí)驗(yàn)三得到的單源最短路徑一致JiJ| AllPaths.java 風(fēng) JZ1 Fgraph.java | JT Rea d E d g eData J a va| JT| Graph.java TOC o 1-5 h z -*/J .L-_l l_ _1l_1for (int j = 0； j = n; j+) Aij = COSTij;7172_ for (int k = 1; k = n; k+) /對(duì)最高下標(biāo)為k的結(jié)點(diǎn)的路徑Problems JavadocI 凰 Declaration

10、l莽 Project Migration 田Console 3terminatedAllPaths Java Application C:UsersXTAppDataLocalMyEclipse Professionslbinarycom.sunava.jdk.win32.x86_64_1.6.0.u43binjavaw.exe (0123456789101012995001000124724004311364682730333227036131541CO314474114042201131500545647430340051126271462250205251575635113260CO39

11、108414439144g000297924g224420g3235030101351644464234380/*計(jì)算后所有對(duì)結(jié)點(diǎn)的最短路徑* * * * /01234567891010120851597642401979148610331516017131524173144781401217111451151062060201451965116210095747562281060111198891511318120679242522262037322502844、（附加3 ）最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃的最短路徑根據(jù)短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序，添加一個(gè)AllParent數(shù)組用來(lái)記錄每個(gè)結(jié)點(diǎn)的最短路徑

12、的父結(jié)點(diǎn)，最后通過(guò)入棧和出棧的方式輸出每個(gè)結(jié)點(diǎn)的路徑/*計(jì)算每對(duì)結(jié)點(diǎn)之間的最短路徑長(zhǎng)度，并將最短路徑記錄下來(lái)param COSTparam Aparam nparam AllParent*/public static void ALL_PATHS(int COST, int A, int n, int AllParent) for (int i = 0 i = n i+) /將 COSTij復(fù)制到 Aij中，將將 所有結(jié)點(diǎn)的父結(jié)點(diǎn)設(shè)為自身for (int j = 0 j = n j+) i j = COSTij AllParentij = ifor (int k = 1 k = n k+) /

13、對(duì)最高下標(biāo)為k的結(jié)點(diǎn)的路徑 for (int i = 1 i = n i+) /對(duì)于所有可能的結(jié)點(diǎn)對(duì)for (int j = 1 j (Aik + Akj) ij = Aik + AkjAllParentij = k 屈 疫筮L3 彝, Q 必,4,密何.5 21 AllPaths.javaFgraph.javaI J7 ReadEdgeData.java| JJ Graph.java W |for (int j = 0； j = n； j+) | SunFaFenXi/src/test/exp4/Graph.java Aij = COSTij; 1：7172, for (int k = 1;

14、 k AllPaths Java Application C:UsersXTAppDataLocaKMyEclipse Professionalbinarycom.sun.java.jdk.win32.x86 64 1.5.0.u43binjavaw.exe (2014-5-恿 Problems I Javadoc 凰 Declaration Project Migration Console 洛651162100957475622810601111988915113181206792425222620373225028101216461610370/*到其它 點(diǎn) 的單源最路徑* * /1=2

15、:11=2=10=3：201=2=10=4:81=5:51=2=7=6:151=2=7:91=2=10=8:71=5=9:61=2=10:4/*2 到其它點(diǎn)的單源最路徑* * j2=1。=1：42=10=3:192=1。=4:72=10=5:92=7=6:142=7:8實(shí)驗(yàn)結(jié)果及其分析1、多段圖的向前處理法實(shí)驗(yàn)中取100000次運(yùn)行的數(shù)據(jù)結(jié)點(diǎn)數(shù)n1224364860728496108120100000次運(yùn)行所用時(shí)間576399147199324391438494578題該問(wèn)題根據(jù)課上的理論分析知為時(shí)間復(fù)雜度為O(n+e)，其中e為邊數(shù)，似 于線性與圖有所區(qū)別這可以是由于數(shù)據(jù)量太少和計(jì)算和復(fù)雜造

16、成的噪聲干擾, 但總體來(lái)看其趨勢(shì)仍接近線性;2、最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃程序?qū)崿F(xiàn)結(jié)果n102030405060708090100所用時(shí)間4223192825084594778212126175982460633810實(shí)驗(yàn)結(jié)果通過(guò)添加趨勢(shì)線可能符合理論分析結(jié)果;它與貪心方法的時(shí)間復(fù)雜度一 樣，但成本上比貪心方法弱些且計(jì)算簡(jiǎn)單，容易理解。附加3是對(duì)上題添加路徑，只是在計(jì)算過(guò)程中記錄每個(gè)結(jié)點(diǎn)的上個(gè)結(jié)點(diǎn)，以 樹(shù)的形式保存下來(lái)，再通過(guò)先入棧再出棧的方式將每對(duì)結(jié)點(diǎn)的路徑輸出出來(lái)。4、總結(jié)動(dòng)態(tài)規(guī)劃是將一個(gè)問(wèn)題的活動(dòng)分為若干個(gè)階段，而且每個(gè)階段在任一階段后 的行為都僅信賴于i階段的過(guò)程

17、狀態(tài)它指出無(wú)論過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最偉決策序列，這便是最優(yōu)性原理。動(dòng)態(tài)規(guī)劃和貪心算法一樣都是求最短路徑問(wèn)題,通過(guò)最優(yōu)性原理求僻出最優(yōu) 策略，可以快速準(zhǔn)確的救出多段圖問(wèn)題和每對(duì)結(jié)點(diǎn)的最短路徑問(wèn)附：源代碼1、多段圖的向前處理法 Fgraph.javaimport java.io.Fileimport java.util.LinkedListpublic class Fgraph (/*多段圖的向前處理算法* param args*/public static void main(String args) (int Z = 10/數(shù)據(jù)個(gè)數(shù)

18、int tp = 0 /文件的初始編號(hào)long D = new long Z2 /記錄數(shù)據(jù)量和運(yùn)行時(shí)間的數(shù)組String surDi = E:我的文檔大三下算法分析與設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)4動(dòng) 態(tài)規(guī)劃算法設(shè)計(jì)datafor (int t = 0 t 10 t+) String fileNam= MultGraph + t + .txtFile su= new File(surDir, fileName)Graph = null/從文件中讀取圖的有關(guān)信息if (G = ReadEdgeData.readEdges(sur, true) = null) Sys .emit. println (讀取錯(cuò)誤，請(qǐng)檢

19、查！)return).GnitCostList()int k = 5 + t / 段數(shù)int n = G.n / 結(jié)點(diǎn)數(shù)int P = new intk + 1/循環(huán)計(jì)算MM次計(jì)算其運(yùn)行時(shí)間long time = 0, T1, T2int MM = 100000T= System.currentTimeMillis()for (int j = 0 j MM j+) FGR (P3, k, n, P)T= System.currentTimeMillis() tim= T2T1t0 = n /將結(jié)點(diǎn)和對(duì)應(yīng)的計(jì)算時(shí)間加入數(shù)組便于輸出t1 = time/*for (int i = 1; i P.le

20、ngth; i+) ( System.out.print(Pi + t); System.out.println();*/ /輸出結(jié)點(diǎn)和對(duì)應(yīng)的運(yùn)行時(shí)間for (int k = 0 k Z k+) Syst.mut.print(Dk0 + t) Syste.nout. println ()for (int k = 0 k Z k+) Syst.mut.print(Dk1 + t) Syste.nout. println ()/* 火輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，G表示圖，并且用鄰接表的訪求來(lái)表示邊集，最后得 到的是最小成本路徑P*paramG*圖*paramk*段圖*paramn*個(gè)結(jié)點(diǎn)*par

21、amP*最小成本路徑*/public static void FGRAPH(Graph G, int k, int n, int P) int COST = new int n + 1 /用來(lái)記錄從j到最后一個(gè)結(jié)點(diǎn)的最小權(quán)值int D = new int n / Dj用來(lái)表示j到最后一個(gè)結(jié)點(diǎn)最短路徑上的后續(xù) 一個(gè)結(jié)點(diǎn)for (int j = n 1 j = 1 j)int minCost = Graph.MAXCOSTint r = 1LinkedLi costList = G.getCostList()jfor (Edge edge : costList) / 找到1j 之后的一個(gè)點(diǎn) r，

22、使 edge.cost+COSTr取最小值，并將最小值賦給minCostint v = edge . v / edge.cost 代表 j 至U v 的權(quán)值if (v j & edge.cost + COSTv minCost) =rvminCo=tedge.cost + COSTvCOT = minCost /將從j到最后一個(gè)結(jié)點(diǎn)的最短路徑的權(quán)值賦給 COSTj) = r1 = 1 /第一個(gè)結(jié)點(diǎn)?k = n /最后一個(gè)結(jié)點(diǎn)for (int j = 2 j k j+) /找路徑上的第j個(gè)結(jié)點(diǎn)p = DPj 12、最短路徑問(wèn)題AllPaths.javaimport java.io.File pu

23、blic class AllPaths /*每對(duì)結(jié)點(diǎn)之前的最短路徑長(zhǎng)度 * param args*/ public static void main(String args) int Z = 10/數(shù)據(jù)個(gè)數(shù)int tp = 21 /文件的初始編號(hào)long D = new long Z2 /記錄數(shù)據(jù)量和運(yùn)行時(shí)間的數(shù)組String surDi = E:我的文檔大三下算法分析與設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)4動(dòng) 態(tài)規(guī)劃算法設(shè)計(jì)datafor (int t = 0 t 10 t+) String fileName= Edges+(tp+t)+.txt File sur= new File(surDir, fileNam

24、e) Graph G= null/從文件中讀取圖的有關(guān)信息if (G = ReadEdgeData.readEdges(sur, true) = null) Syst .mut .println (讀取錯(cuò)誤，請(qǐng)檢查！) returnint n = G.getN()int COST = G.getCost() /*for (int i = 0; i = n; i+) ( for (int j = 0; j = n; j+) (if (COSTij = Graph.MAXCOST) ( System.out.print(8t); else ( System.out.print(COSTij + t

25、);System.out.println();*/int A = new intn + 1n + 1int AllParent=new intn+1n+1/*形如計(jì)mmmmmmmm*/*ALL_PATHS(COST, A, n);*/循環(huán)計(jì)算MM次計(jì)算其運(yùn)行時(shí)間 long time = 0, T1, T2 int MM = 10000T1= System.currentTimeMillis()for (int j = 0 j MM j+) ALL_PAT(COST, A, n,AllParent)T2= System.currentTimeMillis ()time= T2T1北0 = n /

26、將結(jié)點(diǎn)和對(duì)應(yīng)的計(jì)算時(shí)間加入數(shù)組便于輸出 北1 = time/*計(jì)算結(jié)束*/System.out.println(/*計(jì)算后所有對(duì)結(jié)點(diǎn)的最短路徑 */);/*for (int i = 0; i = n; i+) (for (int j = 0; j = n; j+) (if (Aij = Graph.MAXCOST) (System.out.print(8t); else (System.out.print(Aij + t);System.out.println();displayPath(AllParent,A,n);*/輸出結(jié)點(diǎn)和對(duì)應(yīng)的運(yùn)行時(shí)間for (int k = 0 k Z k+) S

27、yscteunt .print (D k0 + t)Sys .emit. println ()for (int k = 0 k Z k+) Syscout.print(Dk1 + t) Sys .emit. println ()/*計(jì)算每對(duì)結(jié)點(diǎn)之間的最短路徑長(zhǎng)度param COST n個(gè)結(jié)點(diǎn)的鄰接矩陣param A Aij是從i到j(luò)的最短路徑的成本param n結(jié)點(diǎn)個(gè)數(shù)*/public static void ALL_PATHS(int COST, int A, int n) for (int i = 0 i = n i+) /將 COSTij 復(fù)制到 Aij中 for (int j = 0

28、j = n j+) i j = COSTijfor (int k = 1 k = n k+) /對(duì)最高下標(biāo)為k的結(jié)點(diǎn)的路徑 for (int i = 1 i = n i+) /對(duì)于所有可能的結(jié)點(diǎn)對(duì)for (int j = 1 j (Aik + Akj)ij = Aik + Akj /*計(jì)算每對(duì)結(jié)點(diǎn)之間的最短路徑長(zhǎng)度，并將最短路徑記錄下來(lái)param COSTparam Aparam nparam AllParent*/public static void ALL_PATHS(int COST, int A, int n, int AllParent) for (int i = 0 i = n i

29、+) /將 COSTij復(fù)制到 Aij中，將將 所有結(jié)點(diǎn)的父結(jié)點(diǎn)設(shè)為自身for (int j = 0 j = n j+) i j = COSTijAllPar ri j = ifor (int k = 1 k = n k+) /對(duì)最高下標(biāo)為k的結(jié)點(diǎn)的路徑 for (int i = 1 i = n i+) /對(duì)于所有可能的結(jié)點(diǎn)對(duì)for (int j = 1 j (Aik + Akj) ij = Aik + AkjAllPa i j = k/*用來(lái)輸出單源點(diǎn)路徑param vparam parentparam DISTparam n*/public static void displayPath(

30、int v, int parent, int DIST, int n) int stack = new intnfor (int i = 1 i 1) /依次出棧并輸出 Sysc(euit .print (stack top) if (top 0) Sy .bent .print (=)topif (DIST i Graph.MAXCOST) Sysc(euit .println (: + DIST i) else Sys count. println (:Infinity)/*火用來(lái)輸出所有點(diǎn)的最短路徑param AllParentparam ALLDISTparam n*/public s

31、tatic void displayPath( int AllParent, int ALLDIST, int n)for(int i=1 i=n i+)Syst.mut.println(/*+i+ 到其它點(diǎn)的單源最路徑 */)displayPa(h,AllParenti,ALLDISTi,n)3、圖和邊類Graph.javapackage test.exp4 import java.util.LinkedList public class Graph int n 點(diǎn)的個(gè)數(shù) int m 邊的個(gè)數(shù) Edg edge /m=edge.length+1，邊從 1 開(kāi)始到U m 止 int costL

32、inkedLis costList public LinkedList getCostList () return costList public void setCostList(LinkedList costList) this.costList = costListboolean isDirected=falsepublic static int MAXCOST = Integer .MAX_VALUE /表示無(wú)窮大 static int MINCOST = Integer.MIN_VALUE /表示無(wú)窮大 public Graph()public Graph(int n,int m,E

33、dge edge,boolean isDirected) this .m=mthis .n=nthis.edge=edgethis.isDirected=isDirectedthis.initCost()public Graph (int n,int m,Edge edge)(this.m=mthis .n=nthis.edge=edgeisDirecte=falsethis.initCost ()/*初始化鄰接矩陣*勺將COST0j和COSTi0設(shè)為列編號(hào)和行編號(hào)COSTii將 0T連通則將COSTij設(shè)為無(wú)窮大 */public void initCost()int COST = new

34、intn + 1n + 1for(int j=0 j=n j+)CO0j=jfor (int i = 1 i = n i+) /將所有邊設(shè)為無(wú)窮大 CO i0=ifor (int j = 1 j = n j+) if(i=j)CDSj=0elseCDSj=MAXCOSTfor (int k = 1 k edge. length k+) /為鄰接矩陣賦初值 CO edgek.uedgek.v = edgek.costif (! this . isDirected) /當(dāng)為無(wú)向圖時(shí)，只賦一邊 CO edgek.vedgek.u = edgek.costthis.cost=COSTpublic vo

35、id initCostList()costLis=new LinkedListn+1for(int i=0 icostList.length i+) costLii=new LinkedList()for(int i=1 iedge.length i+) int u=edgei.u int v=edgei.v int cost=edgei.costEdge e=new Edge(u,v,cost) Edge e=new Edge(v,u,cost) costLi U.add(edl) costLiV.add(ed2) public int getN() return npublic void

36、setN(int n) this.n = n public int getM () return m public void setM(int m) this.m = m public Edge getEdge () return edge public void setEdge(Edge edge) this.edge = edge public int getCost () return cost public void setCost (int cost) this.cost = cost public boolean isDirected () return isDirected pu

37、blic void setDirected(boolean isDirected) this.isDirected = isDirected /*邊類* author XTI*/class Edge int uint vint costpublic Edge()public Edge(int u,int v,int cost)this .u=uthis .v=v,4、圖的生成與讀取ReadEdgeData.javapackage test.exp4 import java.io.BufferedReader import java.io.BufferedWriter import java.i

38、o.Fileimport java.io.FileReader import java.io.FileWriter import java.io.IOException import java.util.LinkedList class ReadEdgeData/*isDirected為true時(shí)表示讀取有向邊param surparam isDirectedreturn Graph */public static Graph readEdges(File sur,boolean isDirected) File dat=surif(! date.exists()|!date.isFile()

39、Syst .mut .println (文件不存在或有誤，請(qǐng)檢查！) return nullFileReader inReadertry(inRead=new FileReader (date) /相對(duì)于項(xiàng)目目錄，倉(cāng)4建一個(gè)文件字符讀 取流，和文件接上catch (lOException e)(Syst.mut.println(File cant be found or File creates error.)return nullBufferedReader inStrea=new BufferedReader( inReader)/緩存輸入流String str /每次讀取一行臨時(shí)存入在此

40、Strin strAry /將str分割成字符串存入的數(shù)組int n=0 存放結(jié)點(diǎn)數(shù)int m=0 /存放邊數(shù)Edg edge=nullGraph grap=nulltry if(str=inStream.readLine()!=null)str =str.split(s|t)=Integer.parseInt(strAry0)=mteger.parseInt(strAry1)e =new Edgem+1 int i=1while(str=inStream.readLine()!=null&i=m)str=syr.split(s|t)Edge=new Edge ().u=Integer.par

41、seInt(strAry 0).v=Integer.parseInt(strAry1).(e(dst=Integer . parseInt (strAry 2 )etg=ed+ igr =new Graph(n,m,edge,isDirected)inStr .aarLose ()inRea .eclose () catch (IOException e) / TODO Auto-generated catch block.printStackTrace()return graph /*火讀取無(wú)向邊param surreturn*/public static Graph readEdges(F

42、ile sur)(return readEdges(sur,false) public static Graph readEdges(String sur)(File surFil=new File(sur)return readEdges(surFile,false) /*火讀取邊param surreturn*/public static Graph readEdges(String sur,boolean isDirected)File surFil=new File(sur)return readEdges(surFile,isDirected) public static File

43、writeEdges(String destString,Graph g)File des=nulltry des= new File(destString)return writeEdges(dest, g) catch (Exception e) / TODO Auto-generated catch block.printStackTrace ()return null public static File writeEdges(File dest,Graph g)FileWriter outWritertry(outWrit =new FileWriter (dest) /相對(duì)于項(xiàng) 目

44、目錄，創(chuàng)建一個(gè)文件字符 讀取流，和文件接上catch (lOException e)(Syst.mut.println(File cant be found or File creates error.)return nullBufferedWriter outStrea=new BufferedWriter(outWriter)/緩存輸入流try int n=g.n,m=g.moutStre .mrite(g.n+ +g.m+rn) /向文件中寫(xiě)入點(diǎn)和邊數(shù)for(int i=1 in*n*(n 1)/2)/m大于n個(gè)結(jié)點(diǎn)所能連接的邊的無(wú)向邊的個(gè)數(shù)Syst .mut .println (邊的條

45、數(shù)過(guò)大)return nullGraph =new Graph ()gsetN (n)gsetM (m)LinkedLis le=new LinkedList()for (int i=1 i=n i+) / /將所可能的n*n*(n-1)/2條邊放入鏈表for(int j=i+1 j=n j+)Edg =new Edge().u=i.v=j.laeid (e)Edg ge=new Edgem+1for(int i=1 in*(n 1) / /m大于n個(gè)結(jié)點(diǎn)所能連接的邊的有向邊的個(gè)數(shù)Syst .mut .println (邊的條數(shù)過(guò)大)return nullGraph =new Graph ()

46、gsetN (n)gsetM (m)LinkedLis le=new LinkedList()for (int i=1 i=n i+) / /將所可能的n*n*(n-1)/2條邊放入鏈表for(int j=1 j=n j+) if(i!=j)Edg =new Edge().u=i.v=j.laeid (e)Edg ge=new Edgem+1for(int i=1 i=m i+)int s=le.size()int r=(int)(Math. random()*s) /在鏈表中隨機(jī)取一條邊并刪除 Edge=le . remove (r)int eCost=(int)(Math.random()*(maxCost minCost)+minCost) .eost=eCosti=egsetEdge (ge)return g/*隨機(jī)生成一個(gè)多段圖，n個(gè)結(jié)點(diǎn)順序編號(hào)，1為起點(diǎn)n為終點(diǎn)，共k段*param n結(jié)點(diǎn)數(shù)*param k分段數(shù)* param minCost 邊的最大值*param maxCost 邊的最小值*/public static Graph randMultGraph(int n,int k,int minCost,int maxCost)if(n=k)Syst .mut .println (分段數(shù)