【正文】 } List。 typedef struct list{ Node * First。 struct node* Link。 typedef struct student T。 int age。 //學(xué)號(hào) 關(guān)鍵字 char name[20]。 //順序表 typedef int KeyType。 T Elements[MaxSize]。 typedef struct student T。 int age。 //學(xué)號(hào) 關(guān)鍵字 char name[20]。 查詢函數(shù) Search: 顯示記錄 輸入要查詢的學(xué)號(hào) 調(diào)用 SeqSearch2函數(shù)在有序表中查詢學(xué)生記錄 成功 y 順序表 查詢函數(shù) Search: 顯示記錄 輸入要查詢的學(xué)號(hào) 在有序表中查詢學(xué)生記錄 成功 y 鏈接表示 查詢學(xué)生記錄 typedef int KeyType。lst)。 } } 修改 lowcost和nearest的值 求下一條最小權(quán)值的邊 將頂點(diǎn) k加到生成樹上 將 源 點(diǎn) k加入到生成樹上 畫出給定圖的最小的生成樹，要求從頂點(diǎn) 1出發(fā)。 k=j。amp。 jn。 } } min=MaxNum。( lowcost[j] pW )){ lowcost[j]=pW。 if (( !mark[j] )amp。 p。 in。 mark[k]=TRUE。 } 程序的時(shí)間復(fù)雜度： O(n2) lowcost[k]=0。 mark[i]=FALSE。 in。 return 。 ENode *p。 void Prim(Graph g, int k, int *nearest, T* lowcost) { int i, j, min, n=。 如（ 2， 1， 5） : 邊 (2,1)的代價(jià)為 5， 其中 nearest[1]=2； lowcost[1]=5 它記錄當(dāng)前對(duì) v而言，與 生成樹上頂點(diǎn)相鄰的所有邊中權(quán)值最小者 。 如果 mark[v]=false,表示 v未加入生成樹 ，反之， v已選入。 ? nearest ? lowcost 設(shè) v是當(dāng)前尚未選入生成樹的頂點(diǎn)， nearest[v]中保存邊(u, v)在 生成樹上 的那個(gè)頂點(diǎn) u，邊 (u, v)是所有 u ? V’的 邊中 權(quán)值最小 的邊。 這時(shí) E’中必有 n1條邊， T=(V’,E’)是圖 G的一棵最小代價(jià)生成樹。 從初始狀態(tài)開始，重復(fù)執(zhí)行下列運(yùn)算： 在所有 u?V’， v?VV’的邊 (u,v)， (u,v)?E中找一條代價(jià)最小的邊 (u’,v’)， 邊 (u’,v’)并入集合 E’，將頂點(diǎn) v’并入集合 V’。 構(gòu)造最小代價(jià)生成樹的兩種算法： 普里姆算法（ Prim) 克魯斯卡爾算法 (Kruskal) 0 1 3 2 1 2 7 0 1 3 2 3 5 7 0 1 3 2 3 1 2 0 1 3 2 3 5 1 2 7 8 設(shè) G=(V,E)是帶權(quán)的連通圖， T=(V’,E’)是正在構(gòu)造中的生成樹。 一棵生成樹的代價(jià)是各條邊上的代價(jià)之和。已知每?jī)蓚€(gè)城市間架設(shè)線路的代價(jià)，問如何選擇 n1條線路，可以使總代價(jià)最??？ 基本概念 0 1 3 2 3 5 1 2 7 8 構(gòu)造一 個(gè)連通圖的最小代價(jià) 生成樹 。 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，請(qǐng)問：每個(gè)頂點(diǎn)的入度和出度，并給出從頂點(diǎn) 1出發(fā)的深度優(yōu)先遍歷和 寬度優(yōu)先遍歷序列。 如同二叉樹的遍歷算法，圖的 DFS和 BFS算法是最重要、最基本的算法，許多有關(guān)圖的算法都可以對(duì)它們稍加修改得到。 對(duì)于每個(gè)出隊(duì)的頂點(diǎn)，都要檢查其所有的鄰接點(diǎn)，對(duì)于無向圖每條邊被檢查 2次。 i++) if (!visited[i]) BFS(g, i, visited)。 for (i=0。 in。 int i, n=。q, wAdjVex)。 visited[wAdjVex]=TRUE。 w。q)。u)。q, v)。 printf(%d , v)。q, MaxNumVertices )。 Queue q。 BFS算法 采用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，其寬度優(yōu)先搜索的程序如下： include void BFS(Graph g, T v, BOOL *visited) { ENode *w。 （ 1）訪問頂點(diǎn) v的所有未訪問過的鄰接點(diǎn)時(shí)， 需將這些鄰接點(diǎn)保存在隊(duì)列中 。 圖中頂點(diǎn)以及遍歷時(shí)生成的邊所構(gòu)成的子圖稱為 寬度優(yōu)先搜索生成樹。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。 3 若圖中還有頂點(diǎn)未被訪問，則另選一個(gè)未訪問的頂點(diǎn)， 重新開始上述過程。 寬 度優(yōu)先遍歷 從圖中任一頂點(diǎn) v出發(fā)遍歷圖的 BFS算法的描述 : 1 訪問頂點(diǎn) v并打上標(biāo)記 。 } 4 ? 2 ? 1 ? 01 2 3 4 5 6 A B C D F G E 5 3 ? 4 3 0 0 ? 1 ? 2 ? 對(duì) V未標(biāo)記的鄰接點(diǎn)嵌套調(diào)用 DFS函數(shù) 對(duì)尚未標(biāo)記的頂點(diǎn)調(diào)用 DFS函數(shù) 時(shí)間分析： 深度優(yōu)先搜索算法對(duì)有向圖的每條邊只查看 1次，而對(duì)于無向圖，查看 2次。 in。 i++) visited[i]=FALSE。 for(i=0。 } void Traversal_DFS(Graph g) { BOOL visited[MaxSize]。 w。 printf(%d , v)。 void DFS(Graph g, int v, BOOL *visited) { ENode *w。 0 ? ? 2 ? 3 01 2 3 4 5 6 A B C D F G E 4 ? 1 ? 5 3 ? 4 0 2 ? (b) 圖 G的鄰接表 1 (a) 有向圖 G B F D E A C G B F D E A C G (c) 圖 G深度優(yōu)先搜索的生成森林 思考 :圖的 DFS序列是否惟一？ (指從同一頂點(diǎn)出發(fā) ) 圖中所有頂點(diǎn)，以及在遍歷時(shí)經(jīng)過的邊構(gòu)成的子圖，稱為圖的深度優(yōu)先搜索生成樹(dfs spanning tree)(或 生成森林 )。 (a) 有向圖 G B F D E A C G 對(duì)有向圖 G，從 A出發(fā) DFS，訪問的次序是 A,B,D,C；遍歷了所有從 A出發(fā)可到達(dá)的頂點(diǎn)，即 A的可達(dá)集。 如果是連通的無向圖或強(qiáng)連通的有向圖，上述 DFS算法必定可以系統(tǒng)地訪問圖中的全部頂點(diǎn)。 深度優(yōu)先搜索算法 從圖 G中某個(gè)頂點(diǎn) v出發(fā) ,深度優(yōu)先搜索 圖的 DFS算法如下： 訪問頂點(diǎn) v并打上標(biāo)記。 在搜索中遇到被標(biāo)記過的頂點(diǎn)則不再訪問它 。 算法開始時(shí) ， 所有頂點(diǎn)的標(biāo)志位清零 。 圖遍歷的方法 :深度優(yōu)先搜索 （類似于樹的先序遍歷）和 寬度優(yōu)先搜索 （類似于樹的按層次遍歷） 課堂提要 第 10章 圖 圖的基本概念 圖的存儲(chǔ)結(jié)構(gòu) 圖的遍歷 最小代價(jià)生成 樹 深度優(yōu)先遍歷 圖遍歷與樹遍歷的差異 : 從圖中任意一個(gè)頂點(diǎn)出發(fā)未必能到達(dá)其它所有頂點(diǎn)； 圖中存在回路時(shí)，又可能多次經(jīng)過同一個(gè)頂點(diǎn)。 return FALSE。 return TRUE。 else gA[u]=pNextArc。 p=pNextArc