图
数据结构——图的学习路线
学习先决条件：指针基础 数组和链表 图的基本概念（如边，顶点，路径，权值）
1 理解图的两大存储结构
1-1 邻接矩阵
1-2 邻接表
注意：邻接表中，指针数组里的每一个指针都是一个单链表的头指针
注意：单链表里每个节点里存储的是图中每条边的信息。
2 理解图的遍历算法
2-1 深度优先遍历 dfs
注意：花半小时看懂dfs的递归代码。
2-2 宽度优先遍历 bfs
注意：又叫广度优先算法，需要一个队列，用非递归实现，请用半小时看懂实现代码。
3 图的最小代价生成树算法
3-1 普里姆算法
注意：把书上给的图文例子看懂。
3-2 克鲁斯卡尔算法
注意：把书上给的图文例子看懂
注意：克鲁斯卡尔的时间复杂度
4 AOV和AOE网络
4-1 AOV 拓扑排序算法过程
注意：AOV和AOE都可以理解为一个工程图，工程由很多项目组成，项目直接有相互依赖。不同的是，AOV图中的顶点代表项目，对比后文的AOE。
4-2 AOE 最长路径
注意：与AOV相反，AOE用边来代表项目，因此边的权值可以理解为这个项目消耗的时间。
5 图的最短路径算法
5-1 迪杰斯特拉算法
注意：把书上给的图文例子看懂。
注意：此算法求的是某个给定顶点到其他各顶点的最短路径（单源）。
5-2 弗洛伊德算法
注意：把书上的图文例子看懂。
注意：此算法求的是图中所有顶点 的两两最短路径。
首先我们把图理论和编程分开看，图的概念算法应用等，可以看看离散数学。现实中图的应用很多也很有意思，比如送外卖路线规划啊，微博舆论传播分析之类的。 图算法实现就不同了，首先要理解图算法的步骤，然后设计实现的方法，在数据结构课程中无非也就是分治(也就是递归)，贪心，用什么栈和队列。 你看深搜用递归，广搜用队列，最短路径用贪心去贪。总之，图算法是理论上的东西，图算法的实现则与你是否理解基础算法有关，如果是算法理论不理解建议看离散，如果是实现上的代码不理解建议先理解基础算法，把图算法的实现作为案例去练习，相信提高会很快的。至于上面说的背下来，虽然也是一种方法，但是个人感觉不是很好，实现算法这种事情，盗用贵乎的一句话，无它，唯手熟耳！
1. 图的存储结构
1.1 邻接矩阵：用两个数组，一个数组保存顶点集，一个数组保存边集。
1.2 邻接表：数组与链表相结合的存储方法。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。
2. 图的遍历
2.1 深度优先遍历（DFS）：从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
注意：图的深度优先遍历类似于树的前序遍历。
2.2 广度优先遍历（BFS）：类似于树的层次遍历。
3. 最小生成树
最小生成树：构造连通网的最小代价生成树。
3.1 普里姆（prime）：
第一种：先将一个起点加入最小生成树，之后不断寻找与最小生成树相连的边权最小的边能通向的点，并将其加入最小生成树，直至所有顶点都在最小生成树中。
第二种：
（1）将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。
（2）首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。
（3）递归重复步骤2，直到B集合中的结点为空，结束此过程。
（4）A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。
3.2 克鲁斯卡尔（kluskal）:在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。
4. 最短路径
4.1 迪杰斯特拉算法（Dijkstra）：把图中的顶点集合V分成两组，第一组为已求出最短路径的顶点集合S（初始时S中只有源节点，以后每求得一条最短路径，就将它对应的顶点加入到集合S中，直到全部顶点都加入到S中）；第二组是未确定最短路径的顶点集合U。
算法步骤：
（1）初始化时，S只含有源节点；
（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）；
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离；
（4）重复步骤（2）和（3），直到终点在S中。
4.2 弗洛伊德算法（Floyd）：
（1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
（2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。参考：