树和图的一些概念

稠密图用 邻接矩阵存储
稀疏图用 邻接表存储
有很少条边或弧的图称为稀疏图，反之称为稠密图，这里的概念是相对而言的。
在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。 如果对于图中任意两个顶点vi、vj ∈E， vi，和vj都是连通的，则称G是连通图。

稠密图我建图是任意两点均有路径，对角线都是0。。求得的最短路所有起点都是1，终点都是n（矩阵的大小）
下面是稠密图的时间统计，因为矩阵不能开太大，所以最大开了1250*1250。除了n = 10 都是秒过就统计一次，其他均生成三次数据。
时间单位是ms。
稠密图总结：（可以是用邻接矩阵的情况）
1、如果n不大，可以用邻接矩阵的话，dijkstra是最好的选择，写起来比较快而且速度也很快。其次是SPFA，写起来比较好写。
2、floyd 这个算法，n大于300就最好不要用了，很有可能跑1秒以上了。
3、bellman-ford ，n大于200就不要用了，比floyd还耗时间 = =。。。

稀疏图的m 是边数，n是点数。
稀疏图总结：（前面的n比较小时可以用邻接矩阵，后面的floyd 啊 dijkstra等不能使用邻接矩阵的就删掉不考虑了）
1、稀疏图，明显感觉用邻接表的算法占优势了。
2、bellman 超过50000边就不要用了。
3、heap的表现可以说是最好的。
4、超过3000个点就不要用dijkstra 加邻接表 不加任何优化的那种。
5、超过500000条边就不要用SPFA加邻接表了。
6、综上，dijkstra + priority 邻接表 是最好的选择。虽然比heap慢一点，跑3W点 300W边和heap没差多少。
7、priority坏处就是，不能在队列里修改值，如果进队多次，可能空间满了。。
8、特别恶心的可以用heap ，一般的恶心用priority足以^ ^
————————————————————————————————————

2018年5月4日更新

今天学习了一些新概念，拿出来说一下
说在前面：对图的dfs遍历，由于顶点可以随意选择并且遍历的方式有许多不同，所以dfs搜索树有很多种。

树边：深度优先树中的边，已生成的边（如图中的黑色实线边）
后向边：不在深度优先树中的边，但由树中的顶点指向其父顶点或者是指向顶点本身的边（，可以是自环，图中的彩色虚线）
前向边：不在深度优先树中的边，但由树中的顶点指向其子辈顶点的边（图中的黑色虚线）
交叉边：除树边、后向边、前向边以外的边（图中的绿色虚线）