．二部圖(bipartite graph) G=(VE)是一個能將其結點集V分為兩不相交子集V 和V=VV的無向圖使得V中的任何兩個結點在圖G中均不相鄰V中的任何結點在圖G中也均不相鄰
()．請各舉一個結點個數為的二部圖和非二部圖的例子
()．請用C或PASCAL編寫一個函數BIPARTITE判斷一個連通無向圖G是否是二部圖並分析程序的時間復雜度設G用二維數組A來表示大小為n*n(n為結點個數)請在程序中加必要的注釋若有必要可直接利用堆棧或隊列操作【浙江大學 八 (分)】
．我們可用破圈法求解帶權連通無向圖的一棵最小代價生成樹所謂破圈法就是任取一圈去掉圈上權最大的邊反復執行這一步驟直到沒有圈為止請給出用破圈法求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細算法並用程序實現你所給出的算法注圈就是回路
【復旦大學 六 (分)】
設圖用鄰接表表示寫出求從指定頂點到其余各頂點的最短路徑的Dijkstra 算法
要求()．對所用的輔助數據結構鄰接表結構給以必要的說明(分)
()．寫出算法描述(C類Pascal類C均可)(分)【南京理工大學 四 (分)】
類似本題的另外敘述有
()寫出求從某個源點到其余各頂點最短路徑的Dijkstra算法要求說明主要的數據結構及其作用最後針對所給有向圖利用該算法求V到各頂點的最短距離和路線即填寫下表【山東師范大學 六 (分)】
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23090.html
