數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)成果(三

1、第七章 圖基本概念: 1). 無向圖: 在一個圖中, 如果任意兩個頂點構(gòu)成(vi, vj)屬于E是無序的, 即頂點之間的連線是沒有方向的, 則稱該圖是無向圖.v1v2; v1, v2稱為鄰接點2). 有向圖: v1 v2: 其中v1是弧尾; 為弧; v2為弧頭3). 無向完全圖: 在一個無向圖中, 如果任意兩頂點都有一條線直接相連, 則稱該圖為無向完全圖; 在一個含有n個頂點的無向完全圖中, 有n(n-1)/2條邊4). 有向完全圖: 任意兩頂點之間都有方向相反的兩條弧相連接, 有n(n-1)條弧5). 頂點的度: 無向: 指附于某頂點的邊數(shù).有向: 入度 ID: 出去的弧出度 OD: 進去的

2、弧6). 簡單路徑: 序列中除起點和重點外其余頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑.7). 子圖: 對于圖G = (V, E), G = (V, E), 若存在V是V的子集, E是E的子集, 且E中的邊所關(guān)聯(lián)的頂點均為V中, 則稱圖G是G的一個子圖.連通的: 在無向圖中, 如果從一個頂點vi到另一個頂點vj(i != j)有路徑, 則稱頂點vi到vj是連通的, 8)(無向).連通圖: 如果圖中任意兩頂點都是連通的, 則稱該圖是連通圖.一個連通圖的生成樹是一個極小連通子圖, 它含有圖中全部的頂點, 但只有足以構(gòu)成一棵樹的n-1條邊。連通分量: 無向圖的極大連通子圖稱為連通分量9(有向).強連通圖:

3、對于有向圖來說, 若圖中任意一對頂點vi和vj(i != j)均有從一個頂點vi到另一個頂點vj有路徑, 也有從vj到vi的路徑, 則稱該有向圖是強連通的.強連通分量: 有向圖中的極大強連通子圖稱做有向圖的強連通分量/選擇題1設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（ B ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2分析: 無向圖中頂點數(shù)確定, 邊數(shù)最多的是完全無向圖. 根據(jù)概念3完全無向圖的性質(zhì)得: 有有n(n-1)/2條邊2一個n個頂點的連通無向圖，其邊的個數(shù)至少為（ A ）。An-1 Bn Cn+1 Dnlogn；分析: 根據(jù)連通圖的定義: 任意兩頂點都是連通的；

4、 可知連通無向圖的邊個數(shù)至少為n-1, 3一個有n個結(jié)點的圖，最少有（ B ）個連通分量，最多有（ D ）個連通分量。A0 B1 Cn-1 Dn分析: 連通分量: 無向圖的極大連通子圖稱為連通分量, 若這n個結(jié)點都是連通的, 則此時連通分量是最少的, 為1個(n個頂點構(gòu)成一個連通分量). 當(dāng)這n個頂點沒有一條邊連接, 則此時連通分量是最多的, 為n個(n個頂點各自組成一個連通分量)4在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ B ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ C ）倍。A1/2 B2 C1 D4分析: 無向圖中, 一條邊連接了兩個頂點, 對于這兩個頂點

5、來說, 由于這條邊的存在, 所以這兩個頂點的度都自增1, 總度數(shù)增加2, 所以無向圖中, 一條邊可以創(chuàng)造兩個度. 所以邊永遠是度的兩倍.有向圖中, 一條弧連接兩個頂點, 對于指向的頂點來說, 入度加1, 對于指出的頂點來說, 出度加1, 所以有向圖中, 一條弧可以增加1個入度, 增加1個出度, 所以有向圖中, 入度之和和出度之和和弧數(shù)是1:1:1的關(guān)系;5下列哪一種圖的鄰接矩陣是對稱矩陣？（ B ）A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng)分析:/ c7-1.h 圖的數(shù)組(鄰接矩陣)存儲結(jié)構(gòu)(見圖7_1)#define INFINITY INT_MAX / 用整型最大值代替#define MA

6、X_VERTEX_NUM 26 / 最大頂點個數(shù)enum GraphKindDG,DN,UDG,UDN;/ 有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef structVRType adj; / 頂點關(guān)系類型。對無權(quán)圖，/ 用1(是)或0(否)表示相鄰否；/ 對帶權(quán)圖，則為權(quán)值InfoType *info; / 該弧相關(guān)信息的指針(可無)ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; / 二維數(shù)組struct MGraphVertexType vexsMAX_VERTEX_NUM; / 頂點向量AdjMatrix arcs; / 鄰接矩陣int ve

7、xnum,arcnum; / 圖的當(dāng)前頂點數(shù)和弧數(shù)GraphKind kind; / 圖的種類標(biāo)志;1) 如圖7-2所示, 無向圖鄰接矩陣中, 第i行的值為1表示有由vi發(fā)出的弧,比如01這個點為1表示v1和v2是有邊相連的, 由于無向圖中發(fā)向和被發(fā)向是相對的, 所以10這個點得值肯定也為1, 所以就會出現(xiàn)以對角線對稱的情況, 但圖7-210并不是1, 這是由于無向圖的鄰接矩陣的對稱性, 則可采用壓縮存儲的方式只存入矩陣的下三角(或上三角)元素. 這里就只是存入了上三角.2) 借助于鄰接矩陣容易判斷任意兩個頂點之間是否有邊(或弧)相連, 并容易求得各個頂點的度. 對于無向圖, 頂點vi的度是鄰

8、接矩陣中第i行(或第i列)的元素之和, 即:n-1TD(vi)=Aij(n=MAX_VERTEX_NUM) j=03) 對于有向圖，第i行的元素之和為頂點vi的出度OD(vi)，第j列的元素之和為頂點vj的入度ID(vj)。 網(wǎng)的鄰接矩陣可定義為 AOV-網(wǎng): 用頂點表示活動, 用弧表示活動間的優(yōu)先關(guān)系的有向圖稱為頂點表示活動的圖, 簡稱AOV-網(wǎng).(用于拓?fù)渑判?AOE-網(wǎng): AOE-網(wǎng)是一個帶權(quán)的有向無環(huán)圖, 其中, 頂點表示事件, 弧表示活動, 權(quán)表示活動持續(xù)的時間, 通常, AOE-網(wǎng)可用來評估工程的完成時間(關(guān)鍵路徑)6當(dāng)一個有N個頂點的圖用鄰接矩陣A表示時，頂點Vi的度是（ B ）

9、。A B C D+ 分析: 鄰接矩陣請查看選擇題第4題; 個人覺得問的是頂點vi的度; 說明應(yīng)該是個無向圖(有向圖應(yīng)該問出度和入度), 而無向圖的度數(shù)為第i行非零元的個數(shù)或第i列非零元的個數(shù),無向圖的度數(shù): 第i行非零元的個數(shù)或第i列非零元的個數(shù).有向圖的度數(shù): 出度: 第i行非零元個數(shù), 入度: 第i列非零元的個數(shù).7下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）：( B ) A深度優(yōu)先遍歷 B. 拓?fù)渑判?C. 求最短路徑 D. 廣度優(yōu)先遍歷分析: 拓?fù)渑判虻淖饔? 判斷能不能順利完工, 有沒有環(huán).拓?fù)渑判? 簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判?/p>

10、。離散數(shù)學(xué)中關(guān)于偏序和全序的定義： 偏序關(guān)系: 若集合X上的關(guān)系是R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關(guān)系。 全序關(guān)系: 設(shè)R是集合X上的偏序,如果對每個x,y屬于X必有xRy 或 yRx，則稱R是集合X上的全序關(guān)系。 注意： 若將圖中頂點按拓?fù)浯涡蚺懦梢恍?，則圖中所有的有向邊均是從左指向右的。 若圖中存在有向環(huán)，則不可能使頂點滿足拓?fù)浯涡颉?一個DAG的拓?fù)湫蛄型ǔ１硎灸撤N方案切實可行。拓?fù)渑判虻牟襟E: 1). 在有向圖中選一個沒有前驅(qū)的頂點且輸出之. 2). 從圖中刪除該頂點和所有以它為尾的弧. 重復(fù)上述兩步, 直到全部頂點均已輸出, 或者當(dāng)前圖中不存在無前驅(qū)的頂點為止,

11、后一種情況則說明有向圖中存在環(huán).8. 在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復(fù)雜度為( B )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)分析:只要記住如果用鄰接矩陣, 那么時間復(fù)雜度就是0(n2), 如果用鄰接表, 時間復(fù)雜度就是0(n + e);鄰接表: 鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu);具體請看書163頁/ c7-2.h 圖的鄰接表存儲結(jié)構(gòu)(見圖7_16)#define MAX_VERTEX_NUM 20enum GraphKindDG,DN,UDG,UDN; / 有向圖,有向網(wǎng),無向圖,無向網(wǎng)struct ArcNodeint adjvex;

12、 / 該弧所指向的頂點的位置ArcNode *nextarc; / 指向下一條弧的指針I(yè)nfoType *info; / 網(wǎng)的權(quán)值指針; / 表結(jié)點typedef structVertexType data; / 頂點信息ArcNode *firstarc; / 第一個表結(jié)點的地址，指向第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM; / 頭結(jié)點struct ALGraphAdjList vertices;/ 頂點表int vexnum,arcnum; / 圖的當(dāng)前頂點數(shù)和弧數(shù)int kind; / 圖的種類標(biāo)志;用我的話來說: ALGraph是用來存放圖的總

13、信息, 比如頂點數(shù)和弧數(shù)和圖的種類并且指向頂點表(AdjListMAX_VERTEX_NUM), 而VNode是用來存放頂點的信息; 并用*firstarc指向第一條依附于該頂點的弧的指針, 而ArcNode是用來存放依附于某個頂點的弧所指向的頂點的位置并且能夠指向下一個弧的指針. 具體請看下面這張圖和上面代碼中的注釋.最小生成樹: 構(gòu)造連通網(wǎng)的最小代價生成樹.求最小生成樹的普里姆算法 (效率不高, 但應(yīng)試解題快): 假設(shè)N=(V, E)是連接網(wǎng), TE是N上最小生成樹中邊的集合, 算法從U = u0(u0屬于V), TE = 開始, 重復(fù)執(zhí)行下列操作, 在所有u屬于U, v屬于V-U的邊(u

14、, v)屬于E中查找一條代價最小的邊(u0, v0)并入集合TE, 同時v0并入U, 直到U = V為止. 此時TE中必有n-1條邊, 則T = (V, TE)為N的最小生成樹.個人理解: 就是先找到一條最短的邊, 把這條邊的兩個頂點連起來, 再找與這兩個頂點相連的邊中最短的一條, 再把他們連接起來(這樣就找到了3個頂點), 再找與這3個頂點相連的邊中最短的一條,再把他們連起來, 直到所有頂點都被連起來為止. 只要注意不要連成環(huán)就行.9. 求解最短路徑的Floyd算法的時間復(fù)雜度為( D )。AO（n） B. O（n+c） C. O（n*n） D. O（n*n*n）分析: 求解最短路徑有兩個算

15、法: 一個是迪杰斯算法, 另一個就是Floyd弗洛伊德算法; 兩者的時間復(fù)雜度都是O(n3)10若一個有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓?fù)溆行蛐蛄校?A ）。 A存在 B不存在分析: 主對角線以下的元素均為零, 說明這個有向圖圖沒有環(huán)(如果下面有元素, 且以主對角線對稱的位置也有元素, 則表示有環(huán)), 沒有環(huán)則說明拓?fù)溆行蛐蛄写嬖?拓?fù)渑判虻膬?nèi)容請查看選擇題第7題;11一個有向無環(huán)圖的拓?fù)渑判蛐蛄校?B ）是唯一的。A一定 B不一定分析: 拓?fù)渑判虻男再|(zhì)請看選擇題第7題; 同一時刻沒有前驅(qū)的結(jié)點數(shù)可能不止一個, 這是拓?fù)渑判虻男蛄薪忉尣晃ㄒ坏牧?12. 在有向圖G的拓?fù)湫?/p>

16、列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（ D ）。 AG中有弧 BG中有一條從Vi到Vj的路徑 CG中沒有弧 DG中有一條從Vj到Vi的路徑分析: 若G中有一條從Vj到Vi的路徑, 那么就會構(gòu)成一個環(huán)了, 那就不是拓?fù)湫蛄辛?13. 在用鄰接表表示圖時，拓?fù)渑判蛩惴〞r間復(fù)雜度為( B )。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n)分析: 只要記住如果用鄰接矩陣, 那么時間復(fù)雜度就是0(n2), 如果用鄰接表, 時間復(fù)雜度就是0(n + e);鄰接表的具體信息請查看選擇題第8題14. 關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A ）。A從源點到匯點的最長路徑

17、 B從源點到匯點的最短路徑C最長回路 D最短回路分析: 關(guān)鍵路徑: 由于AOE-網(wǎng)中又些活動可以并行地進行, 所以完成工程的最短時間是從開始點到完成點的最大路徑的長度(這里所說的路徑長度是指路徑上各活動持續(xù)時間之和, 不是路徑上弧的數(shù)目), 路徑長度最長的路徑叫做關(guān)鍵路徑15下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ B ）。A關(guān)鍵活動不按期完成就會影響整個工程的完成時間B任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成D某些關(guān)鍵活動提前完成，那么整個工程將會提前完成分析: 關(guān)鍵路徑可能有多條，所以不是任何一個關(guān)鍵活動提前完成，那么整個工程將會提

18、前完成判斷題1. 有e條邊的無向圖，在鄰接表中有e個結(jié)點。（ 錯 ）分析: 無向圖在鄰接表中有2e個結(jié)點(a指向b, 同時b也會指向a);有向圖中有 e個結(jié)點(弧是單向的);2. 有向圖的鄰接矩陣是對稱的。（ 錯 ）分析:無向圖的鄰接矩陣才是對稱的.1 任何無向圖都存在生成樹。（ 錯 ）分析: 生成樹: 生成樹是一個連通圖G的一個極小的連通子圖. 包含圖G的所有頂點, 但只有n-1條邊, 并且是連通的. 生成樹可由遍歷過程中所經(jīng)過的邊組成, 深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。連通圖得到的是生成樹;不連通圖得到的是生成森林;4. 不同的求最小

19、生成樹的方法最后得到的生成樹是相同的.（ 錯 ）分析: 請查看選擇題第8題; 最小生成樹并不是唯一的, 所以即使是同一種求最小生成樹的方法最后得到的生成樹也是不同的;5. 有環(huán)圖也能進行拓?fù)渑判?。?錯 ）6. 關(guān)鍵路徑是AOE網(wǎng)中從源點到終點的最長路徑。（ 對 ）填空題1 具有10個頂點的無向圖，邊的總數(shù)最多為 45 。分析:無向圖: n(n-1)/2有向圖: n(n-1)2. 在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要 n 條弧。分析: 構(gòu)成一個環(huán);3. n個頂點的連通無向圖，其邊的條數(shù)至少為 n-1 。分析: 連通圖: 如果圖中任意兩頂點都是連通的, 則稱該圖是連通

20、圖.至少n-1條邊2 N個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有 無向圖：2(n-1)；有向圖：n 個非零元素。分析: 這題就是問N個頂點的連通圖有多少條邊的問題: 無向圖至少有n-1條邊; 有向圖至少有n條邊而鄰接矩陣中無向圖是對稱的, 所以矩陣中非零元素: 無向圖至少有2(n-1)個; 有向圖至少有n個5構(gòu)造連通網(wǎng)最小生成樹的兩個典型算法是 普里姆算法、克魯斯卡爾算法 。分析: 求最小生成樹的普里姆算法請查看選擇題第8題6. 有一個用于n個頂點連通帶權(quán)無向圖的算法描述如下：（1）設(shè)集合T1與T2，初始均為空；（2）在連通圖上任選一點加入T1；（3）以下步驟重復(fù)n-1次：a.在i屬于T1

21、，j不屬于T1的邊中選最小權(quán)的邊；b.該邊加入T2。上述算法完成后，T2中共有 n-1 條邊，該算法稱 普里姆算法 算法，T2中的邊構(gòu)成圖的 最小生成樹 。分析: 求最小生成樹的普里姆算法請查看選擇題第8題a.在i屬于T1，j不屬于T1的邊中選最小權(quán)的邊；指的是與T1相連的邊中權(quán)值最小的那條邊7AOV網(wǎng)中,頂點表示 活動 ,弧表示 活動間的優(yōu)先關(guān)系 。AOE網(wǎng)中,頂點表示 事件 ,弧表示 活動 。8. 當(dāng)一個AOV網(wǎng)用鄰接表表示時，可按下列方法進行拓?fù)渑判颉＃?）查鄰接表中入度為 零 的頂點，并進棧；（2）若棧不空，則輸出棧頂元素Vj，并退棧；查Vj的直接后繼Vk，對Vk入度處理，處理方法是

22、Vk的入度減1，如為零則進棧 ；（3）若?？諘r，輸出頂點數(shù)小于圖的頂點數(shù)，說明有 環(huán)路 ，否則拓?fù)渑判蛲瓿伞７治? 拓?fù)渑判虻牟襟E請查看選擇題第7題算法應(yīng)用題1、對n個頂點的無向圖，采用鄰接矩陣表示，如何判別下列有關(guān)問題 1）圖中有多少條邊？ 2）任意兩個頂點i和j是否有邊相連？ 3）任意一個頂點的度是多少？分析: 鄰接矩陣請查看選擇題第5題1). 矩陣中非零元的個數(shù)除以2(無向圖是對稱的);2). 查看第i行j列或則第j行i列是否為1(有邊相連則為1, 沒有則為0);3). 該頂點所在行或列所有非零元的個數(shù);2設(shè)G=(V,E)以鄰接表存儲，試寫出深度優(yōu)先和廣度優(yōu)先序列。分析:第一步: 如果鄰

23、接表中順序是按從小到大排的, 可以先化成鄰接矩陣清楚些:頂點v1v2v3v4v5v101110v210111v311010v411101v501010第二步:深度優(yōu)先遍歷: 從v1這一行開始從左到右找第一個非零元; 這里找到了v2; v1就不繼續(xù)查找了; 再到v2這一行查找找到了v1, 但是v1已經(jīng)遍歷過了; 所以繼續(xù)找, 這里找到了v3; v2就不繼續(xù)查找了; 再到v3行查找, 同理找到了v4; 再查找找到了v5所以深度優(yōu)先遍歷序列: v1, v2, v3, v4, v5;廣度優(yōu)先遍歷: 從v1這一行開始從左到右找非零元; 這里找到了v2, v3, v4; 再到v2這一行查找非零元; 找到了

24、v1, 但是v1已經(jīng)遍歷過了; 直到查到v5位置; 再到v3, v4行查找非零元;所以廣度優(yōu)先遍歷序列: v1, v2, v3, v4, v5;3、已知一無向圖的鄰接矩陣如下，求該圖從頂點V1出發(fā)的廣度優(yōu)先遍歷和深度優(yōu)先遍歷序列。 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0分析:分析方法同上;廣度優(yōu)先遍歷: v1, v3, v6, v4, v7, v2, v5;深度優(yōu)先遍歷: v1, v3, v4, v2, v7, v6, v5;4下圖表示一個

25、地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的代價，如何選擇能溝通每個城市且總代價最省的n-1條線路，畫出所有可能的選擇。分析: 最小生成樹的普里姆算法 (解答題中最方便的方法): 請查看選擇題第8題; 個人理解: 就是先找到一條最短的邊, 把這條邊的兩個頂點連起來, 再找與這兩個頂點相連的邊中最短的一條, 再把他們連接起來(這樣就找到了3個頂點), 再找與這3個頂點相連的邊中最短的一條,再把他們連起來, 直到所有頂點都被連起來為止. 只要注意不要連成環(huán)就行.這里就是先找到最短的是5這條邊, 所以把2, 3連接起來; 再找與2, 3相連的邊中最短的,找到了6, 把2, 6或則

26、3, 6連接起來; 再找與2, 3, 6相連的邊中最短的; 找到了11, 把2和4連接起來5、對下面的有向圖，試?yán)肈IJKSTRA算法從頂點1到其它頂點的最短路徑，并寫出執(zhí)行該算法過程中每次循環(huán)的狀態(tài)。v4v2v6v5v1v310101015430420215分析: 先從v1連接各點, 找到一條最短的, 這條就是v1到該點的最短路徑; 再從這一點開始連接其他各點, 該點到其他點得距離加上v1到該點的距離和v1到各點的距離比較; 如果比原來短了, 就消掉原來的線, 畫上新的線, 再到這些線中找一條最短的, 即為最短路徑6、對下面的AOE網(wǎng)，求出各項活動的最早開始時間e(i)和最遲開始時間l(i

27、)，并回答：工程完成的最短時間是多少？哪些是關(guān)鍵活動？v1V3V2V5V4V7V8V9V6v10a1 = 5a2 = 6a4 = 6a5 = 3a8 = 3a3 = 3a6 = 4a7 = 5a11 = 5a13 = 4a13 = 2a12 = 2a10 = 4a9 = 1分析:e(i)表示從前面到i弧尾(弧表示活動)得最長路徑; l(i)表示總的最長路徑減去從后面到i弧尾(弧表示活動)的最長路徑, 當(dāng)e(i) = l(i)時, e(i)即為關(guān)鍵活動最長路徑為: v1 - v3 - v4 - v7 - v9 - v10最短時間是24,e(1) = 0; l(1) = 1;e(2) = 0; l(2) = 0;e(3) = 5; l(3) =9;e(4) = 6; l(4) = 6;e(5) = 6; l(5) = 13;e(6) = 12; l(6) = 16;e(7) = 12; l(7) = 12;e(8) = 12; l(8) = 13;e(9) = 15; l(9)