教甄◆資訊科技概論專業(電腦科)題庫下載題庫

O(|V|)+O(|V||E|)+O(|E|)+|V|O(|V||V|+|E|)=O(|V|2|V|+|V||E|)O(|V|)+O(|V||E|)+O(|E|)+|V|O(|V||V|+|E|)=O(|V|2|V|+|V||E|)（新增|V|條邊）+（修正負邊）+（重設權重）+（對每個頂點做「Dijkstra’s algorithm」）相鄰串列與相鄰陣列比較表 Adjacency matrixAdjacency list空間需求O(n2)O(n2)O(n+e)表示頂點數多邊數少之圖需要O(n2)O(n2)且為稀疏矩陣，不適合適合表示邊數多（e=O(n2)(n2)）之圖適合需要O(n+O(n2))O(n+O(n2))，不適合判斷兩頂點間是否存在邊時間複雜度 O(1)，適合時間複雜度 O(e)，不適合求圖上的邊數（判斷連通…）時間複雜度 O(n2)O(n2)，不適合時間複雜度 O(n+e)，適合

參考：

https://wangwilly.github.io/willywangkaa/20...

查看完整內容

• O(|V|)+O(|V||E|)+O(|E|)+|V|O(|V||V|+|E|)=O(|V|2|V|+|V||E|)O(|V|)+O(|V||E|)+O(|E|)+|V|O(|V||V|+|E|)=O(|V|2|V|+|V||E|)
• （新增|V|條邊）+（修正負邊）+（重設權重）+（對每個頂點做「Dijkstra’s algorithm」）

相鄰串列與相鄰陣列比較表

	Adjacency matrix	Adjacency list
空間需求	O(n2)O(n2)	O(n+e)
表示頂點數多邊數少之圖	需要O(n2)O(n2)且為稀疏矩陣，不適合	適合
表示邊數多（e=O(n2)(n2)）之圖	適合	需要O(n+O(n2))O(n+O(n2))，不適合
判斷兩頂點間是否存在邊	時間複雜度 O(1)，適合	時間複雜度 O(e)，不適合
求圖上的邊數（判斷連通…）	時間複雜度 O(n2)O(n2)，不適合	時間複雜度 O(n+e)，適合

參考：

https://wangwilly.github.io/willywangkaa/2018/12/02/Data-structure/