图的原理及算法实现
1 图的基本概念
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。注意：顶点有时也称为节点或者交点，边有时也称为链接。
社交网络，每一个人就是一个顶点，互相认识的人之间通过边联系在一起, 边表示彼此的关系。这种关系可以是单向的，也可以是双向的！
同时，边可以是双向的，也可以是单向的！
地图导航 - 起点、终点和分叉口（包括十字路口·、T 字路口等）都是顶点，导航经过的两顶点的路径就是边！
如上图所示，我们导航从一个点到另外一个点可以有条路径，路径不同，路况就不同，拥堵程度不同，所以导致不同路径所花的时间也不一样，这种不同我们可以使用边的权重来表示，即根据每条边的实际情况给每一条边分配一个正数或者负数值。考虑如下机票图，各个城市就是顶点，航线就是边。那么权重就是机票价格。
我们前面讲解的树和链表都是图的特例！
如果我们有一个编程问题可以通过顶点和边表示，那么我们就可以将你的问题用图画出来，然后使用相应的图算法来找到解决方案。
2 图的表示
2.1 邻接列表
在邻接列表实现中，每一个顶点会存储一个从它这里开始的相邻边的列表。比如，如果顶点 B 有一条边到 A、C 和 E，那么 B 的列表中会有 3 条边。
邻接列表只描述指向外部的边。B 有一条边到 A，但是 A 没有边到 B，所以B没有出现在 A 的邻接列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。
2.2 邻接矩阵
由二维数组对应的行和列都表示顶点，由两个顶点所决定的矩阵对应元素数值表示这里两个顶点是否相连（如，0 表示不相连，非 0 表示相连和权值）、如果相连这个值表示的是相连边的权重。例如，广西到北京的机票，我们用邻接矩阵表示：
往这个图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行/列创建，然后将已有的数据复制到新的矩阵中。
2.3 邻接列表和邻接矩阵的对比分析
邻接列表和邻接矩阵我们该如何选择呢？
结论：大多数时候，选择邻接列表是正确的。（在图比较稀疏的情况下，每一个顶点都只会和少数几个顶点相连，这种情况下邻接列表是最佳选择。如果这个图比较密集，每一个顶点都和大多数其他顶点相连，那么邻接矩阵更合适。)
3 图的算法实现
参考资料：
1.
C/C++从入门到精通-高级程序员之路【奇牛学院】