09年自考《數據結構》各章要點二[4]

　　圖的存儲結構

　　·鄰接矩陣表示法用一個n階方陣來表示圖的結構是唯一的適合稠密圖

　　·無向圖鄰接矩陣是對稱的

　　·有向圖行是出度列是入度

　　建立鄰接矩陣算法的時間是O(n+n^+e)其時間復雜度為O(n^)

　　·鄰接表表示法用頂點表和鄰接表構成不是唯一的適合稀疏圖

　　·頂點表結構 vertex | firstedge指針域存放鄰接表頭指針

　　·鄰接表用頭指針確定

　　·無向圖稱邊表

　　·有向圖又分出邊表和逆鄰接表

　　·鄰接表結點結構為 adjvex | next時間復雜度為O(n+e)空間復雜度為O(n+e)

　　圖的遍歷

　　·深度優先遍歷借助於鄰接矩陣的列使用棧保存已訪問結點

　　·廣度優先遍歷借助於鄰接矩陣的行使用隊列保存已訪問結點

　　生成樹的定義若從圖的某個頂點出發可以系統地訪問到圖中所有頂點則遍歷時經過的邊和圖的所有頂點所構成的子圖稱作該圖的生成樹

　　最小生成樹圖的生成樹不唯一從不同的頂點出發可得到不同的生成樹把權值最小的生成樹稱為最小生成樹(MST)

[]  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22737.html