1、无向图：简单路径（不存在节点到自身的loop）
有向图：回路（cycle），没有回路的有向图称为acyclic，有时简称为DAG。
无向图：如果任意两个节点之间存在一条路径，就成为连通。
有向图：上述性质称为强连通。不能满足上述性质，但有向图对应的底图（去掉方向后的有向图）满足上述性质，称为弱连通。
2、图的三种表示方法
（1）邻接矩阵：主要适合于dense图
（2）邻接表：主要适合于sparse图，具体实现方式也有多种，可以使用vector或list，也可以使用映射（节点为关键字，对应值为adjacency list）。如果使用vector最好对它的容器大小事先做好限制，不要使用默认的大小，否则空间效率就不高了。
（3）边表示：在有些应用条件下是很方便的。
3、关于图的一些常用算法
（1）图的拓扑排序（要求：有向图，无环）
算法思路：根据节点的入度来判断拓扑顺序。 数据结构使用：队列
（2）单源最短路径算法
这里主要考虑4种情况：
无权重的最短路径问题、有权重的最短路径问题、存在negative weight的有权最短路径问题、不存在回路的有权最短路径问题。
在最短路径问题中对于每个节点，预先设定三个信息变量：
Dv：表示距离开始节点的距离 Pv：本节点的父节点（用于还原路径） Known：当节点是否已经处理完毕的标志
无权重的最短路径算法：
思路：图的广度优先搜索，使用的基本数据结构：queue。
Dijkstra's Algorithm（有权重的最短路径问题）: 图中可以存在回路，但不能存在负权值的边或回路
思路：贪心算法
算法按阶段进行：每一个阶段，都从所有unknown节点中选择Dv最小的节点v，然后就将从s到v的最短路径设置为known。剩下的工作就是更新距离值Dw，这里Dw=Dv+Cv,w，这里的节点w是和节点v相邻的且为unknown的节点。
这里使用的数据结构:优先队列（由于算法中需要实时更新路径的距离，而priority_queue并不支持find操作，所以可以使用更高级的优先级队列来实现，如：pairing heap，或 Fabonacci Heap）。
当然，如果使用普通的优先队列也可以实现算法要求：只要某节点的距离值有更新，就将它插入到优先级队列中，只是在出堆的时候，如果该节点的最短距离版本已经出堆，那么后面该节点的其他版本就直接忽略掉，这样做的缺点只在于程序执行效率可能会较低，但算法实现比较容易。
不存在回路的有权最短路径问题：
思路：只要根据拓扑排序的顺序来一次选择节点，将它声明为known就可以了，可以和toplogical运算一起做，而且这样就不需要优先级队列了。
存在negative weight的有权最短路径问题：
思路：Dijkstra算法不适用了。但是可以将有权算法和无权算法结合在一起。
数据结构使用：queue。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
最小生成树问题：
一个图存在最小生成树的前提：图是连通的。（所以执行最小生成树算法之前，一般需要进行连通性检测，如果是非连通的，那么就不存在对应的最小生成树）
最小生成树是acyclic，它本身是不唯一的，它所谓的“最小”就是它生成的树的所有边的代价是最小的。
下面介绍的两个算法都是基于贪心的思想（下面的算法都是基于无向图的，因为有向图比较复杂）
1、Prime Algorithm
这个算法的思想步骤非常类似于Dijstra‘s最短路径算法。
只是Dijstra算法中更新原则：dw=min( dv+cvw, dw);
而Prime算法使用的更新算法原则：dw=min( dw,cvw);
2、Kruskal Algorithnm
这个算法的主要思想是：每次都选择最短的边，然后判断这条边的两个节点是否已经在同一个集合中了，如果在就忽略掉这条边，如果不在同一个集合，就接受这条边。算法中止的条件是成功添加完|V|-1条边，因为图的|V|个节点只需要|V|-1条边就可以联通了。
所以底层的数据结构使用的是并查集。