图与图的存储

· · 算法·理论

图

什么是图？

严格意义上讲，图是一种数据结构，定义为：G=(V,E)。V 是一个有限集合，代表节点，E 代表边的集合，G 就是一张图。

概念

节点：图中的点；
边（弧）：图上的边；
有向图：边具有方向性，只能按方向从一点到另一点。
无向图：边不具有方向性，可以双向。
结点的度：无向图中，与结点相连的边的数目，称为结点的度。
入度：有向图中，以该结点为终点的有向边的数目；
出度：有向图中，以该结点为起点的有向边的数目；
边权：边的权值；
点权：点的权值；
连通：如果图中结点 u 和 v 之间存在一条路径，则称 u 和 v 是连通的；
完全图：任何两点都之间都存在双向边的图；
重边：两个节点之间存在多条方向相同的边；
自环：从节点 u 出发到达其自身的边；
简单图：无重边和自环的图；
孤点：度为 0 的点。

图的存储

邻接，相邻且连接，在图论中，两点邻接可以理解为有边相连的意思。

邻接矩阵

这种方法很容易，但是很少用。

建立矩阵 P=\{e_{i,j}\}，先考虑没有边权的图（没有边权实际上就是所有边权都是 1），其中 e_{i,j}\in\{0,1\}，若 e_{i,j} 为 0，代表有从 i 到 j 的有向边，无向图其实就是每条边都是双向的有向图，所以 e_{i,j}=e_{j,i}，无向图的邻接矩阵关于主对角线对称。

如果边存在权值，那么就可以让 e_{i,j} 等于边的权值，如果不存在边，可以设为 +\infty 也可以是 0 或者 -1，取决于需要。

邻接表