教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

邻接矩阵

介绍

邻接矩阵(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 的边的信息

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

...

目录