Please enable JavaScript.
Coggle requires JavaScript to display documents.
7圖形結構 ((分支度(Degree) (入支度 (In-degree), 出支度 (Out-degree)), 無向圖形(Undirected…
7圖形結構
分支度(Degree)
入支度
(In-degree)
出支度
(Out-degree)
無向圖形(Undirected Graph)
有向圖形(Directed Graph) :
路徑
路徑長度(邊數)
簡單路徑(Simple)-可到達路徑
循環(cycle)
連通(Connected)
兩頂點有路徑相通
連通圖形(Connected Graph)
圖中任兩點連通
拓樸排序(Topological Sort)
AOV網路（Activity On Vertex NetWork）
有循環，拓樸順序就不存在
不只唯一
工作順序、選課
{1,2,3}選第1刪除
圖形表示法
相鄰矩陣
(Adjacency Matrix)
n個頂點，nxn矩陣
出支度 ->
入支度 |
無向圖
上/下三角(節省一半以上空間)
元素1為邊的2倍
:red_flag:相鄰的頂點記錄下來
相鄰串列
(Adjacency Lists)
:red_flag:利用鏈結串列將相鄰的頂點串在一起
加權圖形
(weight)
邊上附加數值 自己0，否無限
圖形走訪
(Traversals)
:red_flag:頂點V到達圖中所有頂點
擴展樹
判斷是否連通
深度優先搜尋 DFS
堆疊(鏈結)
解題:相鄰串列
廣度優先搜尋 BFS
拜訪相鄰頂點
住列
解題:直接看(旁邊記)
最小成本擴展樹
(Minimun Cost Spanning Tree)
n個頂點必有n-1條邊
沒有迴圈
加權數值最低
Kruskal演算法
擴展數邊數，入選邊，成本，是否加入，圖
G(V，E)
V(G)={ V1,V2 }
E(G)={ (V1,V2),(V1,V3) }
最短路徑(Shortest Paths)
Dijkstra演算法
單源點全終點
頂點V0到其他頂點的最短路徑及距離