17 使用相鄰矩陣（Adjacency matrix）記錄一個有 V 個點 E 個邊的無向圖之空間複雜度為何？
(A) O(VE)
(B) O(V2)
(C) O(E）
(D) O(V+E)

答案：登入後查看
統計： A(95), B(140), C(29), D(56), E(11) #2966904

詳解 (共 1 筆)

#6160562

相鄰矩陣（Adjacency matrix）是一種用於表示圖的二維矩陣。對於一個有 V 個頂點的圖，相鄰矩陣是一個V×V 的矩陣，其中每個元素表示兩個頂點之間是否有邊連接。

對於一個無向圖：

  • 如果頂點 i 和頂點 j 之間有邊連接，則相鄰矩陣中的元素 A[i][j]=1A[i][j] = 1A[i][j]=1；
  • 如果頂點 i 和頂點 j 之間沒有邊連接，則 A[i][j]=0A[i][j] = 0A[i][j]=0；
  • 由於是無向圖，相鄰矩陣是對稱的，即 A[i][j]=A[j][i]A[i][j] = A[j][i]A[i][j]=A[j][i]。

因此，無向圖的相鄰矩陣是一個 V×V 的矩陣，這意味著需要V2個元素來存儲這個矩陣。

所以，記錄一個有 V個頂點和 E 個邊的無向圖，其相鄰矩陣的空間複雜度為 O(V2)。

0
0