跳到主要内容

邻接矩阵

提示
  1. 定义和表示：邻接矩阵是一种使用矩阵表示图的方法，矩阵中的每个元素代表两个顶点之间是否存在路径，即如果存在从顶点 i 到 j 的路径，则矩阵中的 Aij 为1，否则为0。
  2. 优点：对于密集图来说，基本操作如添加边、删除边和检查顶点间是否存在边都非常高效；支持在GPU上进行高效的矩阵操作，有助于深入了解图的特性。
  3. 缺点：邻接矩阵需要 VxV 的空间，可能占用大量内存，特别是在图稀疏时；某些操作（如查找 inEdges 和 outEdges）可能成本较高。

邻接矩阵是一种以布尔值（0和1）的矩阵形式表示图的方法。有限图可以在计算机上表示为一个方阵，其中矩阵的布尔值表示两个顶点之间是否存在直接路径。

例如，我们有下面的图形。

一个无向图

我们可以将这个图以矩阵形式表示如下。

图的矩阵表示

上表/矩阵中的每个单元格都表示为 Aij，其中 i 和 j 是顶点。Aij 的值要么是1，要么是0，取决于从顶点 i 到顶点 j 是否存在一条边。

如果存在从 i 到 j 的路径，则 Aij 的值为1，否则为0。例如，从顶点1到顶点2存在一条路径，所以 A12 为1，而从顶点1到3没有路径，所以 A13 为0。

对于无向图，由于每个边 (i,j) 都有对应的边 (j,i)，所以矩阵关于对角线对称。

邻接矩阵的优点​

  • 基本操作，如添加边、删除边以及检查是否存在从顶点i到顶点j的边，非常高效，是常数时间操作。
  • 如果图很密集且边的数量很大，邻接矩阵应该是首选。即使图和邻接矩阵是稀疏的，我们也可以使用稀疏矩阵的数据结构来表示它。
  • 最大的优势来自矩阵的使用。硬件的最新进展使我们能够在GPU上执行昂贵的矩阵操作。
  • 通过对邻接矩阵执行操作，我们可以深入了解图的性质以及其顶点之间的关系。

邻接矩阵的缺点​

  • 邻接矩阵的空间要求为 VxV，占用大量内存。实际中的图通常不会有太多连接，这是为什么邻接表在大多数情况下是更好的选择的主要原因。
  • 虽然基本操作很容易，但使用邻接矩阵表示时，inEdges 和 outEdges 等操作会变得很昂贵。

Python、Java 和 C/C++ 中的邻接矩阵代码​

如果你知道如何创建二维数组，那么你也知道如何创建邻接矩阵。

Python Java C C++

# Python 中的邻接矩阵表示


class Graph(object):

    # 初始化矩阵
    def __init__(self, size):
        self.adjMatrix = []
        for i in range(size):
            self.adjMatrix.append([0 for i in range(size)])
        self.size = size

    # 添加边
    def add_edge(self, v1, v2):
        if v1 == v2:
            print("相同的顶点 %d 和 %d" % (v1, v2))
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1

    # 删除边
    def remove_edge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("顶点 %d 和 %d 之间没有边" % (v1, v2))
            return
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0

    def __len__(self):
        return self.size

    # 打印矩阵
    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 中表示邻接矩阵

public class Graph {
  private boolean adjMatrix[][];
  private int numVertices;

  // 初始化矩阵
  public Graph(int numVertices) {
    this.numVertices = numVertices;
    adjMatrix = new boolean[numVertices][numVertices];
  }

  // 添加边
  public void addEdge(int i, int j) {
    adjMatrix[i][j] = true;
    adjMatrix[j][i] = true;
  }

  // 移除边
  public void removeEdge(int i, int j) {
    adjMatrix[i][j] = false;
    adjMatrix[j][i] = false;
  }

  // 打印矩阵
  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 中表示邻接矩阵

#include <stdio.h>
#define V 4

// 初始化矩阵为零
void init(int arr[][V]) {
  int i, j;
  for (i = 0; i < V; i++)
    for (j = 0; j < V; j++)
      arr[i][j] = 0;
}

// 添加边
void addEdge(int arr[][V], int i, int j) {
  arr[i][j] = 1;
  arr[j][i] = 1;
}

// 打印矩阵
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;
}
// C++中的邻接矩阵表示

#include <iostream>
using namespace std;

class Graph {
   private:
  bool** adjMatrix;
  int numVertices;

   public:
  // 初始化矩阵为零
  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;
    }
  }

  // 添加边
  void addEdge(int i, int j) {
    adjMatrix[i][j] = true;
    adjMatrix[j][i] = true;
  }

  // 删除边
  void removeEdge(int i, int j) {
    adjMatrix[i][j] = false;
    adjMatrix[j][i] = false;
  }

  // 打印矩阵
  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();
}

邻接矩阵的应用​

  • 在网络中创建路由表
  • 导航任务
最后于 更新