2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩21頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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è)班級: 嵌入式軟件2012 </p><p>  學(xué) 號: </p><p>  

2、2014 年 6 月 </p><p><b>  問題描述</b></p><p>  校園里有若干個(gè)景點(diǎn),使用頂點(diǎn)表示,景點(diǎn)之間有路可通,使用邊表示,邊上的權(quán)值表示景點(diǎn)之間的距離,如上圖所示。請為校園的來訪客人設(shè)計(jì)一個(gè)導(dǎo)游咨詢程序。</p><p><b>  系統(tǒng)功能結(jié)構(gòu)</b></p>

3、<p>  使用語言或者圖形方式表示你所實(shí)現(xiàn)的所有功能,如下圖所示</p><p>  1,在控制臺應(yīng)用程序中畫出此圖,并把所有的可行路徑表示出來</p><p>  2,以V0為頂點(diǎn)進(jìn)行深度遍歷,顯示出遍歷序列</p><p>  3,以V0為頂點(diǎn)進(jìn)行廣度遍歷,顯示出遍歷序列</p><p>  4,利用Prime算法生成最小生成

4、樹</p><p>  5,實(shí)現(xiàn)查找兩點(diǎn)之間的最短距離的功能,方便游客選擇路徑</p><p><b>  主要數(shù)據(jù)結(jié)構(gòu)</b></p><p>  使用C#語言,采用控制臺方式</p><p>  編程過程應(yīng)該采用先建框架、逐步求精的方式</p><p>  1,在控制臺應(yīng)用程序中畫出此圖,并把

5、所有的可行路徑表示出來</p><p>  用一個(gè)類來存儲點(diǎn),用構(gòu)造方法為節(jié)點(diǎ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è)類來實(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)造鄰接矩陣,以此來存放權(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)之間沒有直接的路徑</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>  先畫沒有直接路徑的鄰接矩陣的各個(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)?不?存?在ú,?請?重?試??!?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)?不?存?在ú,?請?重?試?。£");</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>  所畫成的鄰接矩陣為</b></p><p>  利用一個(gè)二維數(shù)組來存儲這個(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算法生成最小生成樹</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)?和í邊??!?quot;);</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)?不?存?在ú?!?quot;);</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)使用說明</b></p><p>  通過文字和主要功能截圖的方式,大致說明系統(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)最小生成樹:</p><p>  E,輸入5:查找兩點(diǎn)之間最短路徑:</p><p><b>  當(dāng)輸入點(diǎn)不存在時(shí):</b></p><p>  課程設(shè)計(jì)中遇到的問題及解決方法</p><p>  1,問題:在添加邊或者點(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,問題

64、:本想用棧的先進(jìn)后出來刪除已經(jīng)訪問過的點(diǎn),但發(fā)現(xiàn)棧只可以用peek()的方法返回頂部的對象,不可刪除</p><p>  解決方法:int v = getAdjUnvisitedVertex(getIndex(thestack.Peek().vname));</p><p>  if (v == -1)</p><p>  thestack.Pop();</p

65、><p>  問題:在深度遍歷時(shí)如何判斷節(jié)點(diǎ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>  問題:進(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;//將沒有直接路徑的邊設(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>  //開始畫鄰接矩陣</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);//如果在列表中沒有找到,返回-1</p><p><b>  }</b></p><p>  //給已經(jīng)存在的點(diǎn)畫邊,并寫上權(quán)值,

81、因是無向的,所以對稱,只需寫一半</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)。請先添加一個(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)不存在,請重試。");</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)不存在,請重試。");</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,無時(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算法,生成最小生成樹 {</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)最小生成樹。");</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. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論