Hướng dẫn how do you create a graph from adjacency matrix in python? - làm thế nào để bạn tạo một đồ thị từ 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 vẽ một biểu đồ từ 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 tạo một biểu đồ trong cấu trúc dữ liệu Python?
Làm thế nào để bạn tìm thấy biểu đồ theo hướng của ma trận kề?

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.

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 <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;
}

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

Ứ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 vẽ một biểu đồ 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ề.To fill the adjacency matrix, we 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 .

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

Tạo một ma trận kề trong Python bằng mô -đun Numpy..

Đầu tiên, chúng ta sẽ tạo một ma trận kích thước n x n bằng cách chuyển một tuple (n, n) cho phương thức zeros () ..

Sau đó, chúng tôi sẽ cập nhật các giá trị lên 1 tại vị trí (I-1, J-1) cho mỗi EIJ cạnh trong biểu đồ;Ở đây, chúng tôi sử dụng lập chỉ mục dựa trên 0 ..

Làm thế nào để bạn tạo một biểu đồ trong cấu trúc dữ liệu Python?

Tạo biểu đồ bằng từ điển trong Python ..

Đồ thị và các biểu diễn của nó ..

Thực hiện đồ thị bằng STL để lập trình cạnh tranh |Đặt 2 (đồ thị có trọng số).

Thực hiện đồ thị bằng STL để lập trình cạnh tranh |Đặt 1 (DFS của không có trọng số và không bị ảnh hưởng).

N Nữ hoàng vấn đề |Backtracking-3 ..

Làm thế nào để bạn tìm thấy biểu đồ theo hướng của ma trận kề?

Ma trận liền kề Nếu có một cạnh giữa Vx đến VY thì giá trị của [Vx] [Vy] = 1 và A [Vy] [Vx] = 1, nếu không giá trị sẽ bằng không.Đối với một biểu đồ được định hướng, nếu có một cạnh giữa VX đến VY, thì giá trị của [VX] [VY] = 1, nếu không giá trị sẽ bằng không._x to V_y then the value of A[V_x][V_y]=1 and A[V_y][V_x]=1, otherwise the value will be zero. For a directed graph, if there is an edge between V_x to V_y, then the value of A[V_x][V_y]=1, otherwise the value will be zero.

programming python Weighted graph Python Graph Python Adjacency list Graph theory Python