概览： 无向图、有向图、加权无向图求最小生成树、加权有向图求最短路径。
图
无向图（简单连接）
图是由一组定点和一组能够将两个定点相连的边组成的。
特俗的图： 自环；连接同一对顶点的两条边成为平行边（多重图）。
术语：
相邻：当两个顶点通过一条边相连时，称两个顶点时相邻的，并称该连接依附于这两个顶点。
度数：某个顶点的度数即为依附于他的边的总数。
子图：子图是由一幅图的所有边的一个子集（以及她们所依附的的所有顶点）组成的图。
路径：路径是由边顺序连接的一系列顶点。
简单路径：简单路径是一条没有重复顶点的路径。
环：环是一条至少含有一条边且起点和终点相同的路径。
简单环是一条（除起点和终点必须相同之外）不含有重复顶点和边的环。
路径或环的长度为其中所包含的边数。
当两个顶点存在路径，称两顶点连通。
如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是联通图。一副非联通的图由若干个联通的部分组成，他们都是其极大连通子图。
树是一副无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是他的一副子图，她含有图中的所有顶点且是一棵树。图的生成深林是她的所有连通子图的生成树的集合。
当一副V个节点的图G满足下列5个条件之一时，她就是一棵树：
- G有V-1条边且不含有环；
- G有V-1条边且是连通的；
- G是连通的，但删除任意一条边都会使他不在连通；
- G是无环图，但添加任意一条边都会产生一条环；
- G中的任意一对顶点之间仅存在一条简单路径。
图的密度是指已经连接的顶点对 占 所有可能被连接的顶点对的比例。
图的几种表示方法
要求：
- 他必须为可能在应用中碰到的各种类型的图预留出足够的空间；
- Graph的实例方法的实现一定要快————他们是开发处理图的各种用例基础。
表示方法：
- 邻接矩阵。可以使用V*V的布尔矩阵。当v与w之间有相连接边时，定义v行w列的值为true。这种方法不符合条件1。
- 边的数组。可以使用一个Edge类，含有连个int实例变量。不符合条件2————要实现检查图中的所有边。
- 邻接表数组。使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表。
图的处理算法的设计模式：
将图的表示和实现分离开来。为每个任务创建一个相应的类，用例可以创建相应的对象来完成任务。
深度优先搜索dfs：
- 选择一条没有标记过的通道，在走过的路上铺一条绳子；
- 标记所有你第一次路过的路口和通道；
- 当来到标记过的路口时回退到上个路口；
- 当回退到的路口已没有可走的通道时继续回退；
要搜索一幅图，只需用一个递归方法来遍历所有顶点。在访问其中一个顶点时：
- 将它标记为以访问；
- 递归地访问它的所有没有被标记过的邻居顶点。
深度优先搜索标记和起点连通的所有顶点所需的时间和顶点的度数之和成正比。
深度优先搜索中每条边都会被访问两次，且在第二次时总会发现这个顶点已经被标记过，这意味着深度优先搜索的轨迹可能比想象的长一倍。
连通性问题：给定一幅图，回答两个给定的顶点是否连通 或者图中有多少个连通子图？等类似问题。
单点路径：给定一幅图和一个起点s，回答 从s到给定目的顶点v是否存在一条路径？如果有，找出这条路径。等类问题。
使用一个布尔数组记录已经使用深度优先搜索的顶点
使用一个整型数组记录每个顶点到起点的路径，记录方法为索引为当前顶点编号，索引的数组值为上一个顶点编号，组成一颗由起点为根节点构成的树，向上递归即可获得到达顶点的路径，再使用栈逆序即可。如edgeTo[w]=v表示v-w第一次访问w是经历的边。
判断s到v是否连通，看v上是否被标记为以使用深度优先搜索，即marked[v]
广度优先搜索：
单点最短路径。给定一幅图和一个起点s，从s到给定目的顶点v是否存在一条路径？如果有，找出其中最短的那条。
广度优先搜索BSF：要找到s到v的最短路径，从s开始，在所有邻接点中寻找v，如果找不到就继续在与s距离两条边的顶点中查找v，如此一直进行。
深度优先搜索中，用了一个下压栈，使用LIFO（后进先出）的规则，从有待搜索的通道中选择最晚遇到过的那条。在广度优先搜索中，使用FIFO（先进先出）队列，从有待搜索的通道中选择最早遇到的那条。
实现：
先将起点加入队列，然后重复一下步骤直到队列为空：
- 取队列中的下一个顶点v并标记她。
- 将与v相邻的所有未标记过的顶点加入队列。
两个算法的不同之处仅在于从数据结构中获取下一个顶点的规则，对于广度优先搜索来说，是最早加入的顶点，对于深度优先搜索来说是最晚加入的顶点。
深度优先搜索不断深入图中并在栈中保存了所有分叉的顶点；广度优先搜索则像扇面一般扫描图，用一个队列保存访问过的最前端的顶点。
连通分量：
使用一个数组保存节点编号对应的连通分量。使用一个布尔数组判断一个节点是否被递归搜索过。使用一个整型字典保存连通分量数量。
检测环：
给定的环是无环图吗。在深度优先搜索时，在判断已经标记的分支里进行比较，邻接点与当前顶点相同，即自环。
双色问题：
能够用两种颜色将所有图的所有顶点着色，使得任意一条边的两个端点的颜色都不相同吗？等价于：这是一副二分图吗？
再多一个布尔数组存放节点对应颜色，在判断未标记的分支里着色并递归，在判断已标记的分支汇总判断当前节点与邻接点是否同色，一直无，则是二分图。
符号图：
为适应实际应用，图的格式：
- 顶点名为字符串；
- 用指定的分隔符来隔开顶点名；
- 每一行表示一组边的集合，每一条边都连接着这一行的第一个名称表示的顶点和其他名称所表示的顶点；
- 顶点总数V和边的总数E都是隐式定义的。
实现：
符号图的数据类型，用到一下3中数据结构：
- 一个符号表st,键的类型为String（顶点名），值的类型为int（索引）；
- 一个数组keys[]，用作反向索引，保存每个顶点所对应的顶点名；
- 一个Graph对象G，他使用索引来引用图中顶点。
有向图（连接有方向性）
有向图是由一组顶点和一组有方向的边组成，每条有方向的边都连接着有序的一对顶点。
初度为由该顶点指出的边的总数；入度为指向该顶点的边的总数。
有向路径由一系列顶点组成，对于其中每个顶点都有一条边从它指向下一个顶点。
有向图的表示：使用邻接表，和无向图区别在于每次添加边只需一次操作，且含有一个逆序方法，以便获取指入的边。
有向图的可达性：单点可达性，多点可达性。使用深度优先遍历。
应用：标记-清除的垃圾回收算法；有向图的寻路。
环和有向无环图：
调度问题： 限制优先级。
拓扑排序： 给定一副有向图，对所有顶点排序，使所有有向边从排在前面的元素指向后面的元素。
有向图中的环：
有向环的检测，给定的有向图中包含有向环吗。按照路径方向从某个顶点并返回自己来找到换上所有顶点。
维护一个顶点索引数组onStack[]，标记递归调用栈上所有顶点，使用一个edgeTo[] 数组，在找到有向环时返回环中所有顶点。
顶点的深度优先次序与拓扑排序：
有向图中基于深度优先搜索的顶点排序，基本思想：深度优先搜索证号只会访问每个顶点一次，如果将dfs()的参数顶点保存一个数据结构中，遍历这个数据结构就能访问图中所有顶点，遍历的顺序取决于数据结构性质以及似乎在递归调用之前还是之后保存。
- 前序：在递归调用之前将顶点加入队列
- 后序：在递归调用之后将顶点加入队列
- 逆后序：递归调用之后将顶点压入栈。
拓扑排序及为逆后续排序。记得要先检查是否有向无环图DAG。
解决任务调度类应用通常需要一下3步：
- 指明任务和优先级条件；
- 不断检测并去除有向图中的所有环，以确保可行方案；
- 使用拓扑排序解决调度问题。
有向图中的强连通性
如果两个顶点v和w是相互可达的，则称他们为强连通的。如果一副有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的。
有向图中的强连通性也是一种顶点之间平等关系，自反性、对称性、传递性。
强连通性将所有顶点分为了一些平等的部分，每个部分都是由相互均为强连通的顶点的最大子集组成的。称这些子集为强连通分量。
一个含有V个顶点的有向图含有1-V个强连通分量———— 一个强连通图只含有一个强连通分量，而一个有向无环图中则含有V个强连通分量。需要注意的是强连通分量的定义是基于顶点的，而非边。
强连通性是一种非常重要的抽象，她突出了相互关联的几组顶点（强连通分量）。
Kosaraju 算法：
- 在给定的一副有向图G中，使用DepthFirstOrder来计算她的反向图G(R)的逆后续排列。
- 在G中进行标准的深度优先搜索，但是要按照刚才计算得到的顺序而非标准的顺序来访问所有未被标记的顶点。
- 在构造函数中，所有在同一个递归dfs()调用中被访问到的顶点都在同一个强连通分量中，将他们按照和CC相同的方式识别。
顶点对的可达性：给定一副有向图，是否存在一条从一个给定的顶点v到另个给定顶点w的路径？
有向图G的传递闭包是由相同的一组顶点组成的另一幅有向图，在传递闭包中存在一条从v指向w的边当且仅当在G中w是从v可达的。
一副有向图的传递闭包通常是稠密图，通常将他们表示为一个布尔值矩阵，其中v行w列的值为true当且仅当w是从v可达的。
加权图（连接带有权值） 最小生成树
加权图是一种为每条边关联一个权值或是成本的图模型。
最小生成树。图的生成树是她的一颗含有其所有顶点的无环连通子图。一副加权无向图的最小生成树（MST）是她的一颗权值（树中所有边的权值之和）最小的生成树。
约定：
- 只考虑连通图。最小生成树只可能存在于连通图中。如果一幅图是非连通的，只能计算所有连通分量的最小生成树，合并在一起称为最小生成深林。
- 边的权重不一定表示距离。
- 边的权重可能是0或者负数。
- 所有边的权重各不相同。如果不同边的权重可以相同，最小生成树就不一定唯一了。
我们假设任务目标是在一副加权（但权值各不相同的）连无向图中找到她的最小生成树。
原理：
树性质：
- 用一条边连接树中的任意两个顶点都会产生一个新的环。
- 从树中删去一条边将会得到两颗独立的树。
切分定理：
图的一种切分是将图的所有顶点分为两个非空且不重复的两个集合。横切边是一条连接两个属于不同集合的顶点的边。
贪心算法：
使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。这些算法相互之间的不同之处在于保存切分和判断权重最小的横切边的方式。
最小生成树的贪心算法：
下面这种方法将含有V个顶点的任意加权连通图中属于最小生成树的边标记为黑色：初始状态下所有边均为灰色，找到一种切分，他产生的横切边均不为黑色。将它权重最小的横切边标记为黑色。反复，直到标记了V-1条黑色边为止。
最小生成树的API：
在API中会定义一个接收加权无向图为参数的构造函数并且支持能够为永利返回图的最小生成树和其权重。
如何表示最小生成树：
- 一组边的列表；
- 一副加权无向图；
- 一个以顶点为索引且含有父节点连接的数组。
Prim 算法：
每一步都会为一颗生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向他添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入树中（即由树中的顶点所定义的切分中的一条横切边）。
维护横切边的集合：每当我们向树中添加了一条边之后，也向树中添加了一个顶点。要维护一个包含所有横切边的集合，就要将连接这个顶点和其他所有不在树中的顶点的边加入优先队列。
连接新加入树中的顶点与其他已经在树中顶点的所有边都失效了。即时实现可将这样的边从优先队列中删掉，延时实现是将这些边先留在优先队列中，等到要删除他们时候在检查边的有效性。
最小生成树的生长过程：从0开始，向外扩展，每次都会把树的每个点的所有树外的邻接边放入最小堆，取出权重最小的邻接边加入树中，若邻接边另一端已在树中则丢弃，以此往复，直到队列为空。
Prim 算法的即时实现：
我们感兴趣的只是连接树中顶点和非树顶点中所有邻接边中权重最小的边。
只会在优先队列中保存每个非树顶点w的一条边：将他与树中的顶点连接起来的权重最小的那条边。
Kruskal 算法：
按照边的权重顺序处理他们，将边加入最小生成树，加入的边不会与已经加入的边构成环，知道树中含有V-1条边为止。
加权有向图（连接既有方向性又带有权值） 最短路径
问题：找到一个顶点到另一个顶点的成本最小的路径。
单点最短路径：给定一副加权有向图和一个起点s，从s到给定目的顶点v是否存在一条有向路径？如果有，找出最短（总权重最小）路径。
- 加权有向图的API和实现，以及单点最短路径的API;
- 解决边的权重非负的最短路径问题的经典Dijkstra算法;
- 在无环加权图中解决问题的一种快速算法，边的权重也可以是负值。
- 适用于一般情况的经典Bellman-Ford算法，其中图可以含有环，变得权重也可以是负值。需要算法找出负权重的环，以及不含有这种环的加权有向图中的最短路径。
最短路径的性质
- 路径是有向的。
- 权重不一定等价于距离。
- 并不是所有顶点都是可达的。为简化问题，例图都是强连通的。
- 负权重会使问题更复杂。
- 最短路径一般都是简单的。
- 最短路径不一定是唯一的。
- 可能存在平行边和自环。
最短路径树：
单点最短路径问题，给出起点s，计算的结果是一颗最短路径树（SPT），包含了顶点s到所有可达的顶点的最短路径。
最短路径的数据结构：
最短路径树中的边：使用一个顶点索引的DirectedEdge对象的父链接数组edgeTo[],其中edgeTo[v]的值为树中连接v和他的父节点的边。
到达起点的距离：需要一个由顶点索引的数组distTo[]，其中distTo[v]为从s到v的已知最短路径的长度。
边的松弛：
方式边v->w意味着从s到w的最短路径是否先从s到v，然后再由v到w。如果是，则根据这个情况更新数据结构内容。
顶点的松弛：
放松从一个顶点指出的所有边。
Dijkstra算法
首先将distTo[s] 初始化为0，distTo[] 中的其他元素初始化为正无穷。然后将distTo[]最小的非树顶点放松并加入树中，如此这般，直到所有的顶点都在树中或者所有的非树顶点的distTo[]值均为无穷大。
另一个角度来理解：已知树节点所对应的distTo[]值均为最短路径长度。对于优先队列中任意顶点w，distTo[w]是从s到w的最短路径长度，该路径上所有顶点均在树中且路径上最后条边为edgeTo[w]。优先级最小的顶点distTo[]值就是最短路径的权重。不会小于已经被放松过的任意顶点的最短路径的权重，也不会大于还未被放松过的任意顶点的最短路径权重。这个顶点就是下一个要被放松的顶点。所有从s可达的顶点都会按照最短路径的权重顺序被放松。
计算最短路径Dijkstra算法和最小生成树Prim算法对比：都会用添加边的方式构造一棵树，Prim算法每次添加的都是离树最近的非树顶点，Dijkstra算法每次添加的都是离起点最近的非树顶点。都不需要marked[]数组。
无环加权有向图中的最短路径算法
只要将顶点的放松和拓扑排序结合起来，就能得到一个解决无环加权有向图中的最短路径问题的算法。
首先将distTo[s]初始化为0，其他distTo[]元素初始化为无穷大，然后一个一个第按照拓扑顺序放松所有顶点。
最长路径：
无环加权有向图中的单点最长路径，即最长（总权重最大）的那条路径。
修改AcyclicSP，将distTo[]的初始值变为Double.NEGATIVE_INFINITY并改变relax()方法中不等式方向，即放松操作时取权重大的边。
平行任务调度：
优先级限制下的并行任务调度。给定一组需要完成的特定任务，以及一组关于任务完成的先后次序的优先级限制。如何在若干相同的处理器上安排任务并在最短时间内完成？
单个处理器情况：将任务按照拓扑顺序排序，完成任务的总耗时就是所有任务所需要总时间。
多处理器情况：关键路径。
