邻接矩阵

图算法

邻接矩阵使用二维数组表示图,matrix[i][j]的值表示顶点i和顶点j之间是否存在边(以及边的权重)。

空间复杂度:O(V^2)

算法讲解

邻接矩阵

介绍

邻接矩阵(Adjacency Matrix)是图论中常用的图表示方式之一,它使用二维数组来表示图中顶点之间的连接关系。对于有 n 个顶点的图,我们使用一个 n×n 的矩阵,如果顶点 i 和顶点 j 之间有边,则矩阵中对应位置的元素值为 1(无权图)或者权重值(有权图),否则为 0 或无穷大。

基本概念

在理解邻接矩阵之前,我们需要了解一些基础图论概念:

图(Graph):由顶点(Vertex)和连接顶点的边(Edge)组成的数据结构。

顶点(Vertex):图中的节点,通常用数字标识,如 0, 1, 2... 或字母 A, B, C...

边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。

在邻接矩阵中:

  • 矩阵的行和列分别代表图中的顶点
  • 矩阵元素 M[i][j] 表示从顶点 i 到顶点 j 的边的信息

根据图的类型,邻接矩阵有不同的表示方式:

无向图中:

  • 如果顶点 i 和 j 之间有边,则 M[i][j] = M[j][i] = 1(无权图)或权重值(有权图)
  • 如果没有边,则 M[i][j] = M[j][i] = 0 或无穷大
  • 矩阵是对称的,即 M[i][j] = M[j][i]

有向图中:

  • 如果从顶点 i 到 j 有一条边,则 M[i][j] = 1 或权重值
  • 如果没有边,则 M[i][j] = 0 或无穷大
  • 矩阵通常不是对称的

示例:
假设有一个包含 4 个顶点 (0, 1, 2, 3) 的无权无向图,边的信息如下:

  • 0 连接到 1
  • 0 连接到 2
  • 1 连接到 2
  • 2 连接到 3

则其邻接矩阵表示为:

▼
Plain
复制代码
0 1 2 3 0 [ 0 1 1 0 ] 1 [ 1 0 1 0 ] 2 [ 1 1 0 1 ] 3 [ 0 0 1 0 ]

如果是有权图,矩阵中存储的就是对应边的权重,没有边的位置通常用无穷大(实际编程中可能用一个特殊值如 -1 或 Integer.MAX_VALUE)表示。

核心特性

  • 直观表示:通过矩阵可以直观地看出任意两个顶点之间是否有连接
  • 快速查询:O(1) 时间复杂度即可确定两个顶点之间是否有边
  • 适合密集图:当图中边的数量接近顶点数的平方时,邻接矩阵较为高效
  • 矩阵运算:可以利用矩阵运算解决图论问题,如求最短路径

基本操作

  • 添加边:设置矩阵中对应位置的值
  • 删除边:重置矩阵中对应位置的值
  • 查询边:直接访问矩阵中对应位置
  • 获取顶点的所有邻接点:遍历该顶点对应的行或列

基础实现

代码实现

Java

▼
Java
复制代码
// 邻接矩阵表示的图 class Graph { private int V; // 顶点数 private int[][] adjMatrix; // 邻接矩阵 // 构造函数 public Graph(int v) { this.V = v; adjMatrix = new int[v][v]; // 初始化矩阵,所有边的值都为0 for (int i = 0; i < v; i++) { for (int j = 0; j < v; j++) { adjMatrix[i][j] = 0; } } } // 添加边(无向图) public void addEdge(int source, int destination) { // 确保顶点有效 if (source >= 0 && source < V && destination >= 0 && destination < V) { adjMatrix[source][destination] = 1; adjMatrix[destination][source] = 1; // 对于无向图,两个方向都要设置 } } // 添加带权重的边(有权图) public void addEdge(int source, int destination, int weight) { if (source >= 0 && source < V && destination >= 0 && destination < V) { adjMatrix[source][destination] = weight; adjMatrix[destination][source] = weight; // 对于无向图,两个方向都要设置 } } // 删除边 public void removeEdge(int source, int destination) { if (source >= 0 && source < V && destination >= 0 && destination < V) { adjMatrix[source][destination] = 0; adjMatrix[destination][source] = 0; // 对于无向图,两个方向都要重置 } } // 判断两个顶点之间是否有边 public boolean hasEdge(int source, int destination) { if (source >= 0 && source < V && destination >= 0 && destination < V) { return adjMatrix[source][destination] != 0; } return false; } // 获取边的权重 public int getEdgeWeight(int source, int destination) { if (source >= 0 && source < V && destination >= 0 && destination < V) { return adjMatrix[source][destination]; } return -1; // 表示没有边或顶点无效 } // 打印邻接矩阵 public void printMatrix() { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { System.out.print(adjMatrix[i][j] + " "); } System.out.println(); } } // 获取顶点的所有邻接点 public List<Integer> getAdjacentVertices(int vertex) { List<Integer> adjacentVertices = new ArrayList<>(); if (vertex >= 0 && vertex < V) { for (int j = 0; j < V; j++) { if (adjMatrix[vertex][j] != 0) { adjacentVertices.add(j); } } } return adjacentVertices; } }

Python

▼
Python
复制代码
# 邻接矩阵表示的图 class Graph: def __init__(self, v): self.V = v # 顶点数 # 初始化矩阵,所有边的值都为0 self.adj_matrix = [[0 for _ in range(v)] for _ in range(v)] # 添加边(无向图) def add_edge(self, source, destination, weight=1): # 确保顶点有效 if 0 <= source < self.V and 0 <= destination < self.V: self.adj_matrix[source][destination] = weight self.adj_matrix[destination][source] = weight # 对于无向图,两个方向都要设置 # 删除边 def remove_edge(self, source, destination): if 0 <= source < self.V and 0 <= destination < self.V: self.adj_matrix[source][destination] = 0 self.adj_matrix[destination][source] = 0 # 对于无向图,两个方向都要重置 # 判断两个顶点之间是否有边 def has_edge(self, source, destination): if 0 <= source < self.V and 0 <= destination < self.V: return self.adj_matrix[source][destination] != 0 return False # 获取边的权重 def get_edge_weight(self, source, destination): if 0 <= source < self.V and 0 <= destination < self.V: return self.adj_matrix[source][destination] return -1 # 表示没有边或顶点无效 # 打印邻接矩阵 def print_matrix(self): for i in range(self.V): print(" ".join(str(x) for x in self.adj_matrix[i])) # 获取顶点的所有邻接点 def get_adjacent_vertices(self, vertex): adjacent_vertices = [] if 0 <= vertex < self.V: for j in range(self.V): if self.adj_matrix[vertex][j] != 0: adjacent_vertices.append(j) return adjacent_vertices

JavaScript

▼
Javascript
复制代码
// 邻接矩阵表示的图 class Graph { constructor(v) { this.V = v; // 顶点数 this.adjMatrix = []; // 初始化矩阵,所有边的值都为0 for (let i = 0; i < v; i++) { this.adjMatrix[i] = new Array(v).fill(0); } } // 添加边(无向图) addEdge(source, destination, weight = 1) { // 确保顶点有效 if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) { this.adjMatrix[source][destination] = weight; this.adjMatrix[destination][source] = weight; // 对于无向图,两个方向都要设置 } } // 删除边 removeEdge(source, destination) { if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) { this.adjMatrix[source][destination] = 0; this.adjMatrix[destination][source] = 0; // 对于无向图,两个方向都要重置 } } // 判断两个顶点之间是否有边 hasEdge(source, destination) { if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) { return this.adjMatrix[source][destination] !== 0; } return false; } // 获取边的权重 getEdgeWeight(source, destination) { if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) { return this.adjMatrix[source][destination]; } return -1; // 表示没有边或顶点无效 } // 打印邻接矩阵 printMatrix() { for (let i = 0; i < this.V; i++) { console.log(this.adjMatrix[i].join(' ')); } } // 获取顶点的所有邻接点 getAdjacentVertices(vertex) { const adjacentVertices = []; if (vertex >= 0 && vertex < this.V) { for (let j = 0; j < this.V; j++) { if (this.adjMatrix[vertex][j] !== 0) { adjacentVertices.push(j); } } } return adjacentVertices; } }

Go

▼
Go
复制代码
package main import "fmt" // Graph 邻接矩阵表示的图 type Graph struct { V int // 顶点数 AdjMatrix [][]int // 邻接矩阵 } // NewGraph 创建新图 func NewGraph(v int) *Graph { // 初始化邻接矩阵 adjMatrix := make([][]int, v) for i := range adjMatrix { adjMatrix[i] = make([]int, v) } return &Graph{ V: v, AdjMatrix: adjMatrix, } } // AddEdge 添加边(无向图) func (g *Graph) AddEdge(source, destination int, weight int) { // 确保顶点有效 if source >= 0 && source < g.V && destination >= 0 && destination < g.V { g.AdjMatrix[source][destination] = weight g.AdjMatrix[destination][source] = weight // 对于无向图,两个方向都要设置 } } // RemoveEdge 删除边 func (g *Graph) RemoveEdge(source, destination int) { if source >= 0 && source < g.V && destination >= 0 && destination < g.V { g.AdjMatrix[source][destination] = 0 g.AdjMatrix[destination][source] = 0 // 对于无向图,两个方向都要重置 } } // HasEdge 判断两个顶点之间是否有边 func (g *Graph) HasEdge(source, destination int) bool { if source >= 0 && source < g.V && destination >= 0 && destination < g.V { return g.AdjMatrix[source][destination] != 0 } return false } // GetEdgeWeight 获取边的权重 func (g *Graph) GetEdgeWeight(source, destination int) int { if source >= 0 && source < g.V && destination >= 0 && destination < g.V { return g.AdjMatrix[source][destination] } return -1 // 表示没有边或顶点无效 } // PrintMatrix 打印邻接矩阵 func (g *Graph) PrintMatrix() { for i := 0; i < g.V; i++ { for j := 0; j < g.V; j++ { fmt.Printf("%d ", g.AdjMatrix[i][j]) } fmt.Println() } } // GetAdjacentVertices 获取顶点的所有邻接点 func (g *Graph) GetAdjacentVertices(vertex int) []int { var adjacentVertices []int if vertex >= 0 && vertex < g.V { for j := 0; j < g.V; j++ { if g.AdjMatrix[vertex][j] != 0 { adjacentVertices = append(adjacentVertices, j) } } } return adjacentVertices }

C++

▼
C++
复制代码
#include <iostream> #include <vector> class Graph { private: int V; // 顶点数 std::vector<std::vector<int>> adjMatrix; // 邻接矩阵 public: // 构造函数 Graph(int v) { this->V = v; // 初始化矩阵 adjMatrix.resize(v); for (int i = 0; i < v; i++) { adjMatrix[i].resize(v, 0); } } // 添加边(无向图) void addEdge(int source, int destination, int weight = 1) { // 确保顶点有效 if (source >= 0 && source < V && destination >= 0 && destination < V) { adjMatrix[source][destination] = weight; adjMatrix[destination][source] = weight; // 对于无向图,两个方向都要设置 } } // 删除边 void removeEdge(int source, int destination) { if (source >= 0 && source < V && destination >= 0 && destination < V) { adjMatrix[source][destination] = 0; adjMatrix[destination][source] = 0; // 对于无向图,两个方向都要重置 } } // 判断两个顶点之间是否有边 bool hasEdge(int source, int destination) { if (source >= 0 && source < V && destination >= 0 && destination < V) { return adjMatrix[source][destination] != 0; } return false; } // 获取边的权重 int getEdgeWeight(int source, int destination) { if (source >= 0 && source < V && destination >= 0 && destination < V) { return adjMatrix[source][destination]; } return -1; // 表示没有边或顶点无效 } // 打印邻接矩阵 void printMatrix() { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { std::cout << adjMatrix[i][j] << " "; } std::cout << std::endl; } } // 获取顶点的所有邻接点 std::vector<int> getAdjacentVertices(int vertex) { std::vector<int> adjacentVertices; if (vertex >= 0 && vertex < V) { for (int j = 0; j < V; j++) { if (adjMatrix[vertex][j] != 0) { adjacentVertices.push_back(j); } } } return adjacentVertices; } };

优缺点

优点:

  • 实现简单,易于理解
  • 查询两个顶点之间是否有边的时间复杂度为 O(1)
  • 添加和删除边的操作非常高效,时间复杂度为 O(1)
  • 适合表示密集图(边数接近顶点数平方的图)
  • 可以直接应用矩阵运算来解决一些图论问题

缺点:

  • 空间复杂度为 O(V²),对于大型稀疏图会浪费大量空间
  • 添加或删除顶点的操作复杂,需要重新分配并复制整个矩阵
  • 遍历所有边的时间复杂度为 O(V²),对于稀疏图效率较低
  • 不能表示平行边(两个顶点之间的多条边)

应用场景

  • 表示较小规模的图,尤其是边较密集的图
  • 需要频繁查询两个顶点之间是否存在边的场景
  • 实现图的算法时,特别是那些需要快速判断顶点间连接性的算法
  • 图的分析算法,如Floyd-Warshall算法寻找所有点对之间的最短路径
  • 社交网络分析中的连接关系表示
  • 网络路由算法中的连接性分析

扩展

邻接矩阵的优化

对于无向图,由于邻接矩阵是对称的,我们可以只存储上三角或下三角部分,从而将空间需求降低约一半。这种优化在实际应用中可以通过一维数组加索引转换公式实现。

变种:关联矩阵

除了邻接矩阵外,还有一种称为关联矩阵(Incidence Matrix)的表示方法。在 n 个顶点、m 条边的图中,关联矩阵是一个 n×m 的矩阵:

  • 对于无向图,如果边 j 连接顶点 i,则矩阵元素 M[i][j] = 1,否则为 0
  • 对于有向图,如果边 j 从顶点 i 出发,则 M[i][j] = 1;如果边 j 指向顶点 i,则 M[i][j] = -1;否则为 0

测验

  1. 在一个包含 100 个顶点的无向图中,如果使用邻接矩阵表示,矩阵的大小是多少?存储这个矩阵最少需要多少比特?
  2. 如果一个邻接矩阵是对称的(即 M[i][j] = M[j][i] 对所有 i, j 成立),这说明这个图是什么类型?
  3. 在邻接矩阵中,一个顶点的度(与之相连的边数)如何计算?

测验答案

  1. 矩阵大小为 100×100 = 10000 个元素。如果使用布尔值(1 比特)表示边的存在,则至少需要 10000 比特。
  2. 对称的邻接矩阵表示的是无向图,因为无向图中的边没有方向,从 i 到 j 有边意味着从 j 到 i 也有边。
  3. 对于无向图,顶点的度等于该顶点对应行(或列)中非零元素的数量;对于有向图,顶点的出度等于对应行中非零元素的数量,入度等于对应列中非零元素的数量。

相关的 LeetCode 热门题目