資料結構›Ch6 圖形第 3 題／共 26 題
3. 圖形表示法、Adjacency Matrix、Adjacency List
#DS-06-003易圖形表示法Adjacency MatrixAdjacency List
Compose a pseudocode function designed to accept a 2-dimensional array as input, interpreting it as the adjacency matrix representation of a graph. The function's purpose is to transform this matrix into its equivalent adjacency list representation. Please clearly specify what the return value of your function is.
參考答案與解析
FUNCTION MatrixToList(M, n):
adjList = 長度 n 的空串列陣列
FOR i = 0 TO n-1:
FOR j = 0 TO n-1:
IF M[i][j] != 0:
adjList[i].append(j)
RETURN adjList
回傳值 adjList 是長度 n 的陣列，adjList[i] 存放頂點 i 所有相鄰頂點的清單，時間複雜度 O(n²)。
📄 台大113
▤完整推導請見《WH 資工筆記 · 資料結構》Ch6 圖形