

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p> 數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)</p><p> 校園導(dǎo)游系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)</p><p> 學(xué)院名稱: 計(jì)算機(jī)科學(xué)與通信工程 </p><p> 專業(yè)班級(jí): 嵌入式軟件2012 </p><p> 學(xué) 號(hào): </p><p>
2、2014 年 6 月 </p><p><b> 問(wèn)題描述</b></p><p> 校園里有若干個(gè)景點(diǎn),使用頂點(diǎn)表示,景點(diǎn)之間有路可通,使用邊表示,邊上的權(quán)值表示景點(diǎn)之間的距離,如上圖所示。請(qǐng)為校園的來(lái)訪客人設(shè)計(jì)一個(gè)導(dǎo)游咨詢程序。</p><p><b> 系統(tǒng)功能結(jié)構(gòu)</b></p>
3、<p> 使用語(yǔ)言或者圖形方式表示你所實(shí)現(xiàn)的所有功能,如下圖所示</p><p> 1,在控制臺(tái)應(yīng)用程序中畫(huà)出此圖,并把所有的可行路徑表示出來(lái)</p><p> 2,以V0為頂點(diǎn)進(jìn)行深度遍歷,顯示出遍歷序列</p><p> 3,以V0為頂點(diǎn)進(jìn)行廣度遍歷,顯示出遍歷序列</p><p> 4,利用Prime算法生成最小生成
4、樹(shù)</p><p> 5,實(shí)現(xiàn)查找兩點(diǎn)之間的最短距離的功能,方便游客選擇路徑</p><p><b> 主要數(shù)據(jù)結(jié)構(gòu)</b></p><p> 使用C#語(yǔ)言,采用控制臺(tái)方式</p><p> 編程過(guò)程應(yīng)該采用先建框架、逐步求精的方式</p><p> 1,在控制臺(tái)應(yīng)用程序中畫(huà)出此圖,并把
5、所有的可行路徑表示出來(lái)</p><p> 用一個(gè)類來(lái)存儲(chǔ)點(diǎn),用構(gòu)造方法為節(jié)點(diǎn)名,以及是否被訪問(wèn)賦值</p><p> class Vertex</p><p><b> {</b></p><p> public Vertex(string vna)</p><p><b>
6、{</b></p><p> vname = vna;</p><p> wasVisited = false;</p><p><b> }</b></p><p> public string vname;</p><p> public bool wasVisited;
7、</p><p><b> }</b></p><p> 在另一個(gè)類來(lái)實(shí)現(xiàn)功能,先聲明成員變量</p><p><b> A.用于存放節(jié)點(diǎn):</b></p><p> private Vertex[] vertices = new Vertex[7];</p><p>
8、; B.用于構(gòu)造鄰接矩陣,以此來(lái)存放權(quán)值</p><p> private int[,] cost = new int[7, 7];</p><p> C.用于計(jì)算數(shù)組中節(jié)點(diǎn)數(shù)目</p><p> private int n;</p><p> D.用于表示,即兩點(diǎn)之間沒(méi)有直接的路徑</p><p> in
9、t infinity = 9999999;</p><p> E.用于進(jìn)行深度遍歷而聲明的棧,先進(jìn)后出</p><p> Stack<Vertex> thestack = new Stack<Vertex>(7);</p><p> F.用于進(jìn)行廣度遍歷而聲明的隊(duì)列,先進(jìn)先出</p><p> Queue<
10、;Vertex> thequeue = new Queue<Vertex>();/</p><p> 先畫(huà)沒(méi)有直接路徑的鄰接矩陣的各個(gè)點(diǎn)</p><p> public Graph()</p><p><b> {</b></p><p><b> n = 0;</b>&l
11、t;/p><p> for (int i = 0; i < 7; i++)</p><p> for (int j = 0; j < 7; j++)</p><p><b> {</b></p><p> if (i == j)</p><p> cost[i, j] = 0;&
12、lt;/p><p><b> else</b></p><p> cost[i, j] = infinity;</p><p><b> }</b></p><p><b> }</b></p><p><b> 把節(jié)點(diǎn)添加到數(shù)組中<
13、;/b></p><p> public void addVertex(string vnam)</p><p><b> {</b></p><p> int i = getIndex(vnam);</p><p> if (i != -1)</p><p><b>
14、{</b></p><p> Console.WriteLine("\n該?景°點(diǎn)?已?經(jīng)-存?在ú。£");</p><p><b> return;</b></p><p><b> }</b></p><p> vertices[n]
15、 = new Vertex(vnam);</p><p><b> n++;</b></p><p><b> }</b></p><p> private int getIndex(string vname)</p><p><b> {</b></p>
16、<p> for (int i = 0; i < n; i++)</p><p> if (vertices[i].vname == vname)</p><p> return (i);</p><p> return (-1);</p><p><b> }</b></p>
17、<p> 把邊以及權(quán)值添加到二維數(shù)組中</p><p> public void addEdge(string v1, string v2, int a)</p><p><b> {</b></p><p> int i1, i2;</p><p> if (n == 0)</p>&
18、lt;p><b> {</b></p><p> Console.WriteLine("\n不?存?在ú任?何?景°點(diǎn)??!昴?需è要癮先è增?加ó");</p><p><b> return;</b></p><p><b>
19、 }</b></p><p> while (true)</p><p><b> {</b></p><p> i1 = getIndex(v1);</p><p> if (i1 == -1)</p><p> Console.WriteLine("\n該?起e
20、始?景°點(diǎn)?不?存?在ú,?請(qǐng)?重?試??!?quot;);</p><p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> while (true)</p&g
21、t;<p><b> {</b></p><p> i2 = getIndex(v2);</p><p> if (i2 == -1)</p><p> Console.WriteLine("\n該?目?的?地?景°點(diǎn)?不?存?在ú,?請(qǐng)?重?試??!?quot;);</p>&
22、lt;p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> cost[i1, i2] = cost[i2, i1] = a;</p><p><b> }</b&g
23、t;</p><p><b> 所畫(huà)成的鄰接矩陣為</b></p><p> 利用一個(gè)二維數(shù)組來(lái)存儲(chǔ)這個(gè)鄰接矩陣,數(shù)據(jù)類型為int型</p><p> private int[,] cost = new int[7, 7];//鄰近矩陣包含邊的權(quán)值</p><p><b> 顯示出所有路徑</b&
24、gt;</p><p> public void display()</p><p><b> {</b></p><p> if (n == 0)</p><p><b> {</b></p><p><b> return;</b><
25、/p><p><b> }</b></p><p> Console.WriteLine("\n景°點(diǎn)?:阰");</p><p> for (int i = 0; i < n; i++)</p><p> Console.WriteLine(vertices[i].vname);
26、</p><p> if (edgeExists())</p><p><b> {</b></p><p> Console.WriteLine("\n路·徑?:阰");</p><p> for (int i = 0; i < n; i++)</p><
27、p> for (int j = 0; j < n; j++)</p><p> if ((cost[i, j] != 0) && (cost[i, j] != infinity))</p><p> Console.WriteLine(vertices[i].vname+"--" + vertices[j].vname + "
28、 = " + cost[i, j]);</p><p><b> }</b></p><p><b> }</b></p><p> 2,以V0為頂點(diǎn)進(jìn)行深度遍歷,顯示出遍歷序列</p><p> public void dfs()//深?度è遍括?歷え?</p
29、><p><b> {</b></p><p> vertices[0].wasVisited = true;</p><p> Console.Write("深?度è遍括?歷え?的?結(jié)á果?:阰" + vertices[0].vname + ",");</p><
30、;p> thestack.Push(vertices[0]);</p><p> while (thestack.Count > 0)</p><p><b> {</b></p><p> int v = getAdjUnvisitedVertex(getIndex(thestack.Peek().vname));<
31、/p><p> if (v == -1)</p><p> thestack.Pop();</p><p><b> else</b></p><p><b> {</b></p><p> vertices[v].wasVisited = true;</p>
32、;<p> Console.Write(vertices[v].vname + ",");</p><p> thestack.Push(vertices[v]);</p><p><b> }</b></p><p><b> }</b></p><p>
33、 for (int j = 0; j < n; j++)</p><p> vertices[j].wasVisited = false;</p><p> Console.WriteLine();</p><p><b> }</b></p><p> 3,以V0為頂點(diǎn)進(jìn)行廣度遍歷,顯示出遍歷序列<
34、;/p><p> public void bfs()//廣?度è遍括?歷え?</p><p><b> {</b></p><p> Console.Write("廣?度è遍括?歷え?的?結(jié)á果?:阰" + vertices[0].vname + ",");</p&g
35、t;<p> vertices[0].wasVisited = true;</p><p> thequeue.Enqueue(vertices[0]);</p><p> while (thequeue.Count > 0)</p><p><b> {</b></p><p> int
36、w = getAdjUnvisitedVertex(getIndex(thequeue.Peek().vname));</p><p> if (w == -1)</p><p> thequeue.Dequeue();</p><p><b> else</b></p><p><b> {</
37、b></p><p> Console.Write(vertices[w].vname + ",");</p><p> vertices[w].wasVisited = true;</p><p> thequeue.Enqueue(vertices[w]);</p><p><b> }<
38、/b></p><p><b> }</b></p><p> for (int j = 0; j < n; j++)</p><p> vertices[j].wasVisited = false;</p><p> Console.WriteLine();</p><p>
39、<b> }</b></p><p> 4,利用Prime算法生成最小生成樹(shù)</p><p><b> 用于存放最小的值</b></p><p> int[] lowcost = new int[n];</p><p> for (i = 0; i < n - 1; i++)<
40、/p><p><b> {</b></p><p> min = infinity;</p><p> for (j = 0; j < n; j++)</p><p><b> {</b></p><p> if ((lowcost[j] < min) &a
41、mp;& (lowcost[j] != 0))</p><p><b> {</b></p><p> min = lowcost[j];</p><p><b> k = j;</b></p><p> Console.Write(" --" + lowcost
42、[k] + "-- " + vertices[k].vname);</p><p> for (j = 0; j < n; j++)</p><p><b> {</b></p><p> if (cost[k, j] < lowcost[j])</p><p><b>
43、 {</b></p><p> lowcost[j] = cost[k, j];</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p><b>
44、}</b></p><p><b> }</b></p><p> Console.WriteLine();</p><p> 5,實(shí)現(xiàn)查找兩點(diǎn)之間的最短距離的功能,方便游客選擇路徑</p><p> 兩個(gè)數(shù)組用于存放遍歷每一次通道的權(quán)值和最小距離</p><p> int[
45、] Distance = new int[7];</p><p> bool[] Final = new bool[7];</p><p> public void findShortestPath()//用于找圖的最短路徑</p><p><b> {</b></p><p> int[] Distance =
46、 new int[7];</p><p> bool[] Final = new bool[7];</p><p> string source;</p><p><b> int src;</b></p><p> if (n == 0)</p><p><b> {<
47、/b></p><p> Console.WriteLine("\n圖?不?存?在ú,?你?需è要癮先è插?入?一?些?頂¥點(diǎn)?和í邊?。£");</p><p><b> return;</b></p><p><b> }</b></p>
48、;<p> while (true)</p><p><b> {</b></p><p> Console.WriteLine("\n輸?入?起e始?景°點(diǎn)?:阰 ");</p><p> source = Console.ReadLine();</p><p>
49、src = getIndex(source);</p><p> if (src == -1)</p><p> Console.WriteLine("\n該?起e始?景°點(diǎn)?不?存?在ú。£");</p><p><b> else</b></p><p><b>
50、; break;</b></p><p><b> }</b></p><p> for (int i = 0; i < n; i++)</p><p> Distance[i] = cost[src, i];</p><p> Final[src] = true;</p>&l
51、t;p> for (int i = 0; i < n; i++)</p><p><b> {</b></p><p> int v = 0;</p><p> for (int j = 0; j < n; j++)</p><p><b> {</b></p>
52、;<p> if (Final[j] == false)</p><p><b> {</b></p><p><b> v = j;</b></p><p><b> break;</b></p><p><b> }</b>&l
53、t;/p><p><b> }</b></p><p> for (int j = 0; j < n; j++)</p><p><b> {</b></p><p> if ((Final[j] == false) && (Distance[j] < Distanc
54、e[v]))</p><p><b> v = j;</b></p><p><b> }</b></p><p> Final[v] = true;</p><p> for (int w = 0; w < n; w++)</p><p><b>
55、 {</b></p><p> if (Final[w] == false)</p><p><b> {</b></p><p> if (Distance[v] + cost[v, w] < Distance[w])</p><p> Distance[w] = Distance[v] +
56、cost[v, w];</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> Console.WriteLine("\n從洙?景°點(diǎn)? " + source +
57、"到?其?他?所ù有瓺景°點(diǎn)?的?");</p><p> for (int j = 0; j < n; j++)</p><p><b> {</b></p><p> if (Distance[j] == infinity)</p><p> Console.Wr
58、iteLine(source + "->" + vertices[j].vname + " =No path");</p><p><b> else</b></p><p> Console.WriteLine(source + "->" + vertices[j].vname + &quo
59、t; = " + Distance[j]);</p><p><b> }</b></p><p><b> }</b></p><p><b> 系統(tǒng)使用說(shuō)明</b></p><p> 通過(guò)文字和主要功能截圖的方式,大致說(shuō)明系統(tǒng)的使用方法</p>
60、<p> 主菜單:顯示所有功能,便于旅客自由選擇所需要的功能</p><p><b> 輸入你的選擇:</b></p><p> A.輸入1:顯示所有景點(diǎn)和所有路徑</p><p> B.輸入2:進(jìn)行深度遍歷</p><p> C,輸入3:進(jìn)行廣度遍歷:</p><p>
61、 D,輸入4:采用Prime算法實(shí)現(xiàn)最小生成樹(shù):</p><p> E,輸入5:查找兩點(diǎn)之間最短路徑:</p><p><b> 當(dāng)輸入點(diǎn)不存在時(shí):</b></p><p> 課程設(shè)計(jì)中遇到的問(wèn)題及解決方法</p><p> 1,問(wèn)題:在添加邊或者點(diǎn)時(shí)需要判斷該邊是否已經(jīng)存在:</p><p&
62、gt; 比如添加邊時(shí)的解決方法:</p><p> private bool edgeExists()</p><p><b> {</b></p><p> for (int i = 0; i < 7; i++)</p><p> for (int j = 0; j < 7; j++)</p
63、><p> if ((cost[i, j] != 0) && (cost[i, j] != infinity))</p><p> return (true);</p><p> return (false);</p><p><b> }</b></p><p> 2,問(wèn)題
64、:本想用棧的先進(jìn)后出來(lái)刪除已經(jīng)訪問(wèn)過(guò)的點(diǎn),但發(fā)現(xiàn)棧只可以用peek()的方法返回頂部的對(duì)象,不可刪除</p><p> 解決方法:int v = getAdjUnvisitedVertex(getIndex(thestack.Peek().vname));</p><p> if (v == -1)</p><p> thestack.Pop();</p
65、><p> 問(wèn)題:在深度遍歷時(shí)如何判斷節(jié)點(diǎn)是否與被訪問(wèn)節(jié)點(diǎn)有直接路徑</p><p> 解決方法: public int getAdjUnvisitedVertex(int v)</p><p><b> {</b></p><p> for (int j = 6; j >=0; j--)</p>
66、<p> if (cost[v, j] != infinity && vertices[j].wasVisited == false)</p><p><b> return j;</b></p><p> return -1;</p><p><b> }</b></p>
67、<p> 問(wèn)題:進(jìn)行廣度遍歷時(shí)需判斷圖是否存在,若不存在需進(jìn)行添加點(diǎn)和邊的操作</p><p> if (n == 0)</p><p><b> {</b></p><p> Console.WriteLine("\n圖?不?存?在ú,?你?需è要癮先è插?入?一?些?頂¥點(diǎn)?&qu
68、ot;);</p><p><b> return;</b></p><p><b> }</b></p><p><b> 帶注釋的代碼</b></p><p> using System;</p><p> using System.Col
69、lections.Generic;</p><p> using System.Text;</p><p> namespace play</p><p><b> {</b></p><p> class Vertex</p><p><b> {</b><
70、/p><p> public Vertex(string vna)</p><p><b> {</b></p><p> vname = vna;</p><p> wasVisited = false;</p><p><b> }</b></p>&
71、lt;p> public string vname;</p><p> public bool wasVisited;</p><p><b> }</b></p><p> class Graph</p><p><b> {</b></p><p> p
72、rivate Vertex[] vertices = new Vertex[7];//用于存放點(diǎn)</p><p> private int[,] cost = new int[7, 7];//用于存放權(quán)值</p><p> private int n;//用于計(jì)算節(jié)點(diǎn)個(gè)數(shù)</p><p> int infinity = 9999999;//將沒(méi)有直接路徑的邊設(shè)
73、為非常大的值</p><p> Stack<Vertex> thestack = new Stack<Vertex>(7);//進(jìn)行深度遍歷的棧 </p><p> Queue<Vertex> thequeue = new Queue<Vertex>();// 進(jìn)行廣度遍歷的 隊(duì)列</p><
74、p><b> //開(kāi)始畫(huà)鄰接矩陣</b></p><p> public Graph()</p><p><b> {</b></p><p> n = 0;//此時(shí)節(jié)點(diǎn)數(shù)為0</p><p> for (int i = 0; i < 7; i++)</p>&l
75、t;p> for (int j = 0; j < 7; j++)</p><p><b> {</b></p><p> if (i == j)</p><p> cost[i, j] = 0;</p><p><b> else</b></p><p>
76、; cost[i, j] = infinity;</p><p><b> }</b></p><p><b> }</b></p><p> //把點(diǎn)添加到數(shù)組中</p><p> public void addVertex(string vnam)</p><p&g
77、t;<b> {</b></p><p> int i = getIndex(vnam);</p><p> if (i != -1)</p><p><b> {</b></p><p> Console.WriteLine("\n該景點(diǎn)已經(jīng)存在。");</p&
78、gt;<p><b> return;</b></p><p><b> }</b></p><p> vertices[n] = new Vertex(vnam);</p><p><b> n++;</b></p><p><b> }&l
79、t;/b></p><p> //給vertices[]數(shù)組中存在的點(diǎn)命名,返回被命名點(diǎn)的個(gè)數(shù),數(shù)組中多余的點(diǎn)不必命名,返回-1 private int getIndex(string vname)</p><p><b> {</b></p><p> for (int i = 0; i < n; i++)<
80、/p><p> if (vertices[i].vname == vname)</p><p> return (i);</p><p> return (-1);//如果在列表中沒(méi)有找到,返回-1</p><p><b> }</b></p><p> //給已經(jīng)存在的點(diǎn)畫(huà)邊,并寫(xiě)上權(quán)值,
81、因是無(wú)向的,所以對(duì)稱,只需寫(xiě)一半</p><p> public void addEdge(string v1, string v2, int a)</p><p><b> {</b></p><p> int i1, i2;</p><p> if (n == 0)</p><p>&
82、lt;b> {</b></p><p> Console.WriteLine("\n不存在任何節(jié)點(diǎn)。請(qǐng)先添加一個(gè)節(jié)點(diǎn)。");</p><p><b> return;</b></p><p><b> }</b></p><p> while (tru
83、e)</p><p><b> {</b></p><p> i1 = getIndex(v1);</p><p> if (i1 == -1)</p><p> Console.WriteLine("\n該起始節(jié)點(diǎn)不存在,請(qǐng)重試。");</p><p><b&g
84、t; else</b></p><p><b> break;</b></p><p><b> }</b></p><p> while (true)</p><p><b> {</b></p><p> i2 = getIn
85、dex(v2);</p><p> if (i2 == -1)</p><p> Console.WriteLine("\n該目的景點(diǎn)不存在,請(qǐng)重試。");</p><p><b> else</b></p><p><b> break;</b></p>
86、<p><b> }</b></p><p> cost[i1, i2] = cost[i2, i1] = a;</p><p><b> }</b></p><p> //用于顯示鄰接矩陣中的所有節(jié)點(diǎn)</p><p> //判斷是否有邊的存在,有時(shí)返回true,無(wú)時(shí)返回fals
87、e</p><p> private bool edgeExists()</p><p><b> {</b></p><p> for (int i = 0; i < 7; i++)</p><p> for (int j = 0; j < 7; j++)</p><p>
88、 if ((cost[i, j] != 0) && (cost[i, j] != infinity))</p><p> return (true);//表示有邊的存在</p><p> return (false);</p><p><b> }</b></p><p> public void
89、 display()</p><p><b> {</b></p><p> if (n == 0)</p><p><b> {</b></p><p><b> return;</b></p><p><b> }</b&g
90、t;</p><p> Console.WriteLine("\n景點(diǎn):");</p><p> for (int i = 0; i < n; i++)</p><p> Console.WriteLine(vertices[i].vname);</p><p> if (edgeExists())</
91、p><p><b> {</b></p><p> Console.WriteLine("\n路徑:");</p><p> for (int i = 0; i < n; i++)</p><p> for (int j = 0; j < n; j++)</p><
92、p> if ((cost[i, j] != 0) && (cost[i, j] != infinity))</p><p> Console.WriteLine(vertices[i].vname + "--" + vertices[j].vname + " = " + cost[i, j]);&l
93、t;/p><p><b> }</b></p><p><b> }</b></p><p><b> //進(jìn)行深度遍歷</b></p><p> public void dfs()</p><p><b> {</b><
94、;/p><p> vertices[0].wasVisited = true;</p><p> Console.Write("深度遍歷的結(jié)果:" + vertices[0].vname + ",");</p><p> thestack.Push(vertices[0]);</p><p> wh
95、ile (thestack.Count > 0)</p><p><b> {</b></p><p> int v = getAdjUnvisitedVertex(getIndex(thestack.Peek().vname));</p><p> if (v == -1)</p><p> thesta
96、ck.Pop();</p><p><b> else</b></p><p><b> {</b></p><p> vertices[v].wasVisited = true;</p><p> Console.Write(vertices[v].vname + ","
97、;);</p><p> thestack.Push(vertices[v]);</p><p><b> }</b></p><p><b> }</b></p><p> for (int j = 0; j < n; j++)</p><p> verti
98、ces[j].wasVisited = false;</p><p> Console.WriteLine();</p><p><b> }</b></p><p> public int getAdjUnvisitedVertex(int v)</p><p><b> {</b><
99、;/p><p> for (int j = 6; j >=0; j--)</p><p> if (cost[v, j] != infinity && vertices[j].wasVisited == false)</p><p><b> return j;</b></p><p> ret
100、urn -1;</p><p><b> }</b></p><p> public void bfs()//廣度遍歷的 </p><p> Console.Write("廣度遍歷的結(jié)果是:" + vertices[0].vname + ",");</p><p&g
101、t; vertices[0].wasVisited = true;</p><p> thequeue.Enqueue(vertices[0]);</p><p> while (thequeue.Count > 0)</p><p><b> {</b></p><p> int w = getAdjU
102、nvisitedVertex(getIndex(thequeue.Peek().vname));</p><p> if (w == -1)</p><p> thequeue.Dequeue();</p><p><b> else</b></p><p><b> {</b></p
103、><p> Console.Write(vertices[w].vname + ",");</p><p> vertices[w].wasVisited = true;</p><p> thequeue.Enqueue(vertices[w]);</p><p><b> }</b></
104、p><p><b> }</b></p><p> for (int j = 0; j < n; j++)</p><p> vertices[j].wasVisited = false;</p><p> Console.WriteLine();</p><p><b>
105、}</b></p><p> public void findMinspantree()//采用Prime算法,生成最小生成樹(shù) {</p><p> int[] lowcost = new int[n];//存放權(quán)值最小的數(shù)</p><p> int i, j, k, min;</p><p> for (i
106、 = 0; i < n; i++)</p><p><b> {</b></p><p> lowcost[i] = cost[2, i];//V2起始所有邊的權(quán)</p><p><b> }</b></p><p> Console.Write("最小生成圖:"
107、+ vertices[2].vname);</p><p> for (i = 0; i < n - 1; i++)</p><p><b> {</b></p><p> min = infinity;</p><p> for (j = 0; j < n; j++)</p><
108、p><b> {</b></p><p> if ((lowcost[j] < min) && (lowcost[j] != 0))</p><p><b> {</b></p><p> min = lowcost[j];</p><p><b>
109、k = j;</b></p><p> Console.Write(" --" + lowcost[k] + "-- " + vertices[k].vname);</p><p> for (j = 0; j < n; j++)</p><p><b> {</b></p&
110、gt;<p> if (cost[k, j] < lowcost[j])</p><p><b> {</b></p><p> lowcost[j] = cost[k, j];</p><p><b> }</b></p><p><b> }</b&
111、gt;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> Console.WriteLine();</p><p><b> }</b>&l
112、t;/p><p> public void findShortestPath()//找圖的最短路徑 {</p><p> int[] Distance = new int[7];</p><p> bool[] Final = new bool[7];</p><p> string source;</p>&
113、lt;p><b> int src;</b></p><p> if (n == 0)</p><p><b> {</b></p><p> Console.WriteLine("\n圖不存在,你需要添加一些頂點(diǎn)和邊");</p><p><b> r
114、eturn;</b></p><p><b> }</b></p><p> while (true)</p><p><b> {</b></p><p> Console.WriteLine("\n輸入起始景點(diǎn)。 ");</p><p&
115、gt; source = Console.ReadLine();</p><p> src = getIndex(source);</p><p> if (src == -1)</p><p> Console.WriteLine("\n該起始景點(diǎn)不存在。");</p><p><b> else&l
116、t;/b></p><p><b> break;</b></p><p><b> }</b></p><p> for (int i = 0; i < n; i++)</p><p> Distance[i] = cost[src, i];</p><p&
117、gt; Final[src] = true;</p><p> for (int i = 0; i < n; i++)</p><p><b> {</b></p><p> int v = 0;</p><p> for (int j = 0; j < n; j++)</p><
118、;p><b> {</b></p><p> if (Final[j] == false)</p><p><b> {</b></p><p><b> v = j;</b></p><p><b> break;</b></p&g
119、t;<p><b> }</b></p><p><b> }</b></p><p> for (int j = 0; j < n; j++)</p><p><b> {</b></p><p> if ((Final[j] == false)
120、 && (Distance[j] < Distance[v]))</p><p><b> v = j;</b></p><p><b> }</b></p><p> Final[v] = true;</p><p> for (int w = 0; w < n
121、; w++)</p><p><b> {</b></p><p> if (Final[w] == false)</p><p><b> {</b></p><p> if (Distance[v] + cost[v, w] < Distance[w])</p>&l
122、t;p> Distance[w] = Distance[v] + cost[v, w];</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> Console.WriteLine(&q
123、uot;\n從景點(diǎn)" + source + "到其他所有景點(diǎn)的最短路徑分別是:");</p><p> for (int j = 0; j < n; j++)</p><p><b> {</b></p><p> if (Distance[j] == infinity)</p><
124、p> Console.WriteLine(source + "->" + vertices[j].vname + " =No path");</p><p><b> else</b></p><p> Console.WriteLine(source + "->" + vertice
125、s[j].vname + " = " + Distance[j]);</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> class Program</p>
126、<p><b> {</b></p><p> static void Main(string[] args)</p><p><b> {</b></p><p> Graph obj = new Graph();</p><p> string a = "V0&q
127、uot;, b = "V1", c = "V2", d = "V3", e = "V4", f = "V5", g = "V6";</p><p> obj.addVertex(a); obj.addVertex(b); obj.addVertex(c); obj.addVertex(d);&
128、lt;/p><p> obj.addVertex(e); obj.addVertex(f); obj.addVertex(g);</p><p> obj.addEdge(a, b, 2); obj.addEdge(a, d, 5); obj.addEdge(a, c, 3); obj.addEdge(a, g, 5); </p><p> obj.addEdge
129、(b, d, 2); obj.addEdge(b, f, 7);</p><p> obj.addEdge(c, e, 5);</p><p> obj.addEdge(d, f, 5); obj.addEdge(d, e, 3);</p><p> obj.addEdge(e, f, 2); obj.addEdge(e, g, 7); </p>
130、<p> obj.addEdge(f, g, 1); </p><p><b> char ch;</b></p><p><b> do</b></p><p><b> {</b></p><p> Console.WriteLine();</p
131、><p> Console.WriteLine("菜單");</p><p> Console.WriteLine("1.有路可通的景點(diǎn):");</p><p> Console.WriteLine("2.從V0頂點(diǎn)出發(fā),進(jìn)行深度優(yōu)先遍歷:");</p><p> Console
132、.WriteLine("3.從V0頂點(diǎn)出發(fā),進(jìn)行廣度優(yōu)先遍歷:");</p><p> Console.WriteLine("4.采用Prime算法實(shí)現(xiàn)最小生成樹(shù)。");</p><p> Console.WriteLine("5.找兩景點(diǎn)間的最小距離。);</p><p> Console.WriteLine
133、("6.退出。");</p><p> Console.WriteLine();</p><p> Console.Write("輸入你的選擇:");</p><p> ch = Convert.ToChar(Console.ReadLine());</p><p> switch (ch)&l
134、t;/p><p><b> {</b></p><p> case '1': obj.display(); break;</p><p> case '2': obj.dfs(); break;</p><p> case '3': obj.bfs(); break;&
135、lt;/p><p> case '4': obj.findMinspantree(); break;</p><p> case '5': obj.findShortestPath(); break;</p><p> case '6': break;</p><p> default: C
136、onsole.WriteLine("不合法的選項(xiàng)。");</p><p><b> break;</b></p><p><b> }</b></p><p> } while (ch != '6');</p><p><b> }</b&
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)報(bào)告
- 校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)報(bào)告
- 校園導(dǎo)游系統(tǒng)程序__課程設(shè)計(jì)_報(bào)告
- 校園導(dǎo)游咨詢系統(tǒng)課程設(shè)計(jì)
- 校園導(dǎo)游課程設(shè)計(jì)
- 校園導(dǎo)游系統(tǒng)程序課程設(shè)計(jì)匯本報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--校園導(dǎo)游系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-- 校園導(dǎo)游系統(tǒng)
- c++校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)
- c語(yǔ)言校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園導(dǎo)游系統(tǒng)設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)_校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園導(dǎo)游系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu) 校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)校園導(dǎo)游咨詢課程設(shè)計(jì)報(bào)告
- 校園導(dǎo)游咨詢系統(tǒng)-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園交通導(dǎo)游系統(tǒng)
- 校園導(dǎo)游咨詢系統(tǒng)---數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)——校園導(dǎo)游咨詢系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-校園導(dǎo)游程序
評(píng)論
0/150
提交評(píng)論