Ma trận kề đồ thị (Với các ví dụ mã trong C ++, Java và Python)

Mục lục

Biểu diễn ma trận kề
Ví dụ về ma trận kề
Ưu điểm của ma trận kề
Nhược điểm của ma trận kề
Ví dụ về Python, Java và C / C ++
Ứng dụng ma trận gần kề

Trong hướng dẫn này, bạn sẽ tìm hiểu ma trận kề là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của ma trận kề trong C, C ++, Java và Python.

Ma trận kề là cách biểu diễn đồ thị G = (V, E) dưới dạng ma trận boolean.

Biểu diễn ma trận kề

Kích thước của ma trận là VxVnơi Vlà số đỉnh của đồ thị và giá trị của một mục Aijlà 1 hoặc 0 tùy thuộc vào việc có một cạnh từ đỉnh i đến đỉnh j.

Ví dụ về ma trận kề

Hình ảnh dưới đây cho thấy một đồ thị và ma trận kề tương đương của nó.

Ma trận kề từ biểu đồ

Trong trường hợp đồ thị vô hướng, ma trận đối xứng qua đường chéo vì ở mọi cạnh (i,j)thì cũng có một cạnh (j,i).

Ưu điểm của ma trận kề

Các phép toán cơ bản như thêm một cạnh, xóa một cạnh và kiểm tra xem có cạnh nào từ đỉnh i đến đỉnh j là các phép toán thời gian không đổi, hiệu quả về thời gian hay không.

Nếu đồ thị dày đặc và số lượng cạnh lớn, ma trận kề nên là lựa chọn đầu tiên. Ngay cả khi đồ thị và ma trận kề là thưa, chúng ta có thể biểu diễn nó bằng cách sử dụng cấu trúc dữ liệu cho ma trận thưa.

Tuy nhiên, lợi thế lớn nhất đến từ việc sử dụng ma trận. Những tiến bộ gần đây trong phần cứng cho phép chúng tôi thực hiện các hoạt động ma trận thậm chí tốn kém trên GPU.

Bằng cách thực hiện các phép toán trên ma trận liền kề, chúng ta có thể có được những hiểu biết quan trọng về bản chất của đồ thị và mối quan hệ giữa các đỉnh của nó.

Nhược điểm của ma trận kề

Các VxVyêu cầu không gian của ma trận kề làm cho nó một con heo bộ nhớ. Các đồ thị ngoài tự nhiên thường không có quá nhiều kết nối và đây là lý do chính tại sao danh sách kề là lựa chọn tốt hơn cho hầu hết các nhiệm vụ.

Trong khi các phép toán cơ bản là dễ dàng, các phép toán giống inEdgesvà outEdgestốn kém khi sử dụng biểu diễn ma trận kề.

Ví dụ về Python, Java và C / C ++

Nếu bạn biết cách tạo mảng hai chiều, bạn cũng biết cách tạo ma trận kề.

Python Java C C +

 # 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()

 // 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(""); ) 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()); ) )

 // Adjacency Matrix representation in C #include #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(""); ) ) 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; )

 // Adjacency Matrix representation in C++ #include 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 << ""; ) ) ~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(); )