Hướng dẫn how do you code an adjacency matrix in python? - làm thế nào để bạn viết mã ma trận kề trong python?

Question

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

Nội dung chính Show

Ưu điểm của ma trận phụ thuộc
Nhược điểm của ma trận phụ thuộc
Mã ma trận kề trong Python, Java và C/C ++
Ứng dụng ma trận kề
Làm thế nào để bạn tạo ma trận kề trong Python?
Làm thế nào để bạn viết một ma trận kề?
Danh sách kề trong Python là gì?
Làm thế nào để bạn mã hóa một biểu đồ trong Python?

Một ma trận kề là một cách thể hiện biểu đồ dưới dạng ma trận của Booleans (0 và 1). Một biểu đồ hữu hạn có thể được biểu diễn dưới dạng ma trận vuông trên máy tính, trong đó giá trị boolean của ma trận cho biết nếu có đường dẫn trực tiếp giữa hai đỉnh.

Ví dụ, chúng tôi có một biểu đồ dưới đây.

Một biểu đồ không mong muốn

Chúng ta có thể biểu thị biểu đồ này trong mẫu ma trận như dưới đây.

Hướng dẫn how do you code an adjacency matrix in python? - làm thế nào để bạn viết mã ma trận kề trong python?

Biểu diễn ma trận của đồ thị

Mỗi ô trong bảng/ma trận trên được biểu diễn dưới dạng Aij, trong đó i và j là các đỉnh. Giá trị của Aij là 1 hoặc 0 tùy thuộc vào việc có cạnh từ đỉnh i đến đỉnh j hay không.

Nếu có một đường dẫn từ i đến j, thì giá trị của Aij là 1 nếu không thì 0. Ví dụ, có một đường dẫn từ đỉnh 1 đến đỉnh 2, vì vậy

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

3 là 1 và không có đường dẫn từ đỉnh 1 đến 3, Vì vậy,

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

4 là 0.

Trong trường hợp các biểu đồ không mong muốn, ma trận là đối xứng về đường chéo vì mỗi cạnh

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

5, cũng có một cạnh

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

6.

Ưu điểm của ma trận phụ thuộc

Các hoạt động cơ bản như thêm một cạnh, loại bỏ một cạnh và kiểm tra xem có cạnh từ đỉnh I đến đỉnh J cực kỳ hiệu quả về thời gian, thời gian không đổi hay không.
Nếu biểu đồ dày đặc và số lượng cạnh lớn, một ma trận kề phải là lựa chọn đầu tiên. Ngay cả khi biểu đồ và ma trận kề là thưa thớt, chúng ta có thể biểu diễn nó bằng cách sử dụng các cấu trúc dữ liệu cho ma trận thưa thớt.
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 đắt tiền trên GPU.
Bằng cách thực hiện các hoạt động trên ma trận liền kề, chúng ta có thể nhận được những hiểu biết quan trọng về bản chất của biểu đồ và mối quan hệ giữa các đỉnh của nó.

Nhược điểm của ma trận phụ thuộc

Yêu cầu không gian

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

7 của ma trận kề làm lại làm cho nó trở thành một con lợn bộ nhớ. Các biểu đồ trong 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ụ.

Mặc dù các hoạt động cơ bản là dễ dàng, các hoạt động như

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

8 và

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

9 rất tốn kém khi sử dụng biểu diễn ma trận kề.

Mã ma trận kề trong Python, Java và C/C ++

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

# 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("\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());
  }
}

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

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

Ứng dụng ma trận kề

Tạo bảng định tuyến trong mạng
Nhiệm vụ điều hướng

Làm thế nào để bạn tạo ma trận kề trong Python?

2. Ma trận liền kề. Các chỉ số hàng và cột biểu thị các đỉnh: m a t r i x [i] [j] = 1 ma trận [i] [j] = 1 ma trận [i] [j] = 1 có nghĩa là có một cạnh từ các đỉnh I đến j và m a t r i x [i] [j] = 0 ma trận [i] [j] = 0 ma trận [i] [j] = 0 biểu thị rằng không có cạnh giữa i và j.

Làm thế nào để bạn viết một ma trận kề?

Ma trận liền kề của biểu đồ để điền vào ma trận liền kề, chúng tôi nhìn vào tên của đỉnh theo hàng và cột.Nếu các đỉnh đó được kết nối bởi một cạnh trở lên, chúng tôi đếm số cạnh và đặt số này làm phần tử ma trận.Ma trận để biểu thị một biểu đồ theo cách này được gọi là ma trận kề.look at the name of the vertex in row and column. If those vertices are connected by an edge or more, we count number of edges and put this number as matrix element. The matrix to represent a graph in this way is called Adjacency matrix .

Danh sách kề trong Python là gì?

Một danh sách kề vật biểu thị một biểu đồ dưới dạng một mảng các danh sách được liên kết.Chỉ số của mảng đại diện cho một đỉnh và mỗi phần tử trong danh sách được liên kết của nó thể hiện các đỉnh khác tạo thành một cạnh với đỉnh.represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

Làm thế nào để bạn mã hóa một biểu đồ trong Python?

Output:..

Xác định trục x và giá trị trục y tương ứng như danh sách ..

Vẽ chúng trên vải bằng cách sử dụng.âm mưu () chức năng ..

Đặt tên cho trục x và trục y bằng cách sử dụng.Xlabel () và.các chức năng ylabel () ..

Đưa ra một tiêu đề cho cốt truyện của bạn bằng cách sử dụng.tiêu đề () chức năng ..

Cuối cùng, để xem cốt truyện của bạn, chúng tôi sử dụng.Hiển thị () chức năng ..

programming python Adjacency matrix Adjacency list Weighted graph Python

Hướng dẫn how do you code an adjacency matrix in python? - làm thế nào để bạn viết mã ma trận kề trong python?

Ưu điểm của ma trận phụ thuộc

Nhược điểm của ma trận phụ thuộc

Mã ma trận kề trong Python, Java và C/C ++

Ứng dụng ma trận kề

Làm thế nào để bạn tạo ma trận kề trong Python?

Làm thế nào để bạn viết một ma trận kề?

Danh sách kề trong Python là gì?

Làm thế nào để bạn mã hóa một biểu đồ trong Python?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội