數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題-資料下載頁
2025-03-25 03:01本頁面
【正文】 =2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（4）是否存在某項活動，當(dāng)其提高速度后能使整個工程縮短工期？圖79五、算法設(shè)計題1．假設(shè)圖G采用鄰接表存儲，分別設(shè)計實現(xiàn)以下要求的算法：（1）求出圖G中每個頂點的入度。（2）求出圖G中每個頂點的出度（3）求出圖G中出度最大的一個頂點，輸出該頂點的編號。（4）計算圖G中出度為0的頂點數(shù)。（5）判斷圖G中是否存在邊i,j。2．假設(shè)圖G采用鄰接矩陣存儲，分別設(shè)計實現(xiàn)以下要求的算法：（1）求出圖G中每個頂點的入度。（2）求出圖G中每個頂點的出度（3）求出圖G中出度最大的一個頂點，輸出該頂點的編號。（4）計算圖G中出度為0的頂點數(shù)。（5）判斷圖G中是否存在邊i,j。3．設(shè)計一個將鄰接表轉(zhuǎn)換為鄰接矩陣的算法。4．一個連通圖采用鄰接表作為存儲機構(gòu)，設(shè)計一個算法實現(xiàn)從頂點v出發(fā)的深度優(yōu)先遍歷的非遞歸過程。5．設(shè)計一個算法，求不帶權(quán)無向連通圖G中距離頂點v的最遠頂點。6．設(shè)計一個算法，判斷無向圖G是否是一棵樹，若是樹，返回1；否則返回0。7．假設(shè)圖采用鄰接表存儲，分別寫出基于DFS和BPS遍歷的算法來判別頂點i和頂點j（i!=j）之間是否有路徑。8．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷無向圖G是否連通，若連通則返回1；否則返回0。9．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點u到v的長度為1的所有簡單路徑。10．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點u到v的所有簡單路徑。11．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，從如圖710所示的無向圖G中找出滿足如下條件的一條路徑：（1）給定起點vi和終點vj。（2）給定一組必經(jīng)點{7,9}，即輸出的路徑必須包含這些頂點。（3）給定一組必避點{1,6}，即輸出的路徑不能包含這些頂點。01234567891011121314圖71012．假設(shè)圖G采用鄰接矩陣存儲，采用遍歷方法實際一個有向圖的根的算法。若有向圖中存在一個頂點v，從v可以通過路徑達達圖中其它所有頂點，則稱v為該有向圖的根。13．假設(shè)圖G采用鄰接矩陣存儲，設(shè)計一個算法判斷在給定的有向圖中是否存在一個簡單有向回路，若存在，則以頂點序列的方法輸出該回路（找到一條即可）。14．采用堆排序來實現(xiàn)Kruskal算法，并說明時間復(fù)雜度O(elog2e)的理由。15．如圖711是一個城市連接圖，圖中權(quán)值表示兩城市之間的里程（單位為100km），現(xiàn)要設(shè)計一條鐵路貫通所有城市（即從一個任一城市可以到達其他城市）。設(shè)計一個算法，求出最小代價。假設(shè)每1km的鐵路造價為1000萬元。6364255651103452 圖711 城市連通圖16．利用狄克斯特拉算法，設(shè)計一個可產(chǎn)生從指定頂點出發(fā)的最小生成樹的算法。17．設(shè)計一個算法求圖的中心點。設(shè)v是有向圖G的一個頂點，把v的偏心度定義為：MAX{從w到v的最短距離|wV(G)}如果v是有向圖G中具有最小偏心度的頂點，則稱頂點v是G的中心點。18．假設(shè)圖G采用鄰接矩陣存儲，采用弗洛伊德算法設(shè)計一個求有向圖的根的算法。若有向圖中存在一個頂點v，從v可以通過路徑到達圖中其他所有頂點，則稱v為該有向圖的根。19．設(shè)計一個算法，判斷有向圖是否存在回路。20．對于一個使用鄰接表存儲的帶權(quán)有向圖G。試?yán)蒙疃葍?yōu)先搜索方法，對該圖中所有頂點進行逆向拓撲排序。若鄰接表的數(shù)據(jù)類型定義為AGraph，則算法的首部為：void dfs_topsort(AGraph *G) 若拓撲排序成功，表示圖中不存在環(huán)；否則表示圖中存在環(huán)。在這個算法中嵌套一個遞歸深度優(yōu)先搜索算法為：Dfs(AGaph G , int v)在遍歷圖的同時進行逆序拓撲排序，其中，v是頂點編號。（1）給出該圖的鄰接表定義（2）定義在算法中使用的全局輔助數(shù)組（3）寫出逆向拓撲排序的算法。21．假設(shè)AOE網(wǎng)以鄰接表方式存儲，設(shè)計一個算法求該AOE網(wǎng)的所有關(guān)鍵活動。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1