數(shù)據(jù)結(jié)構(gòu)c語言描述圖(編輯修改稿)
2024-08-28 15:06 本頁面
【文章內(nèi)容簡介】 鄰接表表示相反 ， 求頂點的入度容易 ，而求頂點出度較難 。 在鄰接矩陣表示中 ， 很容易判定 (vi， vj)或＜ vi， vj＞是否是圖的一條邊 ， 只要判定矩陣中的第 i行第 j列上的那個元素是否為零即可；但是在鄰接表表示中 ， 需掃描第 i個邊表 ， 最壞情況下要耗費 O(n)時間 。 在鄰接矩陣中求邊的數(shù)目 e，必須檢測整個矩陣，所耗費的時間是0(n2)，與 e的大小無關(guān)；而在鄰接表表示中，只要對每個邊表的結(jié)點個數(shù)計數(shù)即可求得 e，所耗費的時間是 0(e+n)。因此，當(dāng) e＜＜ n2時，采用鄰接表表示更節(jié)省時間。 圖的遍歷 和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點出發(fā)順著邊可以訪問到該圖的所有頂點。然而，圖的遍歷比樹的遍歷復(fù)雜得多，這是因為圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了該頂點。為了避免重復(fù)訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設(shè)置一個布爾向量 visited[n]，它的初值為 false，一旦訪問了頂點 vi，便將 visited[i1]置為 TRUE。 深度優(yōu)先搜索 (DepthFirstSearch)遍歷類似于樹的前序遍歷。假設(shè)給定圖 G的初態(tài)是所有頂點均未訪問過，在 G中任選一頂點 vi為初始出發(fā)點，則深度優(yōu)先搜索可定義如下：首先，訪問出發(fā)點 vi，并將其標(biāo)記為已訪問過，然后，依次從 vi出發(fā)搜索 vi的每一個鄰接點vj,若 vj未曾訪問過，則以 vj為新的出發(fā)點繼續(xù)進(jìn)行深度優(yōu)先搜索。顯然上述搜索法是遞歸定義的，它的特點是盡可能先對縱深方向進(jìn)行搜索，故稱之為深度優(yōu)先搜索。例如，設(shè) x是剛訪問過的頂點，按深度優(yōu)先搜索方法，下一步將選擇一條從 x出發(fā)的未檢測過的邊(x， y)。若發(fā)現(xiàn)頂點 y已被訪問過，則重新選擇另一條從 x出發(fā)的未檢測過的邊。若發(fā)現(xiàn)頂點 y未曾訪問過，則沿此邊從 x到達(dá) y，訪問 y并將其標(biāo)記為已訪問過，然后從 y開始搜索，直到搜索完從 y出發(fā)的所有路徑，才回溯到頂點 x，然后再選擇一條從 x出發(fā)的未檢測過的邊。上述過程直至從 x出發(fā)的所有邊都已檢測過為止。此時，若 x不是初始出發(fā)點，則回溯到在 x之前被訪問過的頂點；若 x是初始出發(fā)點，則整個搜索過程結(jié)束。顯然這時圖 G中所有和初始出發(fā)點有路徑相通的頂點都已被訪問過。因此，若 G是連通圖，則從初始出發(fā)點開始的搜索過程結(jié)束，也就意味著完成了對圖 G的遍歷。 在該存儲結(jié)構(gòu)上執(zhí)行 DFS算法的過程如下：設(shè)初始出發(fā)點是 v1，則DFS（ 0）的執(zhí)行結(jié)果是訪問 v1，將其置上已訪問標(biāo)記，從 v1搜索到的第 1個鄰接點是 v2，因 v2未曾訪問過，故調(diào)用 DFS(1)。執(zhí)行DFS(1)，首先訪問 v2，將其標(biāo)記為已訪問過，然后從 v2搜索到的第 1個鄰接點是 vl，但 vl已訪問過，故繼續(xù)搜索到第 2個鄰接點 v4，v4未曾訪過，因此調(diào)用 DFS(3)。類似地分析，訪問 v4后調(diào)用DFS(7)，訪問 v：后調(diào)用 DPS(4)。執(zhí)行 DFS(4)時，在訪問 v5并作標(biāo)記后，從 v5搜索到的兩個鄰接點依次是 v2和 v8，因為它們均已被訪問過，所以 DFS(4)執(zhí)行結(jié)束返回，回溯到 v8。又因為 v8的兩個鄰接點已搜索過，故 DFS(7)亦結(jié)束返回，回溯到 v4。類似地由 v4回溯到 v2。 V2的鄰接點 vl和 v4已搜索過，但 v2的第 3個鄰接點 v5還尚未搜索，故接下來由 v2搜索到 v5，但因為 v5已訪問過，所以 DFS(1)也結(jié)束返回，回溯到 vl。 vl的第 1個鄰接點已搜索過，故繼續(xù)從 v1搜索到第 2個鄰接點 v3，因為 v3未曾訪問過，故調(diào)用 DFS(2)。類似地依次訪問 v3， v6， v7后，又由 v7依次回溯到 v6， v3， vl。此時， vl的所有鄰接點都已搜索過，故 DFS(0)執(zhí)行完畢。 寬度優(yōu)先搜索法 寬度優(yōu)先搜索 (BreadthFirstSearch)遍歷類似于樹的按層次遍歷 。 設(shè)圖 G的初態(tài)是所有頂點均未訪問過 ， 在 G中任選一頂點 2為初始出發(fā)點 ， 則寬度優(yōu)先搜索的基本思想是：首先訪問出發(fā)點 Vi， 接著依次訪問 vi的所有鄰接點 wl， w2， … ， wt， 然后 ， 再依次訪問與 wl，w2， … ， wt鄰接的所有未曾訪問過的頂點 ， 依此類推 ， 直至圖中所有和初始出發(fā)點 v有路徑相通的頂點都已訪問到為止 。 此時 ， 從vi開始的搜索過程結(jié)束 ， 若 G是連通圖則遍歷完成 。 顯然，上述搜索法的特點是盡可能先對橫向進(jìn)行搜索，故稱之為寬度優(yōu)先搜索。設(shè) x和 y是兩個相繼被訪問過的頂點，若當(dāng)前是以 x為出發(fā)點進(jìn)行搜索，則在訪問 x的所有未曾訪問過的鄰接點之后，緊接著是以 y為出發(fā)點進(jìn)行橫向搜索，并對搜索到的 y的鄰接點中尚未被訪問的頂點進(jìn)行訪問。也就是說，先訪問的頂點其鄰接點亦先被訪問。為此，需引進(jìn)隊列保存已訪問過的頂點。 最小生成樹 圖的生成樹不是唯一的 ， 從不同的頂點出發(fā)進(jìn)行遍歷 ，可以得到不同的生成樹 。 對于連通網(wǎng)絡(luò) G＝ (V， E)， 邊是帶權(quán)的 ， 因而 G的生成樹的各邊也是帶權(quán)的 。 我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán) ， 并把權(quán)最小的生成樹稱為 G的 最小生成樹 (Minimun Spanning Tree)。 生成樹和最小生成樹有許多重要的應(yīng)用。令圖 G的頂點表示城市，邊表示連接兩個城市之間的通訊線路。 n個城市之間最多可設(shè)立的線路
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1