《算法》（第4版）第4章读书笔记
图的应用
在计算中，常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图，称为“算图”或“诺模图”。计算时根据已知条件，从有关线段上一点开始，连结相关线段上的点，连线与表示所求量线段的交点即为答案。 [1]
无向图、有向图和网络能运用很多常用的图算法。这些算法包括：各种遍历算法（这些遍历类似于树的遍历），寻找最短路径的算法，寻找网络中最低代价路径的算法，回答一些简单相关问题（例如，图是否是连通的，图中两个顶点间的最短路径是什么，等等）的算法。 [2]
一些性质
-
一个自我循环是一个顶点连接到其自身的优势。
-
如果它们连接同一对顶点，则 两条边是平行的。
-
当边连接两个顶点时，我们说顶点彼此 相邻，并且边缘 入射在两个顶点上。
-
顶点 的程度是入射在其上的边的数量。
-
甲子图是曲线图的边（和相关联的顶点）的子集构成的曲线图。
-
图中的路径是由边连接的顶点序列。一个简单的路径是一个不重复的顶点。
-
甲周期是路径（具有至少一个边缘），其第一和最后的顶点是相同的。一个简单的循环是一个循环，没有重复的边或顶点（除了必要的重复第一个和最后一个顶点）。
-
路径或循环 的长度是其边数。
-
我们说如果存在包含它们的路径，则一个顶点连接到另一个顶点。
-
如果存在从每个顶点到每个其他顶点的路径， 则连接图形。
-
未连接的图形由一组 连接的组件组成，这些组件是最大连接子图。
-
一个非循环图是没有循环的曲线图。
-
甲树是无环连接图。
-
一个森林是一个不相交集的树木。
-
一个生成树的连通图的是一个包含所有图的顶点，是一个单一的树子。甲生成森林的曲线图是其连接的组件的生成树的联合。
-
一个二分图是一个顶点，我们可以分成两个集合，使得所有边缘的一组与另一组顶点连接顶点的图形
-
。
最常用的图处理代码
有趣问题-走迷宫深度优先搜索
public class DepthFirstSearch {
private boolean[] marked;
private int count;
public DepthFirstSearch(Graph G, int s) {
marked = new boolean[G.V()];
validateVertex(s);
dfs(G, s);
}
// depth first search from v
private void dfs(Graph G, int v) {
count++;
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
public boolean marked(int v) {
validateVertex(v);
return marked[v];
}
public int count() {
return count;
}
private void validateVertex(int v) {
int V = marked.length;
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
int s = Integer.parseInt(args[1]);
DepthFirstSearch search = new DepthFirstSearch(G, s);
for (int v = 0; v < G.V(); v++) {
if (search.marked(v))
StdOut.print(v + " ");
}
StdOut.println();
if (search.count() != G.V()) StdOut.println("NOT connected");
else StdOut.println("connected");
}
}
l 有向图：由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点（顶点分别称为头和尾）。
l 单点可达性：是否存在一条从s到给定顶点v的有向路径。多点可达性：是否存在一条从集合中的任意顶点到达给定顶点v的有向路径。在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。
l 单点有向路径，单点最短有向路径。优先级限制下的调度问题。拓扑排序：给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）。拓扑排序典型应有：任务调度，课程安排，继承，电子表格，符号链接。
l 如果一个有优先级限制的问题中存在有向环，那么这个问题一定是无解的。有向无环图（DAG）：就是一幅不含有向环的有向图。
l 当且仅当一幅有向图是无环图时它才能进行拓扑排序。一幅有向无环图的拓扑排序即为所有顶点的逆后序排列。使用深度优先搜索对有向无环图进行拓扑排序所需的时间和V+E成正比。
l 解决任务调度类应用通常需要以下三步：指明任务和优先级条件；不断检测并去除有向图中的所有环以确保存在可行方案；使用拓扑排序解决调度问题。
l 强连通：两个顶点互相可达。强连通图：一幅有向图中任意两个顶点都是强连通的。强连通性具有：自反性，对称性，传递性。
l Kosaraju算法：高效计算强连通分量。使用深度优先查找给定有向图G的方向图GR，根据由此得到的所有顶点的逆后序再次深度优先搜索处理有向图G（Kosaraju算法），其构造函数中的每一次递归调用所标记的顶点都在同一个强连通分量之中。Kosaraju算法的预处理所需的时间和空间与V+E成正比且支持常数时间的有向图强连通性的查询。
l 图的生成树：是它的一棵含有其所有顶点的无环连通子图。
l 一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树。
l 一些约定：只考虑连通图（非连通图不存在最小生成树，只有最小生成森林）；边的权重不一定表示距离；边的权重也可能是0或者负数（边权重都为正数的话最小生成树定义为连接所有顶点且总权重最小的子图就足够了）；所有边的权重都各不相同（若权重可以相同那么最小生成树就不一定是唯一的了，但这个假设并不会限制算法的适用范围）。
l 图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点和边。
l 切分定理：在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。
l 最小生成树的贪心算法：下面这种方***将含有V个顶点的任意加权连通图中属于最小生成树的边标记为黑色：初始状态下所有边均为灰色，找到一种切分它产生的横切边均不为黑色，将它权重最小的横切边标记为黑色，反复，知道标记了V-1条黑色边为止。
l Prim算法：计算最小生成树的方法，它的每一步都会为一棵生长中的树添加一条边，一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边（黑色表示）加入树中（即由树中的顶点所定义的切分中的一条横切边）。能够计算任意加权连通图的最小生成树。
l Prim算法的延时实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间与E成正比，所需的时间与ElogE成正比（最坏情况）。
l Prim算法的即时实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需空间和V成正比，所需的时间和ElogV成正比（最坏情况）。
l Kruskal算法：按照边的权重顺序（从小到大）处理它们，将边加入最小生成树中（图中的黑色边），加入的边不会与已经加入的边构成环，直到树中含有V-1条边为止。这些黑色的边逐渐由一片森林合并为一棵树，也就是图的最小生成树。Kruskal算法能能够计算任意加权连通图的最小生成树。
Kruskal算法代码实现
public static void kruskal(Graph g) {
// 每个顶点加编号
int[] parent = new int[g.MAX_VERTEX ];
for (int i = 0; i < g.MAX_VERTEX; i++) {
parent[i] = i;
}
// 找到n-1条边，既满足条件
while (result.size() < (g.MAX_VERTEX-1) ) {
// 取最小边
double min = MOUSTMAX;
int jtemp=0;
int i = 0;
for(int k=0;k<g.MAX_VERTEX;k++){
for (int j = 0; j < g.MAX_VERTEX; j++) {
// System.out.println("-------------"+k+"--"+j + "parent[" + k + "]--"+parent[k]+"parent[" + j+"]" +parent[j] + "--"+g.L1_Matrix[k][j] + "min" + min);
if ((parent[k] != parent[j] ) && g.L1_Matrix[k][j] < min) {
min = g.L1_Matrix[k][j];
jtemp = j;
i=k;
}
}
}
int jj = parent[i];
int kk = parent[jtemp];
proc.add("------选中结点 "+i+" 与结点 "+jtemp + " ，路径长度：" + g.L1_Matrix[i][jtemp]);
//判断该边的两个端点是否在同一个子树中：
// 不在：将该边加入结果集
// 在：继续循环
if (kk != jj) {
int tempi = parent[i];
//将新找到的边的顶点与以前的顶点标志值设为一样，注意要把以前的顶点相连的顶点都要同步改变值
for(int j = 0; j<parent.length;j++){
if(parent[j] == tempi )
parent[j] = parent[jtemp];
}
//取出已经加入的边
boolean temp = true;
for(Vertex[] v:result){
if(v[0] == g.vertexList[i] && v[1] ==g.vertexList[jtemp]){
temp = false;
}
if(v[1] == g.vertexList[i] && v[0] ==g.vertexList[jtemp]){
temp = false;
}
}
if(temp){
result.add(new Vertex[] { g.vertexList[i],g.vertexList[jtemp] } );
}
//将已找到的边，权值设为最大
g.L1_Matrix[i][jtemp] = MOUSTMAX;
}
}
}
l Kruskal算法的计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间和E成正比，所需的时间和ElogE成正比（最坏情况）。
l Prim算法和Kruskal算法不能处理有向图处理问题。有向图更难，称为最小树形图问题。
l 在一幅加权有向图中，从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者。
l 最短路径的性质：路径是有向的；权重不一定等价于距离；并不是所有顶点就是可达的；负权重会使问题更复杂；最短路径一般都是简单的；最短路径不一定是唯一的；可能存在平行边和自环。
l 最短路径树：给定一幅加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含s和从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。
l 放松***作（relax）：放松边v->w意味着检查从s到w的最短路径是否是先从s到v，然后再由v到w。如果是，则根据这个情况更新数据结构的内容。由v到达w的最短路径是distTo[v]与e.weight()之和，如果这个值不小于distTo[w]，称这条边失效了并将它忽略，如果这个值更小就更新数据。（松弛术语来源于橡皮筋比喻：放松一条边就像将橡皮筋转移到一条更短的路径上，从而缓解了橡皮筋的压力）
l 最短路径的最优性条件：令G为一幅加权有向图，顶点s是G中的起点，distTo[]是一个由顶点索引的数组，保存的是G中路径的长度，对于从s可达的所有顶点v，distTo[v]的值是从s到v的某条路径的长度，对于从s不可达的所有顶点v，该值为无穷大。当且仅当对于从v到w的任意一条边e，这些值都是满足distTo[w]<=distTo[v]+e.weight()时（换句话说，不存在有效边时），它们是最短路径的长度。
l 通用最短路径算法：将distTo[s]初始化为0，其他distTo[]元素初始化为无穷大，继续如下***作：放松G中的任意边，直到不存在有效边为止。对于任意从s可达的顶点w，在进行这些***作之后，distTo[w]的值即为从s到w的最短路径的长度（且edgeTo[w]的值即为该路径上的最后一条边）。
l Dijkstra算法：首先将distTo[s]初始化为0，distTo[]中的其他元素初始化为正无穷，然后将distTo[]最小的非树顶点放松并加入树中，如此这般，直到所有的顶点都在树中或者所有的非树顶点的distTo[]值均为无穷大。Dijkstra算法能够解决边权重非负的加权有向图的单起点最短路径问题。
l 在一幅含有V个顶点和E条边的加权有向图中，使用Dijkstra算法计算根结点为给定起点的最短路径树所需的空间与V成正比，时间与ElogV成正比（最坏情况下）。
l 无环加权有向图中的最短路径算法：能够在线性时间内解决单点最短路径问题；能够处理负权重的边；能够解决相关的问题，例如找出最长的路径。
l 按照拓扑排序放松顶点，就能在和E+V成正比的时间内解决无环加权有向图的单点最短路径问题。
l 解决无环加权有向图中的最长路径问题所需的时间与E+V成正比。
l 解决并行任务调度问题的关键路径方法的步骤如下：创建一幅无环加权有向图，其中包含一个起点s和一个重点t且每个任务都对应着两个顶点（一个起始顶点和一个结束顶点）。对于每个任务都有一条从它的其实顶点指向结束顶点的边，边的权重为任务所需的时间。对于每条优先级限制v->w添加一条从v的结束顶点指向w的起始顶点的权重为0的边。我们还需要为每个任务添加一条从起点指向该任务的其实顶点的权重为0的边以及一条从该任务的结束顶点到终点的权重为0的边。这样每个任务预计的开始时间即为从起点到它的起始顶点的最长距离。
l 解决优先级限制下的并行任务调度问题的关键路径算法所需的时间为线性级别。
l 相对最后期限限制下的并行任务调度问题是一个加权有向图中的最短路径问题（可能存在环和负权重边）。
l 负权重环：加权有向图中的负权重环是一个总权重(环上的所有边的权重之和)为负的有向环。（绕着这个环一直转圈子就能将总权重降到任意小的权重值）
l 当且仅当加权有向图中至少存在一条从s到v的有向路径且所有从s到v的有向路径上的任意顶点都不存在与任何负权重环中时，s到v的最短路径才是存在的。
l Bellman-Ford算法：在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环，以下算法能够解决其中的单点最短路径问题：将distTo[s]初始化为0，其他distTo[]元素初始化为无穷大，以任意顺序放松有向图的所有边，重复V轮。Bellman-Ford算法所需的时间和EV成正比，空间和V成正比；
l 套汇问题等价于加权有向图中的负权重环的检测问题
#读书笔记##笔记#
科锐国际HR面27人在聊