1、 實驗六 圖的應用及其實現(xiàn)（相關知識點：拓撲排序、關鍵路徑、最小生成樹和最短路徑） 一、實驗目的1進一步功固圖常用的存儲結構。2熟練掌握在圖的鄰接表實現(xiàn)圖的基本操作。3理解掌握AOV網、AOE網在鄰接表上的實現(xiàn)以及解決簡單的應用問題。二、實驗內容 一.基礎題目：(本類題目屬于驗證性的，要求學生獨立完成) 題目一：從鍵盤上輸入AOV網的頂點和有向邊的信息,建立其鄰接表存儲結構,然后對該圖拓撲排序,并輸出拓撲序列. 試設計程序實現(xiàn)上述AOV網的類型定義和基本操作,完成上述功能。測試數據：教材圖7.28 題目二：從鍵盤上輸入AOE網的頂點和有向邊的信息,建立其鄰接表存儲結構,輸出其關鍵路徑和關鍵路徑

2、長度。 試設計程序實現(xiàn)上述AOE網類型定義和基本操作,完成上述功能。測試數據：教材圖7.29 二.簡單應用題目：（ACM/ICPC訓練題，本類題目屬于設計性的，要求學生三人為一個團隊，分工協(xié)作完成)）【題目三】高速公路描述某國共有n個城市（n不超過200），有些城市之間直接有一條高速公路相連，高速公路都是雙向的，總共有m條。每條高速公路都有自己的載重限制，即載重最大值。通過車輛的載重不能超過公路的載重限制。如今我們想了解的是，從某一起點城市出發(fā)，到達目標城市，車輛最多能帶多重的貨物。 輸入輸入的第一行為兩個整數n和m。以下有m行，每行三個整數描述一條公路，分別是首尾相連的城市以及載重限制。然后

3、是一個整數k，即問題個數。接下來k行描述k個問題，每行兩個整數表示起點城市和目標城市。問題數不超過一百。輸出輸出包括k行，每行對應一個問題，輸出從起點到目標的最大載重量。如果兩城市間無路徑則輸出-1。樣例輸入33 1210023100135021323樣例輸出100100【題目四】 最短的旅程描述在Byteland有n個城市（編號從1到n），它們之間通過雙向的道路相連。Byteland的國王并不大方，所以，那里只有n -1條道路，但是，它們的連接方式使得從任意城市都可以走到其他的任何城市。一天，starhder到了編號為k的城市。他計劃從城市k開始，游遍城市m1，m2，m3，mj（不一定要按這

4、個順序旅游）。每個城市mi都是不同的，并且，也與k不同。 Starhder 就像每一個旅行家一樣，攜帶的錢總是有限的，所以，他要以最短的路程旅行完所有的城市（從城市k開始）。于是，他請你幫助計算一下，旅游完上述的城市最短需要多少路程。輸入第一行包含兩個整數，上文中的n和k，以一個空格隔開。（2= n =50000，1 = k =n），下面的n- 1行每行描述一條路，第i + 1行包含3個整數ai，bi，di，相鄰兩個數用一個空格隔開（1= ai,bi = n，1= di = 1000），ai和bi是用道路直接相連的城市編號，di是這條道路的長度。第n + 1行包含一個整數j，是starhder

5、要旅游的城市數（1= j = n - 1），接下來一行包含j個不同的整數m1，m2，mj，每兩個相鄰的整數用一個空格隔開，表示starhder想要去的城市。（1= mt=n，mt k）。輸出輸出只有一行，包含一個整數：starhder旅游的最短路程。樣例輸入42121422233213樣例輸出5【題目五】連通 OR 不連通描述：給定一個無向圖，一共n個點，請編寫一個程序實現(xiàn)兩種操作：D x y 從原圖中刪除連接x，y節(jié)點的邊。Q x y 詢問x，y節(jié)點是否連通 輸入第一行兩個數n,m（5=n=40000,1=m=100000）接下來m行，每行一對整數 x y （x,y=n）,表示x,y之間有邊

6、相連。保證沒有重復的邊。接下來一行一個整數 q（q=100000）以下q行每行一種操作，保證不會有非法刪除。輸出按詢問次序輸出所有Q操作的回答，連通的回答C，不連通的回答D樣例輸入331213235Q12D12Q12D32Q12樣例輸出CCD【題目六】 Sort ProblemAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For exa

7、mple, the sorted sequence A, B, C, D implies that A B, B C and C D. in this problem, we will give you a set of relations of the form A B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line c

8、ontaining two positive integers n and m. the first value indicated the number of objects to sort, where 2 = n = 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A B which will be given in this prob

9、lem instance. 1 = m = 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.【

10、Output】For each problem instance, output consists of one line. This line should be one of the following three:Sorted sequence determined: y y y y.Sorted sequence cannot be determined.Inconsistency found.y y y y is the sorted, ascending sequence.Sample Input Sample Output 4 6 Sorted sequence determin

11、ed: A B C D.AB Inconsistency found.AC Sorted sequence cannot be determined.BCCDBDAB3 2ABBA26 2AZDS0 0設計要求：（上述題目可任選一個）1、上機前，認真學習教材，熟練掌握AOV網、AOE網的構造和拓撲排序算法。2、上機前，認真獨立地寫出本次程序清單，流程圖，該程序包括圖類型以及每一種操作的具體的函數定義和主函數。有關算法分別參閱講義和參考教材事例圖的存儲結構定義#define INFINITY INT_MAX /定義無窮大#define MAX_VERTEX_NUM 20 typedef stru

12、ct ArcNode / 表結點定義 int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數組中的位置 struct node *nextarc; /鏈域，指示依附于vi的下一條邊或弧的結點， ArcNode typedef struct VNode /表頭結點 int vexdata; /存放頂點信息 struct ArcNode *firstarc; /指示第一個鄰接點VNode，AdjListMAX_VERTEX_NUM;typedef struct /圖的結構定義 AdjList vertices; /頂點向量 int vexnum, arcnum; GraphKind kind; / 圖的種類標志 MGraph;Int indegreeMAX_