鄰接矩陣計算機

在鄰接矩陣、邊列表和鄰接表之間進行轉換。自動檢測有向/無向圖，計算度序列、密度、連通分量和矩陣冪，並提供互動式 SVG 圖形視覺化。

鄰接矩陣計算機

鄰接矩陣計算機是一款圖論工具，可在三種規範的圖表示法（鄰接矩陣、邊列表和鄰接列表）之間進行轉換，並透過結構分析豐富結果：度數序列、圖密度、連通分量和矩陣冪。它會自動檢測您的輸入描述的是有向圖還是無向圖，並在每個結果旁呈現即時 SVG 視覺化圖表。

什麼是鄰接矩陣？

給定一個具有 n 個頂點的圖 G = (V, E)，其鄰接矩陣是一個 n × n 方陣 A，如果存在從頂點 i 到頂點 j 的邊，其條目 A[i][j] 為 1，否則為 0。

A[i][j] = 1 若 (v_i, v_j) ∈ E ，否則為 0

對於無向圖，鄰接矩陣總是對稱的：每條邊 {u, v} 都會同時產生 A[u][v] = 1 和 A[v][u] = 1。對於有向圖，矩陣可能是不對稱的，反映了每條弧的方向。

三種表示法 — 挑選適合您問題的一種

表示法	空間複雜度	邊查找	列出鄰居	最適用於
鄰接矩陣	Θ(n²)	O(1)	Θ(n)	稠密圖；矩陣代數（冪、特徵值）
鄰接列表	Θ(n + m)	O(deg v)	Θ(deg v)	稀疏圖；BFS/DFS 和最短路徑算法
邊列表	Θ(m)	Θ(m)	Θ(m)	輸入/輸出、Kruskal 最小生成樹、以邊為中心的算法

計算出的關鍵指標

度數序列

對於無向圖，頂點的度數是與其相連的邊數（自環計為兩次）。對於有向圖，每個頂點都有入度（進入的弧）和出度（出去的弧）。排序後的度數列表是一個經典的圖不變量，用於同構測試和 Erdős–Gallai 可實現性定理。

握手定理： Σ deg(v) = 2m (無向) Σ in-deg(v) = Σ out-deg(v) = m (有向)

圖密度

密度衡量圖相對於 n 個頂點上可能的最大邊數的「飽和」程度。

無向圖： D = 2m / (n(n−1)) 有向圖： D = m / (n(n−1))

密度為 0 表示沒有邊，1 表示圖是完全圖。低於 0.1 的值通常表示稀疏圖，此時鄰接列表比矩陣更節省空間。

連通分量

連通分量是頂點的最大子集，使得每一對頂點都由路徑連接。對於有向圖，此計算機會報告弱連通分量（忽略箭頭方向）— 這與將每條弧視為無向邊所獲得的子集相同。

矩陣冪 (A², A³ ... )

代數圖論的一個基本定理指出，A^k 的 (i, j) 條目等於從頂點 i 到頂點 j 恰好長度為 k 的步行次數。因此：

A²[i][i] 等於頂點 i 的度數（無向圖），因為從 i 到自身的 2 步步行是「走到鄰居再回來」。
A³ 的跡 (trace) 除以 6 等於無向圖中的三角形數量。
Aⁿ⁻¹ 是否有任何零條目可以告訴您該圖是否連通。

接受的輸入格式

1. 邊列表

每行一條邊或以逗號分隔。任何分隔符號都可以：A-B, A B, A,B, A->B, A--B。如果您想強制進行有向解釋，請使用 ->。

A-B, B-C, C-A, C-D (帶尾巴的無向 4-環) A->B, B->C, C->D, D->A (長度為 4 的有向環)

2. 鄰接列表

每行一個頂點，格式為 頂點: 鄰居1, 鄰居2, ...。順序不重要；缺失的頂點會從鄰居列表中自動添加。

A: B, C, D B: A, C C: A, B, D D: A, C

3. 鄰接矩陣

每行一個行向量，包含以空格或逗號分隔的 0/1 值。矩陣必須是方陣。可選擇在「矩陣標籤」欄位中提供自定義標籤（否則使用 A, B, C…）。

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

如何使用此計算機

使用分頁選擇器挑選輸入格式：邊列表、鄰接列表或鄰接矩陣。
在文本區域粘貼或輸入您的圖形。對於矩陣輸入，可在矩陣標籤欄位添加可選標籤。
選擇圖形類型 — 保持為「自動檢測」，計算機將從箭頭 (->) 或矩陣對稱性推斷有向性。如果您想覆蓋自動判斷，請強制設為「有向」或「無向」。
點擊「轉換並分析圖形」。結果頁面顯示鄰接矩陣、互動式 SVG 渲染、另外兩種文本表示、度數統計、連通分量，以及當圖形足夠小時顯示步行計數矩陣 A² 和 A³。
將滑鼠停留在矩陣行或圖形節點上以點亮匹配的行/列和關聯邊 — 這是每種格式編碼相同資訊的即時視覺證明。

實作範例

考慮頂點 {A, B, C, D} 上的無向圖，邊為 AB, BC, CA, CD。鄰接矩陣為：

A B C D A [ 0 1 1 0 ] B [ 1 0 1 0 ] C [ 1 1 0 1 ] D [ 0 0 1 0 ]

計算機導出的關鍵事實：

對稱嗎？ 是 — 確認為無向圖。
度數序列： (3, 2, 2, 1) — 頂點 C 是中心節點。
密度： 2·4 / (4·3) = 0.667 — 一個中等稠密的圖。
連通嗎？ 是，單一分量。
三角形： 恰好一個 (A–B–C)，正如 tr(A³) = 6 所證明的。

常見應用

社交網絡分析 — 朋友/追蹤者圖表、中心性。
網絡與引用圖 — PageRank 和 HITS 直接在 A 和 A^T 上運行。
路由與網絡 — 最短路徑、最小割、最大流。
化學 — 以原子為頂點、化學鍵為邊的分子圖。
調度與依賴關係解析 — 構建系統中的有向無環圖 (DAG)。
馬可夫鏈 — 從圖形導出的行隨機矩陣編碼了轉移概率。

常見問題解答

什麼是鄰接矩陣？

鄰接矩陣是用於表示有限圖的 n × n 方陣。如果存在從頂點 i 到頂點 j 的邊，則每個單元格 A[i][j] 為 1，否則為 0。對於無向圖，矩陣是對稱的，因此 A[i][j] = A[j][i]。該矩陣使得在常數時間內檢查兩個頂點是否相連變得容易，並且矩陣冪編碼了頂點之間的步行次數。

如何從鄰接矩陣判斷圖是否為有向圖？

如果鄰接矩陣是對稱的，即每一對索引的 A[i][j] 都等於 A[j][i]，則該圖是無向圖。如果至少有一對 A[i][j] 與 A[j][i] 不同，則該圖是有向圖。當您選擇「自動檢測」選項時，此計算機會自動執行對稱性檢查。

鄰接矩陣的 k 次冪代表什麼？

A^k 的條目 (i, j) 計算了從頂點 i 到頂點 j 恰好長度為 k 的步行次數。例如，A²[i][j] 是 2 步路徑的數量，在無向圖中這等於 i 和 j 之間的公共鄰居數量。此屬性用於三角形計數、可達性和 PageRank 風格計算的算法中。

什麼是圖密度？

圖密度是現有邊數與最大可能邊數的比率。對於具有 n 個頂點的無向簡單圖，密度 = 2m / (n(n-1))。對於有向圖，密度 = m / (n(n-1))。密度接近 0 表示稀疏圖；密度為 1 表示完全圖。

鄰接矩陣與鄰接列表有何不同？

鄰接矩陣使用 n² 位元存儲每對頂點的連通性，使鄰居查找為 O(1)，但內存使用為 O(n²)。鄰接列表僅存儲每個頂點的實際鄰居，給出 O(n + m) 內存，對於稀疏圖來說要小得多，但鄰居查找需要線性掃描。矩陣更適合稠密圖和矩陣代數運算；列表更適合稀疏圖和 BFS/DFS 等遍歷算法。

此工具可以處理加權圖嗎？

目前的計算機側重於具有 0/1 條目的未加權鄰接矩陣。如果您粘貼具有非零數值權重的矩陣，則每個非零單元格在結構分析中都被視為 1。對於最短路徑等加權圖計算，請考慮使用專用的加權圖工具。

延伸閱讀

引用此內容、頁面或工具為：

"鄰接矩陣計算機" 於 https://MiniWebtool.com/zh-tw/鄰接矩陣計算器/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊開發。更新日期：2026年4月20日

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

鄰接矩陣計算機