圖結(jié)構(gòu)習(xí)題答案

圖結(jié)構(gòu)習(xí)題答案第6章圖【例6-1】回答下列問題:(1)具有n個頂點得連通圖至少有多少條邊?(2)具有n個頂點得強連通圖至少有多少條邊?這樣得圖應(yīng)該就是什么形狀?(3)具有n個頂點得有向無環(huán)圖最多有多少條邊?解:(1)具有n個頂點得連通圖至少有n-1條邊。這就是一個與生成樹相關(guān)得問題。生成樹就是一個連通圖,它具有能夠連通圖中任何兩個頂點得最小邊集,任何一個生成樹都具有n-1邊。因此,具有n個頂點得連通圖至少有n-1條邊。(2)具有n個頂點得強連通圖至少有n條邊,這樣得圖就是一個由n個頂點構(gòu)成得環(huán)。強連通圖就是相對于有向圖而言得。由于強連通圖要求圖中任何兩個頂點之間能夠相互連通,因此每個頂點至少要有一條以該頂點為弧頭得弧與一條以該頂點為弧尾得弧,每個頂點得入度與出度至少各為1,即頂點得度至少為2,這樣根據(jù)圖得頂點數(shù)、邊數(shù)以及各項點得度三者之間得關(guān)系計算可得:邊數(shù)=2×n/2=n。(3)具有n個頂點得有向無環(huán)圖最多有n×(n—1)/2條邊。這就是一個拓撲排序相關(guān)得問題?！獋€有向無環(huán)圖至少可以排出一個拓撲序列,不妨設(shè)這n個頂點排成得拓撲序列為v1,v2,v3,…,vn,那么在這個序列中,每個頂點vi只可能與排在它后面得頂點之間存在著以vi為弧尾得弧,最多有n-i條,因此在整個圖中最多有(n-1)+(n-2)+…+2+1=n×(n-1)/2條邊。2.圖得存儲結(jié)構(gòu)常用得存儲結(jié)構(gòu)有鄰接矩陣與鄰接表。(1)鄰接矩陣表示法設(shè)G＝(V,E)就是有n(n≥1)個頂點得圖。則G得鄰接矩陣就是按如下定義得n階方陣:0其它1當(Ｖ0其它1當(Ｖi,Vj)∈E或<Ｖi,Vj>∈E時cost[i,j]=0110101111010110A2=A1=011001000例如,圖6-1中G1,Ｇ20110101111010110A2=A1=011001000由鄰接矩陣得定義可知,無向圖得鄰接矩陣必定就是對稱陣;有向圖得鄰接矩陣不一定就是對稱得。根據(jù)鄰接矩陣,很容易判定任意兩個頂點之間就是否有邊相連。求各頂點得度也就是非常容易得。對于無向圖,頂點Vi得度就就是鄰接矩陣中第i行(或第j列)上非零元得個數(shù),即。對于有向圖,第i行中非零元得個數(shù)為頂點Vi得出度,而第i列上得非零元個數(shù)為頂點Vi得入度。(2)鄰接表表示法圖得鄰接鏈表存儲結(jié)構(gòu)就是一種順序分配與鏈式分配相結(jié)合得存儲結(jié)構(gòu)括兩個部分:一部分就是向量,另一部分就是鏈表。鄰接鏈表中得表頭部分就是向量,用來存儲n個表頭結(jié)點。向量得下標指示頂點得序號。例如,對于圖6-1中G1與G2,其鄰接鏈表如圖6-3所示。在無向圖得鄰接表中頂點vi得度就就是第i個鏈表中結(jié)點得個數(shù)。在有向圖中,第i個鏈表得結(jié)點數(shù)僅就是vi得出度,求vi得入度,必須查遍n個鏈表才能得出。(a)G1得鄰接表123332∧∧∧(b)G2得鄰接表圖6-3鄰接表312341(a)G1得鄰接表123332∧∧∧(b)G2得鄰接表圖6-3鄰接表312341∧2∧443322∧1∧<3,6>,<4,6>,<5,6>},請畫出圖G,并寫出其鄰接矩陣與鄰接表表示。解:圖G如圖6-4中得(a)所示,圖G得鄰接矩陣與鄰接表表示分別如圖(b)與(c)所示。對于這類問題,只要掌握了圖得概念與存儲結(jié)構(gòu)就可以做出正確得答案。通常情況下.對圖得頂點排列順序與各頂點得鄰接點排列順序并沒有特定要求,因此,在寫出鄰接矩陣與鄰接表表示時,只要按照某種排列順序畫出相應(yīng)得結(jié)構(gòu)圖就可以了。但應(yīng)該注意得就是,對于鄰接矩陣表示,如果頂點結(jié)點得順序不同,那么鄰接矩陣就不相同;對于鄰接表表示,如果頂點結(jié)點得順序或者鄰接點得順序不同,那么鄰接表就不相同。011100000010010011000001000011000000(b)圖6-4圖及其存儲結(jié)構(gòu)1(a)3011100000010010011000001000011000000(b)圖6-4圖及其存儲結(jié)構(gòu)1(a)34256(c)12645322354∧5∧6∧∧6∧6∧(1)畫出該無向圖;(2)根據(jù)鄰接表,分別寫出用DFS(深度優(yōu)先搜索)與BFS(廣度優(yōu)先搜索)算法從頂點V0開始遍歷該圖后所得到得遍歷序列。圖6-5圖得鄰接表存儲V6V0圖6-5圖得鄰接表存儲V6V0V1V5V3V4V223056043611∧2∧1∧210250∧6∧3∧4∧(1)該無向圖如圖6-6所示。v0v1v2v3v4v6v5圖6-6無向圖(2)根據(jù)該無向圖得鄰接表表示,從頂點V0開始得深度優(yōu)先遍歷序列為:V0、V2、V3、V1、V4、V6、V5。廣度優(yōu)先遍歷序列為V0、V2、V5、V6v0v1v2v3v4v6v5圖6-6無向圖從圖得邏輯結(jié)構(gòu)上來講,從圖中某個頂點開始得深度(或廣度)優(yōu)先遍歷序列不一定就是唯一得。這就是因為在邏輯結(jié)構(gòu)中,并沒有對每個頂點得所有鄰接點規(guī)定它們之間得先后順序,這樣在搜索算法中選取第—個鄰接點與下一個鄰接點時可能會有不同得結(jié)果。但就是在存儲結(jié)構(gòu)中,明確地給出了鄰接點得先后順序,這時深度優(yōu)先與廣度優(yōu)先遍歷序列就就是唯一得?！纠?-4】對于如圖6-8所示得帶權(quán)無向圖,用圖示說明:(1)利用Prim算法從頂點a開始構(gòu)造最小生成樹得過程;3e1fdcba3e1fdcbag97946218548圖6-8帶權(quán)無向圖解:(1)利用Prim算法從頂點a開始構(gòu)造最小生成樹得過程如圖6-9所示。aefdcbg初始狀態(tài)aefaefdcbg初始狀態(tài)aefdcbg連通e2aefdcbg連通g21aefdcbg連通d2133aefdcbg連通f2143aefdcbg連通b2146圖6-9用Prim算法構(gòu)造最小生成樹得過程3aefdcbg連通c21461aefdcbg初始狀態(tài)aaefdcbg初始狀態(tài)aefdcbg增加第2條邊11aefdcbg增加第1條邊13aefdcbg增加第5條邊21413aefdcbg增加第4條邊211aefdcbg增加第3條邊211圖6-10用Kruskal算法構(gòu)造最小生成樹得過程3aefdcbg增加第6條邊21461解:一個帶權(quán)無向圖得最小生成樹不一定就是唯一得。從Kruskal算法構(gòu)造最小生成樹得過程可以瞧出,當從圖中選擇當前權(quán)值最小得邊時,如果存在多條這樣得邊,并且這些邊與已經(jīng)選取得邊構(gòu)成回路,此時這些邊就不可能同時出現(xiàn)在一棵最小生成樹中,對這些邊得不同選擇結(jié)果可能會產(chǎn)生不同得最小生成樹。習(xí)題6一、單項選擇題1、在一個具有n個頂點得有向圖中,若所有頂點得出度數(shù)之與為s,則所有頂點得入度數(shù)之與為(1、A)。A、s B、s-1 C、s+1 D、n2、在一個具有n個頂點得有向圖中,若所有頂點得出度數(shù)之與為s,則所有頂點得度數(shù)之與為(2、D)。A、s B、s-1 C、s+1 D、2s3、在一個具有n個頂點得無向圖中,若具有e條邊,則所有頂點得度數(shù)之與為(3、D)。A、n B、e C、n+e D、2e4、在一個具有n個頂點得無向完全圖中,所含得邊數(shù)為(4、C)。A、n B、n(n-1) C、n(n-1)/2 D、n(n+1)/25、在一個具有n個頂點得有向完全圖中,所含得邊數(shù)為(5、B)。A、n B、n(n-1) C、n(n-1)/2 D、n(n+1)/26、在一個無向圖中,若兩頂點之間得路徑長度為k,則該路徑上得頂點數(shù)為(6、B)。A、k B、k+1 C、k+2 D、2k7、對于一個具有n個頂點得無向連通圖,它包含得連通分量得個數(shù)為(7、B)。A、0 B、1 C、n D、n+18、若一個圖中包含有k個連通分量,若要按照深度優(yōu)先搜索得方法訪問所有頂點,則必須調(diào)用(8、A)次深度優(yōu)先搜索遍歷得算法。A、k B、1 C、k-1 D、k+19、若要把n個頂點連接為一個連通圖,則至少需要(9、C)條邊。A、n B、n+1 C、n-1 D、2n10、在一個具有n個頂點與e條邊得無向圖得鄰接矩陣中,表示邊存在得元素(又稱為有效元素)得個數(shù)為(10、D)。A、n B、ne C、e D、2e11、在一個具有n個頂點與e條邊得有向圖得鄰接矩陣中,表示邊存在得元素個數(shù)為(11、C)。A、n B、ne C、e D、2e12、在一個具有n個頂點與e條邊得無向圖得鄰接表中,邊結(jié)點得個數(shù)為(12、D)。A、n B、ne C、e D、2e13、在一個具有n個頂點與e條邊得有向圖得鄰接表中,保存頂點單鏈表得表頭指針向量得大小至少為(13、A)。A、n B、2n C、e D、2e14、在一個無權(quán)圖得鄰接表表示中,每個邊結(jié)點至少包含(14、B)域。A、1 B、2 C、3 D、415、對于一個有向圖,若一個頂點得度為k1,出度為k2,則對應(yīng)鄰接表中該頂點單鏈表中得邊結(jié)點數(shù)為(15、B)。A、k1 B、k2 C、k1-k2 D、k1+k216、對于一個有向圖,若一個頂點得度為k1,出度為k2,則對應(yīng)逆鄰接表中該頂點單鏈表中得邊結(jié)點數(shù)為(16、C)。A、k1 B、k2 C、k1-k2 D、k1+k217、對于一個無向圖,下面(17、A)種說法就是正確得。A、每個頂點得入度等于出度 B、每個頂點得度等于其入度與出度之與C、每個頂點得入度為0 D、每個頂點得出度為018、在一個有向圖得鄰接表中,每個頂點單鏈表中結(jié)點得個數(shù)等于該頂點得(18、A)。A、出邊數(shù) B、入邊數(shù) C、度數(shù) D、度數(shù)減119、若一個圖得邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點A開始對該圖進行深度優(yōu)先搜索,得到得頂點序列可能為(19、B)。A、A,B,C,F,D,E B、A,C,F,D,E,BC、A,B,D,C,F,E D、A,B,D,F,E,C20、若一個圖得邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點A開始對該圖進行廣度優(yōu)先搜索,得到得頂點序列可能為(20、D)。A、A,B,C,D,E,F B、A,B,C,F,D,EC、A,B,D,C,E,F D、A,C,B,F,D,E21、若一個圖得邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點1開始對該圖進行深度優(yōu)先搜索,得到得頂點序列可能為(21、A)。A、1,2,5,4,3 B、1,2,3,4,5C、1,2,5,3,4 D、1,4,3,2,522、若一個圖得邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點1開始對該圖進行廣度優(yōu)先搜索,得到得頂點序列可能為(22、C)。A、1,2,3,4,5 B、1,2,4,3,5C、1,2,4,5,3 D、1,4,2,5,323、由一個具有n個頂點得連通圖生成得最小生成樹中,具有(23、B)條邊。A、n B、n-1 C、n+1 D、2n24、已知一個有向圖得邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},則由該圖產(chǎn)生得一種可能得拓撲序列為(24、A)。A、a,b,c,d,e B、a,b,d,e,b C、a,c,b,e,d D、a,c,d,b,e二、填空題1、在一個圖中,所有頂點得度數(shù)之與等于所有邊數(shù)得________倍。1、22、在一個具有n個頂點得無向完全圖中,包含有________條邊,在一個具有n個頂點得有向完全圖中,包含有________條邊。2、n(n-1)/2,n(n-1)3、假定一個有向圖得頂點集為{a,b,c,d,e,f},邊集為{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},則出度為0得頂點個數(shù)為________,入度為1得頂點個數(shù)為________。3、2,44、在一個具有n個頂點得無向圖中,要連通所有頂點則至少需要________條邊。4、n-15、表示圖得兩種存儲結(jié)構(gòu)為__________與__________。5、鄰接矩陣,鄰接表6、在一個連通圖中存在著________個連通分量。6、17、圖中得一條路徑長度為k,該路徑所含得頂點數(shù)為________。7、k+18、若一個圖得頂點集為{a,b,c,d,e,f},邊集為{(a,b),(a,c),(b,c),(d,e)},則該圖含有________個連通分量。8、39、對于一個具有n個頂點得圖,若采用鄰接矩陣表示,則矩陣大小至少為________________。9、n,n10、對于具有n個頂點與e條邊得有向圖與無向圖,在它們對應(yīng)得鄰接表中,所含邊結(jié)點得個數(shù)分別為________與________。10、2e,e11、在有向圖得鄰接表與逆鄰接表表示中,每個頂點鄰接表分別鏈接著該頂點得所有________與________結(jié)點。11、出邊,入邊12、對于一個具有n個頂點與e條邊得無向圖,當分別采用鄰接矩陣與鄰接表表示時,求任一頂點度數(shù)得時間復(fù)雜度分別為________與________。12、O(n),O(e/n)13、假定一個圖具有n個頂點與e條邊,則采用鄰接矩陣與鄰接表表示時,其相應(yīng)得空間復(fù)雜度分別為________與________。13、O(n2),O(n+e)14、一個圖得邊集為{(a,c),(a,e),(b,e),(c,d),(d,e)},從頂點a出發(fā)進行深度優(yōu)先搜索遍歷得到得頂點序列為____________,從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到得頂點序列為____________。14、acdeb,acedb(答案不唯一)15、一個圖得邊集為{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},從頂點a出發(fā)進行深度優(yōu)先搜索遍歷得到得頂點序列為____________,從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到得頂點序列為____________。15、acfebd,acefbd(答案不唯一)16、圖得________優(yōu)先搜索遍歷算法就是一種遞歸算法,圖得________優(yōu)先搜索遍歷算法需要使用隊列。 16、深度,廣度17、對于一個具有n個頂點與e條邊得連通圖,其生成樹中得頂點數(shù)與邊數(shù)分別為________與________。17、n,n-118、若一個連通圖中每個邊上得權(quán)值均不同,則得到得最小生成樹就是________(唯一/不唯一)得。 18、唯一19、根據(jù)圖得存儲結(jié)構(gòu)進行某種次序得遍歷,得到得頂點序列就是__(唯一/不唯一)得。19、唯一20、假定一個有向圖得邊集為{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},對該圖進行拓撲排序得到得頂點序列為________。 20、aebdcf(答案不唯一)三、應(yīng)用題1、對于一個無向圖6-11(a),假定采用鄰接矩陣表示,試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索遍歷得到得頂點序列與按廣度優(yōu)先搜索遍歷得到得頂點序列。注:每一種序列都就是唯一得,因為都就是在存儲結(jié)構(gòu)上得到得。1、深度優(yōu)先搜索序列:0,1,2,8,3,4,5,6,7,9廣度優(yōu)先搜索序列:0,1,4,2,7,3,8,6,5,92、對于一個有向圖6-11(b),假定采用鄰接表表示,并且假定每個頂點單鏈表中得邊結(jié)點就是按出邊鄰接點序號從大到小得次序鏈接得,試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索遍歷得到得頂點序列與按廣度優(yōu)先搜索遍歷得到得頂點序列。注:每一種序列都就是唯一得,因為都就是在存儲結(jié)構(gòu)上得到得。圖6-110165948372(a)603451278(b)圖6-110165948372(a)603451278(b)廣度優(yōu)先搜索序列:0,4,3,1,7,5,6,2,83、已知一個無向圖得鄰接矩陣如圖6-12(a)所示,試寫出從頂點0出發(fā)分別進行深度優(yōu)先與廣度優(yōu)先搜索遍歷得到得頂點序列。3、深度優(yōu)先搜索序列:0,2,3,5,6,1,4廣度優(yōu)先搜索序列:0,2,3,5,6,1,44、已知一個無向圖得鄰接表如圖6-12(b)所示,試寫出從頂點0出發(fā)分別進行深度優(yōu)先與廣度優(yōu)先搜索遍歷得到得頂點序列。(a)(b)圖6-124、深度優(yōu)先搜索序列:0,3,6,4,1,5,2(a)(b)圖6-12廣度優(yōu)先搜索序列:0,3,2,6,5,4,15、已知圖6-13所示得一個網(wǎng),按照Prim方法,從頂點1出發(fā),求該網(wǎng)得最小生成樹得產(chǎn)生過程。(a)V1V2V3V4V5V6(a)V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V750(c)V1V2V3V4V5V6V7(b)V1V2V3V4V5V6V7504045504230V1V2V3V4V5V6V7504045504230(h)圖6-16V1V2V3V4V5V6V75040504230(g)V1V2V3V4V5V6V750405030(f)V1V2V3V4V5V6V75040(d)V1V2V3V4V5V6V7504050(e)圖6-13V1V2V3V4V5V6圖6-13V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V7(a)30V1V2V3V4V5V6V7V1V2V3V4V5V6V7(a)30V1V2V3V4V5V6V7(b)3040V1V2V3V4V5V6V7(c)304042圖6-17V1V2V3V4V5V6V7(e)3040424550V1V2V3V4V5V6V7(f)304042455050V1V2V3V4V5V6V7(d)30404245(a)有向帶權(quán)圖V1V0V5V4(a)有向帶權(quán)圖V1V0V5V4V3V25106030100502010∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞(b)帶權(quán)鄰接矩陣圖6-14有向帶權(quán)圖及其鄰接矩陣終點從v0到各終點得D值與最短路徑得求解過程

i=1i=2i=3i=4i=5

V1∞∞∞∞∞無V210(v0,v2)V3∞60(v0,v2,v3)50(v0,v4,v3)V430(v0,v4)30(v0,v4)V5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)VjV2V4V3V5

S{v0,v2}{v0,v2,v4}{v0,v2,v3,v4}{v0,v2,v3,v4,v5}

8、圖6-15給出了一個具有15個活動、11個事件得工程得AOE網(wǎng),求關(guān)鍵路徑。v1v5v3v8v11v9v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6v6v7v4v2圖6-15a1=3a3=2a4=1a7=6a8=8a11=7a12=4a6=5a10=2①事件得最早發(fā)生時間ve[k]。ve(1)=0ve(2)=3ve(3)=4ve(4)=ve(2)+2=5ve(5)=max{ve(2)+1,ve(3)+3}=7ve(6)=ve(3)+5=9ve(7)=max{ve(4)+6,ve(5)+8}=15ve(8)=ve(5)+4=11ve(9)=max{ve(8)+10,ve(6)+2}=21ve(10)=max{ve(8)+4,ve(9)+1}=22ve(11)=max{ve(7)+7,ve(10)+6}=28②事件得最遲發(fā)生時間vl[k]。vl(11)=ve(11)=28vl(10)=vl(11)-6=22vl(9)=vl(10)-1=21vl(8)=min{vl(10)-4,vl(9)-10}=11vl(7)=vl(11)-7=21vl(6)=vl(9)-2=19vl(5)=min{vl(7)-8,vl(8)-4}=7vl(4)=vl(7)-6=15vl(3)=min{vl(5)-3,vl(6)-5}=4vl(2)=min{vl(4)-2,vl(5)-1}=6vl(1)=min{vl(2)-3,vl(3)-4}=0③活動ai得最早開始時間e[i]與最晚開始時間l[i]?；顒觓1e(1)=ve(1)=0l(1)=vl(2)-3=3活動a2e(2)=ve(1)=0l(2)=vl(3)-4=0活動a3e(3)=ve(2)=3l(3)=vl(4)-2=13活動a4e(4)=ve(2)=3l(4)=vl(5)-1=6活動a5e(5)=ve(3)=4l(5)=vl(5)-3=4活動a6e(6)=ve(3)=4l(6)=vl(6)-5=14活動a7e(7)=ve(4)=5l(7)=vl(7)-6=15活動a8e(8)=ve(5)=7l(8)=vl(7)-8=13活動a9e(9)=ve(5)=7l(9)=vl(8)-4=7活動a10e(10)=ve(6)=9l(10)=vl(9)-2=19活動a11e(11)=ve(7)=15l(11)=vl(11)-7=21活動a12e(12)=ve(8)=11l(12)=vl(10)-4=18活動a13e(13)=ve(8)=11l(13)=vl(9)-10=11活動a14e(14)=ve(9)=21l(14)=vl(10)-1=21活動a15e(15)=ve(10)=22l(15)=vl(11)-6=22④最后,比較e[i]與l[i]得值可判斷出a2,a5,a9,a13,a14,a15就是關(guān)鍵活動,關(guān)鍵路徑如圖6-18所示。v1v5v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6圖6-181、編寫一個算法,求出鄰接矩陣表示得無向圖中序號為numb得頂點得度數(shù)。intdegree1(Graph&