图是一种非线性数据结构,由「节点(顶点)」和「边」组成,每条边连接一对顶点。根据边的方向有无,图可分为「有向图」和「无向图」。本文 以无向图为例 开展介绍。
如下图所示,此无向图的 顶点 和 边 集合分别为:
顶点集合: vertices = {1, 2, 3, 4, 5}
边集合: edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

表示图的方法通常有两种:
邻接矩阵: 使用数组 vertices
存储顶点,邻接矩阵 edges
存储边; edges[i][j]
代表节点 i + 1
和 节点 j + 1
之间是否有边。

C++实现如下:
int vertices[5] = {1, 2, 3, 4, 5}; int edges[5][5] = {{0, 1, 1, 1, 1}, {1, 0, 0, 1, 0}, {1, 0, 0, 0, 1}, {1, 1, 0, 0, 1}, {1, 0, 1, 1, 0}};
邻接表: 使用数组 vertices
存储顶点,邻接表 edges
存储边。 edges
为一个二维容器,第一维 i
代表顶点索引,第二维 edges[i]
存储此顶点对应的边集和;例如 edges[0] = [1, 2, 3, 4]
代表 vertices[0]
的边集合为 [1, 2, 3, 4]
。

C++实现如下:
int vertices[5] = {1, 2, 3, 4, 5}; vector<vector<int>> edges; vector<int> edge_1 = {1, 2, 3, 4}; vector<int> edge_2 = {0, 3}; vector<int> edge_3 = {0, 4}; vector<int> edge_4 = {0, 1, 4}; vector<int> edge_5 = {0, 2, 3}; edges.push_back(edge_1); edges.push_back(edge_2); edges.push_back(edge_3); edges.push_back(edge_4); edges.push_back(edge_5);
邻接矩阵 VS 邻接表 :
邻接矩阵的大小只与节点数量有关,即 N^2,其中 N 为节点数量。因此,当边数量明显少于节点数量时,使用邻接矩阵存储图会造成较大的内存浪费。
因此,邻接表适合存储稀疏图(顶点较多、边较少); 邻接矩阵适合存储稠密图(顶点较少、边较多)。