20161114【充实计划】第280期 - 第5页

41楼

andwandw 发表于 2016-11-14 11:17:55

昨天阅读5小时，累计阅读162小时。

已有 1 人评分	论坛币	收起理由
充实每一天	+ 10	精彩帖子

总评分: 论坛币 + 10 查看全部评分

42楼

IT小渣渣 发表于 2016-11-14 11:27:51

[试着用思想来投资] 20161114【充实计划】第280期

时间：2016-11-14 参与挑战30天第3天

1.今天你阅读到的有价值的全文内容链接
因为所有内容都是总结性质的，用到的全文内容链接太多，我觉得没有必要一一列举出来，将内容整理好全部放在段落摘录内。
图论相关的内容，之前这一块算是没有好好学，现在补一下，看到网上大部分的判断图连通的算法都是由C，C++实现的，少数用Java实现，打算全部看懂以后，转用Python重新写一遍，这次只是算法概念的描述，大体上的总结，有兴趣的坛友可以一起探讨，需要的话，可以整理成帖子重新发出来，在这里主要是写给自己看哒

2.今天你阅读到的有价值的内容段落摘录
判断图的连通性：
深度优先遍历 DFS
DFS有两个主要特点，即：深度优先搜索形成的不再是一棵树，而是深度优先森林、节点的发现时间和完成时间具有括号性。之所以形成优先森林，是因为在进行深度优先遍历时，到达某个节点的源节点不唯一。具有括号性是指：如果开始搜索记为“（”，结束搜索记为“）”，则左右的括号都适当的嵌套在一起。通过括号性，我们可以更好的理解深度优先遍历的过程。其实现的时间复杂度为O(v2)

广度优先遍历 BFS
BFS的特点是其搜索过的节点形成一颗广度优先树，每个节点到这棵树的根节点的距离叫做深度。BFS搜到的路径是最短路径，这里的最短路径是指经历的节点数目。BFS算法一般会用到队列作为节点的存储结构，其实现的时间复杂度为O(v+e)

Warshall 算法
【算法思想】
Warshall算法通过动态规划的形式，以多阶段决策的方式来逐步构建一个有向图的传递闭包:
1）有向图的邻接矩阵表示了一个有向图，实际上有向图的邻接矩阵我们可以看作是没有经过任何中间顶点 (即一个点仅到它的邻接点为可达) 的图的传递闭包 (传递闭包的初始条件)
2）我们可以通过一次加入一个点的方式 (一共n次，加入n个点，n步决策) 来构造最终的传递闭包：
用R0表示邻接矩阵，以后每次加入一个顶点来构造R1，R2.......Rn。
如果 r(i , j) 在Rk-1中为1，那么加入顶点k作为中间节点后，r(i , j) 在Rk中的值仍为1 (如果可达了，加入点之后肯定还是可达)
如果 r(i , j) 在Rk-1中不为1，仅当 r(i , k) = 1 且 r(k , j) = 1，r(i , j)在Rk中才为1 (如果现在不可达，仅当加入的一个中间节点可以作为一个桥梁使之可达，才可达)
【时间复杂度】
【伪代码】

算法 Warshall (A[1..n, 1..n])
// 实现计算传递闭包的Warshall算法
// 输入: 包括n个顶点有向图的临界矩阵A
// 输出: 该有向图的传递闭包
R(0) ← A
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
R(k)[i, j] ← R(k-1)[i, j] or R(k-1)[i, K] and R(k-1)[k, j]
return R(n)

复制代码

【时间复杂度】O(v3)

Tarjan 算法
【功能】
Tarjan算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。
【算法思想】
用dfs遍历G中的每个顶点，通dfn表示dfs时达到顶点i的时间，low表示i所能直接或间接达到时间最小的顶点。(实际操作中low不一定最小，但不会影响程序的最终结果)
程序开始时，time初始化为0，在dfs遍历到v时，low[v]=dfn[v]=time++，
v入栈（这里的栈不是dfs的递归时系统弄出来的栈）扫描一遍v所能直接达到的顶点k，如果 k没有被访问过那么先dfs遍历k，low[v]=min(low[v],low[k])；如果k在栈里，那么low[v]=min(low[v],dfn[k])(就是这里使得low[v]不一定最小，但不会影响到这里的low[v]会小于dfn[v])。扫描完所有的k以后，如果low[v]=dfn[v]时，栈里v以及v以上的顶点全部出栈，且刚刚出栈的就是一个极大强连通分量。
【大概的证明】
1．在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，low[v]=dfn[v]时，v一定能到达栈里v上面的顶点：
因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有low=dfn），这时如果发现low[v]=dfn[v]，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。

2 .dfs遍历时，如果已经遍历完v所能直接到达的顶点而low[v]=dfn[v]，我们知道v一定能到达栈里v上面的顶点，这些顶点的low一定小于自己的dfn，不然就会出栈了，也不会小于dfn[v],不然low [v]一定小于dfn[v],所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话low[v]也一定小于dfn[v]（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。
【时间复杂度】
因为所有的点都刚好进过一次栈，所有的边都访问的过一次，所以时间复杂度为O(n+m)
【伪代码】

tarjan(u)
{
DFN=Low=++Index // 为节点u设定次序编号和Low初值
Stack.push(u) // 将节点u压入栈中
for each (u, v) in E // 枚举每一条边
if (v is not visted) // 如果节点v未被访问过
tarjan(v) // 继续向下找
Low = min(Low, Low[v])
else if (v in S) // 如果节点v还在栈内
Low = min(Low, DFN[v])
if (DFN == Low) // 如果节点u是强连通分量的根
repeat
v = S.pop // 将v退栈，为该强连通分量中一个顶点
print v
until (u== v)
}

复制代码

Gabow 算法
【算法步骤】
步骤1:
在所有顶点中，找一个没有被访问过的节点v，以v为参数执行步骤2。否则完成。
步骤2:
记录v的访问顺序。
将v压入堆栈Path和Root。
如果v指向其它的邻接顶点，那么对于每个邻接顶点next：
1) 如果没有访问过，则以next为参数，递归执行步骤2。
2) 如果访问过，而且没有确定它属于哪个强连通分量，弹出Root栈中next之后所有的顶点
如果Root栈的顶元素等于v，那么在Part中记录顶点对应的的强连通分量。
最后递归返回。
【时间复杂度】O(v+e)

拓扑排序 (多用于有向图)
拓扑排序就是将有向图中节点间的关系转化为线性关系。拓扑排序可以用于查看图中是否存在环，如果存在环则无法进行拓扑排序。但是，在下面的程序中，我们假设图中不存在环。对于无向图来说，因为节点间的关系是对称的，所以节点不能进行拓扑排序。拓扑排序其实很简单，其过程如下：每次从节点集合中选出一个节点A，且A的入度为0，然后修改以A为使点的节点的入度，按上述过程依次进行，直到节点集合为空或者不存在拓扑排序为止。这个过程可以通过DFS的括号性来表示，即：拓扑排序就是将节点按着完成时间进行降序排序
【算法思想】
1) 从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;
2) 从有向图中删去此顶点以及所有以它为尾的弧;
【算法步骤】
1.构造空列表 L和S；
2.把所有没有依赖节点的节点放入L；
3.当L还有节点的时候，执行下面步骤：
      3.1 L中拿出一个节点ｎ（从L中remove掉），并放入S
      3.2  对每一个邻近n的节点m，
         3.2.1 去掉边（n,m）;（表示加入最终结果集S）
         3.2.2 如果m没有依赖节点，把m放入L;
【时间复杂度】O(n+e)

3.今天你阅读到的有价值信息的自我思考点评感想
谈一谈关于图的连通性判断的用途：根据所构建的图的不同，连通性判断可以被转化成多种含义，一开始死学理论的时候，觉得这块内容就是跟数学有关，直到接触了实际数据，才知道它的用途变化多端，然后重新开始学习(出来混迟早是要还的)，在这里不想讲打算用图的连通性去做什么，这一块大家接触的不一样，研究方向不同，会有很大差距。我想说：不要轻视任何模块的知识，只要我们投入时间学习了，就应将它转化、吸收、存储起来，哪怕通过学习它还是我们的短板，但至少这个短板长高过。哈哈，说的有些煽情！
结合自己的经历，之前对这一块的知识就是各种混乱，每次想要做连通性判断的时候，能想到的都是转化成文本，利用文本匹配的相关知识进行判断，所以嘛，虽然现在还是不清不楚的，但是想要去尝试一下哈，先把自己之前写的一两个小的demo换用判断图连通的算法实现一下，看看效果！

4.昨日你阅读的时间量：2.5 小时
5.你参与活动至今的总时间量：6 小时