數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題(參考版)
2025-03-28 03:01本頁(yè)面
【正文】 。（1）給出該圖的鄰接表定義（2）定義在算法中使用的全局輔助數(shù)組（3）寫(xiě)出逆向拓?fù)渑判虻乃惴āＨ羿徑颖淼臄?shù)據(jù)類(lèi)型定義為AGraph，則算法的首部為：void dfs_topsort(AGraph *G) 若拓?fù)渑判虺晒Γ硎緢D中不存在環(huán)；否則表示圖中存在環(huán)。20．對(duì)于一個(gè)使用鄰接表存儲(chǔ)的帶權(quán)有向圖G。若有向圖中存在一個(gè)頂點(diǎn)v，從v可以通過(guò)路徑到達(dá)圖中其他所有頂點(diǎn)，則稱(chēng)v為該有向圖的根。設(shè)v是有向圖G的一個(gè)頂點(diǎn)，把v的偏心度定義為：MAX{從w到v的最短距離|wV(G)}如果v是有向圖G中具有最小偏心度的頂點(diǎn)，則稱(chēng)頂點(diǎn)v是G的中心點(diǎn)。6364255651103452 圖711 城市連通圖16．利用狄克斯特拉算法，設(shè)計(jì)一個(gè)可產(chǎn)生從指定頂點(diǎn)出發(fā)的最小生成樹(shù)的算法。設(shè)計(jì)一個(gè)算法，求出最小代價(jià)。14．采用堆排序來(lái)實(shí)現(xiàn)Kruskal算法，并說(shuō)明時(shí)間復(fù)雜度O(elog2e)的理由。若有向圖中存在一個(gè)頂點(diǎn)v，從v可以通過(guò)路徑達(dá)達(dá)圖中其它所有頂點(diǎn)，則稱(chēng)v為該有向圖的根。（3）給定一組必避點(diǎn){1,6}，即輸出的路徑不能包含這些頂點(diǎn)。11．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，從如圖710所示的無(wú)向圖G中找出滿(mǎn)足如下條件的一條路徑：（1）給定起點(diǎn)vi和終點(diǎn)vj。9．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的長(zhǎng)度為1的所有簡(jiǎn)單路徑。7．假設(shè)圖采用鄰接表存儲(chǔ)，分別寫(xiě)出基于DFS和BPS遍歷的算法來(lái)判別頂點(diǎn)i和頂點(diǎn)j（i!=j）之間是否有路徑。5．設(shè)計(jì)一個(gè)算法，求不帶權(quán)無(wú)向連通圖G中距離頂點(diǎn)v的最遠(yuǎn)頂點(diǎn)。3．設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。2．假設(shè)圖G采用鄰接矩陣存儲(chǔ)，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。（3）哪些是關(guān)鍵活動(dòng)a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（4）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期？圖79五、算法設(shè)計(jì)題1．假設(shè)圖G采用鄰接表存儲(chǔ)，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。14．如圖79所示的AOE網(wǎng)，求：（1）每項(xiàng)活動(dòng)ai最早開(kāi)始時(shí)間e(ai)和最遲開(kāi)始時(shí)間l(ai)。表2 某工程各工序關(guān)系表工序代號(hào) A B C D E F G H I J K L M N所需時(shí)間 15 10 50 8 15 40 300 15 120 60 15 30 20 40先驅(qū)工作 A,B B C,D B E G,I E I F,I H,J,K L G完成如下各小題：（1）畫(huà)出相應(yīng)的AOE網(wǎng)（2）列出事件的最早發(fā)生時(shí)間，最遲發(fā)生時(shí)間。39822 127153426512 12 15131344313204圖77 一個(gè)有向圖 圖78一個(gè)有向圖 12．設(shè)圖78中的頂點(diǎn)表示村莊，有向邊代表交通路線(xiàn)，若要建立一家醫(yī)院，試問(wèn)建在哪個(gè)村莊能使個(gè)村莊總體交通代價(jià)最小。143256圖75 一個(gè)有向圖8．什么樣的圖其最小生成樹(shù)是惟一的？9．已知帶權(quán)連通圖G(V,E)鄰接表如圖76所示，請(qǐng)畫(huà)出該圖，并分別以深度優(yōu)先和廣度優(yōu)先遍歷該圖，寫(xiě)出遍歷中結(jié)點(diǎn)的序列，并畫(huà)出該圖的一棵最小生成樹(shù)，其中表結(jié)點(diǎn)的3個(gè)域各為：頂點(diǎn)號(hào)邊上所帶的權(quán)指針v1v2v3v4v54 4 ∧4 18 ∧5 22 ∧5 10 ∧1 161 122 12
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1