什么是图

0x00 什么是图

​ 图表示多对多关系

​ 包含 一组顶点 通常用V（vertex）表示顶点集合

​ 一组边 通常用E(Edge) 表示边的集合

​ 边是顶点对：（v，w）∈E

​ 有向边<v,w>表示从v指向w的边

​ 不考虑重边和自回路

​ 以下图片可以帮助理解图：

0x01 抽象数据类型定义

0x02 怎么在程序中表示一张图

​ 邻接矩阵

可以看到 该矩阵是关于红线对称的，如果是有向图，那么该对称有意义，无向图则无意义，可以省略一半的空间

​ 邻接矩阵的优缺点

​

另一种则是邻接表

​ 由于邻接表需要指针域，所以元素越多则占用空间越大。