- 0 - 算法與數(shù)據(jù)結(jié)構(gòu)課程項目設(shè)計方案 一、課設(shè)目的與要求 本次課設(shè)主要是圖的基本操作與應(yīng)用，共包括四個部分：有向圖的基本操作與應(yīng)用、無向圖的基本操作與應(yīng)用、有向網(wǎng)的基本操作與應(yīng)用、無向網(wǎng)的基本操作與應(yīng)用。 測試文件 (給出 。 * # n; n) : G); : : n; LG,n); : n; LG,n); n!=5) n; n) : G); : : G); n; G,n); : G); G); n!=5) n; n) : G); : : n!=4) n; n) : G); : : : G); n; G,n); : G); G); n!=6) n; n) : ; : ; : ; : ; n!=5) ,p- p=p- 算法運行結(jié)果如下圖所示： 在遍歷時，對圖中每個頂點至多訪問一次 為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結(jié)構(gòu)。對于 當用鄰接矩陣作其存儲結(jié)構(gòu)時，深度遍歷圖 的時間復(fù)雜度為 O(而當以鄰接表作其存儲結(jié)構(gòu)時，深 - 8 - 度優(yōu)先遍歷圖的時間復(fù)雜度為 O(n+e)。 廣度優(yōu)先遍歷 類似于樹的層次遍歷。其基本思想是：從圖中某頂點 訪問了 后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復(fù)上述過程，直到圖中所有頂點都被訪問到 為止。 以鄰接表作為圖的存儲結(jié)構(gòu)的廣度 優(yōu)先遍歷算法如下： ,v) ; p; ); v=1; %d,%c,v,v ,v); ) , p=p) if(p-=1) p-1; %d,%c,p-p- ,p- p=p- 算法運行結(jié)果如下圖所示： - 9 - * #G) i,j,c; 請輸入頂點 :); i=1;ii; i=1;iij; ij=1; ji=1; i=1;iii i=1;終點序號 :,i); sd; p=(); q=(); p-d; q-s; p-s /*sp; - 11 - q-d /*dq; 算法運行結(jié)果如下圖所示： ) i; p; 圖 的鄰接表表示如下 :n); i=1;i,i,i p=ip!= %d ,p- p=p- n); 0; ,v) p; v=1; %d,%c,v,v p=vp) p- ,p- - 12 - p=p- ,v) ; p; ); v=1; %d,%c,v,v ,v); ) , p=p) if(p-=1) p-1; %d,%c,p-p- ,p- p=p- 三 、無向網(wǎng)的基本操作與應(yīng)用 無向圖的基本操作與應(yīng)用包括用鄰接矩陣和鄰接表創(chuàng)建無向網(wǎng)以及以鄰接矩陣為存儲結(jié)構(gòu)的 兩種算法求最小生成樹 (。 計方案 用 與構(gòu)造無向圖相似的的方式可以構(gòu)造出鄰接矩陣和鄰接表。無向網(wǎng)的鄰接矩陣可定義為： A i j = 中的邊或弧是或或若（反之G,i ,),(v j )v i , 其中， vi,弧 上的權(quán)值；表示 一個計算機允許的、大于所有邊上權(quán)值的數(shù)。 鄰接矩陣存儲結(jié)構(gòu)定義如下： #0 /*最大頂點數(shù)設(shè)為 20*/ /*頂點類型設(shè)為字符型 */ /*頂點表 */ /*鄰接矩陣 */ - 13 - /*圖中頂點數(shù)和邊數(shù) */ /*鄰接矩陣存儲的圖類型 */ 無向網(wǎng)的鄰接表構(gòu)造方法與無向圖的構(gòu)造方法相似，只需要在 表結(jié)點中加入權(quán)值 代碼如下： /鄰接點序號 w; /邊或狐上的權(quán) /頂點信息 /指向下一個邊結(jié)點 現(xiàn)過程 其實現(xiàn)過程同無向圖的實現(xiàn)過程類 似，其邊的輸入由由邊的兩個頂點和邊上的權(quán)組成 。用鄰接矩陣創(chuàng)建無向網(wǎng)的函數(shù)為 G)，用鄰接表創(chuàng)建無向網(wǎng)的函數(shù)為G)，其代碼參見頭文件 構(gòu)造最小生成樹可以有多種算法， 以下是 普里姆算法，克魯斯卡爾算法 的說明。 假設(shè) N=(V,E)是連通網(wǎng)， T=(U, 的頂點集合， 的邊集合。普里姆算法 的基本思想是：首先從集合 假設(shè)為 入集合 時 U=，然后所有 u U， v u,v) 取具有最小權(quán)值的邊 (u0,入集合 時將頂點 中。重復(fù)上述操作， 直到 U=時 T=(U, 為實現(xiàn) 設(shè)置一個輔助數(shù)組 錄從 每個頂點 輔助數(shù)組中存在一個相應(yīng)分量 它包括兩個域： 中 中的頂點， /*該邊依附于集合 ; /*該邊的權(quán)值 */ 算法中將第 設(shè)為 )并入集合 i實現(xiàn) (即用 i表示頂點 在 i表示 在 ；選取 最小權(quán)值的邊，通過在所有 i0(的 i選擇最小的值來實現(xiàn)。 不妨設(shè)無向網(wǎng)采用鄰接矩陣存儲 ()，若存在分量 i0，ii，表示頂點 j已并入 (i, j)是最小 - 14 - 生成樹中的一條邊。 初始狀態(tài)時， U= (，初始 ，數(shù) 組的其他各分量的 ui,U,每選取一條邊，設(shè)置 表示頂點 中。由于頂點 后，這兩個集合的內(nèi)容發(fā)生了變化，就需依據(jù)具體情況更新數(shù)組 后 當無向網(wǎng)采用鄰接矩陣存儲時， ,v) i,j,k,i=1;i請輸入頂點 :); i=1;ii; i=1;iijw; ij=w; ji=w; i=1;iii i=1;終點序號，權(quán)值 :,i); sdw; p=(); q=(); p-d; q-s; p-w=w; q-w=w; p-s /*sp; q-ddq; 算法運行結(jié)果如下圖所示： ,v) - 19 - i,j,k,i=1;i; p=p- s); i=1; k=p-kks,k); if(請輸入頂點 :); i=1;ii; i=1;iij; ij=1; i=1;iii i=1;終點序號 :,i); sd; p=(); p-d; p-s /*sp; 算法運行結(jié)果如下圖所示： - 24 - ) i,k,v,; s; p; i=1; p=p- s); i=1; k=p-kk - 25 - s,k); if(表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。 用鄰接表創(chuàng)建有向圖時僅創(chuàng)建一個結(jié)點，其前驅(qū)為弧尾頂點，后記為弧頭頂點。輸入時還應(yīng)加上弧上的權(quán) w。 用鄰接矩陣創(chuàng)建有向網(wǎng)的函數(shù)為 G)，用鄰接表創(chuàng)建有向網(wǎng)的函數(shù)為 G)，其代碼參見頭文件 向網(wǎng)應(yīng)用的實現(xiàn) 從一個頂點到其余各頂點的最短路徑 從某個源點到其余各頂點的最短路徑又稱為單源最短路徑。迪杰斯特拉提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法，又稱“貪心”算法。 算法的基本思想是：把圖中的頂點分成兩個集合 ，集合 合 最短路徑長度遞增的次序逐個將 中，直到從源點出發(fā)可以到達的所有頂點都在 為實現(xiàn)算法，引入一個輔助結(jié)構(gòu)數(shù)組 來存放源點 有兩個域：存儲該頂點當 前最短路徑長度的 從 i則為。而i(i!=0)。顯然長度為 iii=1,2, ,路徑就是從 路徑為 (v0, 假設(shè)下一條最短路徑的終點為 么該路徑或者是弧 (v0,或者是中間只經(jīng)過集合為假若此路徑上除 頂點不在集合 明存在一條終點不在 與我們按路徑長度遞增的順序產(chǎn)生最短路徑的前提相矛盾。因此，一般情況下，下一條長度次短的最短路徑的長度必是jiT 另引入一個數(shù)組 來標識頂點是否已經(jīng)確定最短路徑。 i=1,表明 26 - 短路徑已經(jīng)確定，即 S。 i=0，表明 T。當從集合 中，需要更新頂點 中任一頂點 如果jjk%c:%dn,v,i,i s); s,i); j=ij!= s,j); j=j s) s,k); ik+Dkj) Dij=Dik+Dkj; ij=k; ,D, ,i,j) k; k=ij; if(k=-1),i,k); T 其中， 為弧 上的權(quán)。 vli vli是指在不推遲整個工期的前提下 (即保證事件 ve(n)時刻發(fā)生的前提下 ),事件于 ve(n)減去 vln=ven - 31 - vli=vlj S 其中 eek 若活動 示，只有事件 動 以，活動 eek=eli e1k 在不推遲整個工程完成 的前提下，活動 由弧 表示活動 vlj減去活動 ： elk=vlj 把 elk=eek的活動 elii表示完成活動 即在不延遲工期的前提下活動 關(guān)鍵路徑的算法步驟為： (1)輸入 建立 (2)從源點 =0,按拓撲有序求其余各頂點的最早發(fā)生時間 vei(1 i如果得到的拓撲有序序列中頂點個數(shù) 小于網(wǎng)中頂點數(shù) n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止：否則執(zhí)行步驟 (3). (3)從匯點 vlve按逆拓撲有序求其余各頂點的最遲發(fā)生時間vli(i 2)。 (4)根據(jù)各頂點的 每條 弧 ee(s)和最遲開始時間 el(s)。若某條弧滿足條件 ee(s)=el(s),則為關(guān)鍵活動。 用頭結(jié)點中增加一個存儲相應(yīng)頂點的入度值域的特殊鄰接表作 關(guān)鍵路徑的算法如下： ,T) s; i,v,k,; p; s); i=1; p=p- i=1; k=p-kks,k); if(vev+p-wvek) vek=vev+p-w; ) j,k,v,ee,p; ; ); if(,&T)!= k=p-p-w; if(vlk k=p- - 33 - p-w; ee=vej; el=vlkif(%d,%d,%d,%d,%dn,j,k,ee, %c,%cn,jk 算法運行結(jié)果如下圖所示： 設(shè) 求關(guān)鍵路徑的時間復(fù)雜度為 O(n+e)。 * G) i,j,c,w; 請輸入頂點 :); i=1;ii; i=1;iijw; ij=w; i=1;iii i=1;終點序號，權(quán)值 :,i); sdw; p=(); p-d; - 35 - p-w=w; p-s /*sp; 算法運行結(jié)果如下圖所示： ,v) i,j,k,s; i=1;i%c:%dn,v,i,i s); s,i); j=ij!= s,j); j=j s) s,k); ik+Dkj) Dij=Dik+Dkj; ij=k; ,D, ,i,j) k; k=ij; if(k=-1),i,k); ; p=p- i=1; k=p-kks,k); if(vev+p-wvek) vek=vev+p-w; ) j,k,v,ee,p; ; ); if(,&T)!= k=p-p-w; if(vlk k=p-p-w; ee=vej; el=vlkif(%d,%d,%d,%d,%dn,j,k,ee, %c,%cn,jk 六 、難點與收獲 我的模版是數(shù)據(jù)結(jié)構(gòu)老師給的，對于圖的基本操作，我是按她的思路進行擴展編寫而成的。 其他的程序是按書上的程序編寫的，由于存儲圖的數(shù)組的下標是從 1開始的， 所以之后的程序大多都要修改，在調(diào)試程序的過程中也遇到很多 問題 。 有些錯誤編譯器有提示，有的錯誤它根本不提示，你不知道錯在哪里，編譯能通過，連接也能通過，但就是不能輸出正確結(jié)果。因此需要不斷地調(diào)試才能找出問題所在。 以下列出的就是我遇到的 這樣的 問題以及我的解決方法。 （ 1） 3 - Q is 是一個指向隊列的指針，在調(diào)用隊列的初始化函數(shù) )時就出現(xiàn)了這個錯誤，其大意是 針 不初始化就不能使用。于是我加了這樣一條語句： Q=();這樣運行通過了，但新的問題又出現(xiàn)了，廣度遍歷的時候程序只輸出第一個結(jié)點，后面的結(jié)點就不輸 出了，我調(diào)試的時候發(fā)現(xiàn) 元素的確入隊了但出隊時顯示隊空，于時我判斷隊列的頭文件有問題。 于是我更換了隊列的頭文件，運行之后發(fā)現(xiàn)錯誤排除了。 (2)圖的基本操作及應(yīng)用 的 0未處理的異常 : 0讀取位置 0發(fā)生訪問沖突 . 在進行拓撲排序的時候出現(xiàn)了以上的錯誤。程序運行到語句 p=ip;p=p-終止。經(jīng)調(diào)試發(fā)現(xiàn) 開始取的，而圖的頂點列表中 0號單元沒有值，因此無法讀取數(shù)據(jù) 。 （ 3） 2664: “ : 不能將參數(shù) 2 從“ ”轉(zhuǎn)換為“ ” - 40 - 這是運行關(guān)鍵路徑的程序時出現(xiàn)的錯誤。在調(diào)用函數(shù) ,&T)時不能入 定義的棧是指針類型， 為了解決這個問題，我重載了入棧函數(shù) s,e)之后程序能正常運行了。 （ 4） 無法解析的外部符號 _ (?)， 1 個無法解析的外部命令。這兩個錯誤是在每對頂點最短路徑問題時出現(xiàn)的開始看了根本不知道是什么意思，最后仔細比較程序發(fā)現(xiàn)， 。 除此之外，還有一些問題也很棘手，那就是程序編譯和連接都能通過但不能輸出正確結(jié)果，這樣的錯誤最難纏，經(jīng)過調(diào)試后發(fā)現(xiàn)這些錯誤都出在一些小問題上，比如說循環(huán)語句的判斷語句不對造成死循環(huán)，或者循環(huán)的起始條件不對 ，僅循環(huán)一次就退出。又或者 在頭文件之后造成程序出現(xiàn)“未定義的標識符 的錯誤，頭文件包含 會出現(xiàn)函數(shù)重定義，函數(shù)已有一個文體的錯誤。總之，一切的不小心都會造成程序運行出錯。 通過這次課設(shè)，提高了我的編程能力，尤其是調(diào)試程序的能力。 我很少向老師求助，并不是我沒有問題，而是我習慣了自己解決問題。我相信通過自己實際操作更能夠提高能力，體會更深刻。 編程是 需要很好的耐心和極認真的態(tài)度，不認真 就會出現(xiàn)各種小錯誤，當然細微的小錯誤是無法避免的，比如敲代碼時