# 鄰接矩陣 > 原文： [https://www.programiz.com/dsa/graph-adjacency-matrix](https://www.programiz.com/dsa/graph-adjacency-matrix) #### 在本教程中，您將學習什么是鄰接矩陣。 此外，您還將在 C，C++ ，Java 和 Python 中找到鄰接矩陣的工作示例。 鄰接矩陣是將圖形`G = {V, E}`表示為布爾矩陣的一種方式。 * * * ## 鄰接矩陣表示 矩陣的大小為`VxV`，其中`V`是圖形中的頂點數，而條目`Aij`的值取決于頂點`i`至頂點`j`的邊為 1 或 0。 * * * ## 鄰接矩陣示例 下圖顯示了一個圖形及其等效的鄰接矩陣。  圖的鄰接矩陣 在無向圖的情況下，由于每個邊`(i,j)`，矩陣關于對角線對稱，也有邊`(j,i)`。 * * * ## 鄰接矩陣的優點 基本操作（如添加邊線，移除邊線和檢查從頂點`i`到頂點`j`的邊線）是非常節省時間的恒定時間操作。 如果圖是密集的并且邊的數量很大，則鄰接矩陣應該是首選。 即使圖和鄰接矩陣是稀疏的，我們也可以使用稀疏矩陣的數據結構來表示它。 但是，最大的優勢來自矩陣的使用。 硬件的最新進展使我們能夠在 GPU 上執行甚至昂貴的矩陣運算。 通過對相鄰矩陣執行運算，我們可以深入了解圖形的性質及其頂點之間的關系。 * * * ## 鄰接矩陣的缺點 鄰接矩陣的`VxV`空間要求使其成為存儲豬。 野外繪制的圖形通常沒有太多的聯系，這就是[鄰接表](/dsa/graph-adjacency-list)是大多數任務的更好選擇的主要原因。 雖然基本操作很容易，但是當使用鄰接矩陣表示法時，`inEdges`和`outEdges`之類的操作很昂貴。 * * * ## Python，Java 和 C/C++ 示例 如果您知道如何創建二維數組，那么您還將知道如何創建鄰接矩陣。 ```py # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = [] for i in range(size): self.adjMatrix.append([0 for i in range(size)]) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix[v1][v2] = 1 self.adjMatrix[v2][v1] = 1 # Remove edges def remove_edge(self, v1, v2): if self.adjMatrix[v1][v2] == 0: print("No edge between %d and %d" % (v1, v2)) return self.adjMatrix[v1][v2] = 0 self.adjMatrix[v2][v1] = 0 def __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('{:4}'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main() ``` ```java // Adjacency Matrix representation in Java public class Graph { private boolean adjMatrix[][]; private int numVertices; // Initialize the matrix public Graph(int numVertices) { this.numVertices = numVertices; adjMatrix = new boolean[numVertices][numVertices]; } // Add edges public void addEdge(int i, int j) { adjMatrix[i][j] = true; adjMatrix[j][i] = true; } // Remove edges public void removeEdge(int i, int j) { adjMatrix[i][j] = false; adjMatrix[j][i] = false; } // Print the matrix public String toString() { StringBuilder s = new StringBuilder(); for (int i = 0; i < numVertices; i++) { s.append(i + ": "); for (boolean j : adjMatrix[i]) { s.append((j ? 1 : 0) + " "); } s.append("\n"); } return s.toString(); } public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); System.out.print(g.toString()); } } ``` ```c // Adjacency Matrix representation in C #include <stdio.h> #define V 4 // Initialize the matrix to zero void init(int arr[][V]) { int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr[i][j] = 0; } // Add edges void addEdge(int arr[][V], int i, int j) { arr[i][j] = 1; arr[j][i] = 1; } // Print the matrix void printAdjMatrix(int arr[][V]) { int i, j; for (i = 0; i < V; i++) { printf("%d: ", i); for (j = 0; j < V; j++) { printf("%d ", arr[i][j]); } printf("\n"); } } int main() { int adjMatrix[V][V]; init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; } ``` ```cpp // Adjacency Matrix representation in C++ #include <iostream> using namespace std; class Graph { private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero Graph(int numVertices) { this->numVertices = numVertices; adjMatrix = new bool*[numVertices]; for (int i = 0; i < numVertices; i++) { adjMatrix[i] = new bool[numVertices]; for (int j = 0; j < numVertices; j++) adjMatrix[i][j] = false; } } // Add edges void addEdge(int i, int j) { adjMatrix[i][j] = true; adjMatrix[j][i] = true; } // Remove edges void removeEdge(int i, int j) { adjMatrix[i][j] = false; adjMatrix[j][i] = false; } // Print the martix void toString() { for (int i = 0; i < numVertices; i++) { cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix[i][j] << " "; cout << "\n"; } } ~Graph() { for (int i = 0; i < numVertices; i++) delete[] adjMatrix[i]; delete[] adjMatrix; } }; int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.toString(); } ``` * * * ## 鄰接矩陣應用 1. 在網絡中創建路由表 2. 導航任務