邻接矩阵
介绍
邻接矩阵(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 的边的信息
根据图的类型,邻接矩阵有不同的表示方式:
...