【摘要】图的算法是进行静态分析的基础数据算法，如何提高图的分析效率，就需要对图的算法有进一步的认识。
1. 引言
在静态分析技术中, 我们常用会将代码转成抽象语法树(AST), 然后采用深度遍历（DFS）来完成对语法树的遍历和查询，找到潜在的问题缺陷。
对于语义的分析，我们采用的控制流和数据流也都无一例外的采用了以图为基础的算法, 通过图的可达性, 来完成变量、表达式的可达分析, 以及变量的依赖分析、值流图等等。
图的算法是进行静态分析的基础数据算法，如何提高图的分析效率，就需要对图的算法有进一步的认识。
1.1. 故事从1986年的图灵奖说起
1986年的图灵奖是John E.和 E·两人共同获得， 而且 E·曾是John E.的学生,他们的密切合作取得了算法设计与分析方面的卓越贡献, 赢得了1986年度美国计算机协会（ , ACM）图灵奖的荣誉。
1.2. 故事的前半段
在领奖的时候，John E. 做了一个“计算机科学:一门学科的出现” 的演讲， 从他自己的经历出发，展现了计算科学在那个风起云涌的年代形成的过程。
时间回到1964年，计算机才刚刚成为一门学科， 普林斯顿大学一个偶然的邀请，使本打算到美国西海岸教授电器工程的改变了自己的人生轨迹，从此投入到了计算机科学的研究。
那个时候，计算机科学的大部分课程的内容都是围绕着数字计算机电路的设计以及如何减少构造这些电路所需要的晶体管数展开的。然而, 到了六十年代中期, 技术的进步已使得晶体管马上就要被每片有多达几百个元件的计算机芯片所取代。因此, 减少晶体管数再没有么意义，那时所谓的计算机科学的课程即将过时, 必须发展新的课程。
并没有接受过正规计算机教育，只是他在斯坦福大学读电器工程学博士的时候，上过（霍夫曼编码的发明者）教的一门计算机课程，学习了开关电路、逻辑设计以及计算理论的基本知识。普林斯顿要在自动机理论方面开设一门新的课程，当时没有任何教程可以参考, 只给了他推荐了6篇论文。 其中包括：
1967年，转去康奈尔大学，转而研究算法与数据结构。他相信理论计算机科学的方法学，可以用来为算法设计发展一种科学基础,这对于实践者将是很有用的。
在七十年代初期, 在斯坦福大学度过了一年的假期, 在那里遇到 并与他同用一间办公室, 那时是二年级研究生。获得这次图灵奖的研究就是在那段合作时间里作的。
在发言的最后，还不忘呼吁，为了保持美国取得的技术和经济的领导地位，必须对计算机科学进行全国性的投入和支持。
1.3. 故事的后半段
说到，他在图论算法和数据结构领域有很大的贡献。 下面对这个大牛也做个简单的介绍。
在1969年获得了加州理工学院数学学士学位。在斯坦福大学，他获得了他的计算机科学硕士学位（1971）和博士学位(1972). 从1985年开始任教于普林斯顿大学
还拥有很多研究所和公司的工作经验， 例如：AT&T贝尔实验室、NEC研究所、es、康柏、惠普、微软等。
是一个非常高产的计算机科学家，从计算机科学出版物在线参考网站dblp收集的有关他发表在的杂志、会议和出版物，多达300+。
他独立研究的算法有：离线的LCA算法（一种优秀的求最近公共祖先的线性离线算法）、强连通分量算法（甚至比后来才发表的算法平均要快30%）、-算法（第一个平面性测试的线性算法）。
他还开发了一些重要的数据结构，比如斐波那契堆（ Heap，插入查询合并O(1)，删除O(logn)的强大数据结构）、伸展树（Splay Tree，和另外一位计算机科学家共同发明）、动态树（Link-，发明人之一）。
下图是他普林斯顿大学个人简介中的一个插图， 这个是他的另一个重要的研究领域：自适应搜索树的查询(self- tree)，在树的遍历过程中，改变树的结构以提高树的搜索效率。
他的主要荣誉：
2. 算法
图的一些基本概念：
求强连通分量就是我们今天要解决的问题，根据强连通分量定义，用双向遍历取交集的方法求强连通分量，时间复杂度为O（$N^2$+M）. 而或算法, 两者的时间复杂度都是O（N+M）。
2.1. 算法简介
算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
o DFN(u)为节点u 搜索的次序编号(时间戳);
o LOW(u)为u 或 u的子树能够追溯到的最早的栈中节点的次序号;
由定义可以得出，当 DFN(u)=LOW(u)时，以u为根的搜索子树上所有节点是一个强连通分量。
1. 当首次搜索到点u时DFN[u]=LOW[u]=time;
2. 每当搜索到一个点，把该点压入栈顶;
3. 当u和v有边相连时:
3.1. 如果v不在栈中（树枝边），DFS(v)，并且LOW[u] =min{LOW(u),LOW(v)};
3.2. 如果v在栈中（前向边/后向边），此时LOW[u] =min{LOW[u],DFN[v]}
4. 当DFN[u]=LOW[u]时，将它以及在它之上的元素弹出栈，此时，弹出栈的结点构成一个强连通分量;
5. 继续搜索，知道图被遍历完毕。
由于在这个过程中每个点只被访问一次，每条边也只被访问一次，所以算法的时间复杂度是O(n+m).
2.2. 算法伪代码
2.3. 举例演算
0.求下面有向图的强连通分量
1. 从节点0开始DFS:
2. 返回节点4:
3. 返回节点2:
4. 从节点2继续搜索到节点3:
5. 返回节点2;
6. 返回节点0;
7. 从节点0继续搜索到节点1;
8. 返回节点0;
2.4. 算法
是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是 O(N+M)。与算法相比，算法可能会稍微更直观一些。但是只用对原图进行一次DFS，不用建立逆图，更简洁。
在实际的测试中，算法的运行效率也比算法高30%左右。
3. 算法实现
为了便于后期的扩展, 适用更为广泛的图运算。 这里算法的实现中，图的表示采用了库中的.graph,你需要在pom.xml 中加入guava的依赖包如下:
为了和举例中图的特征保持一致, 图结构采用guava里的 graph,的值表示结点的编号。 例如 graph.(0, 2); 表示增加一条有向边, 从结点0 指向 结点2, graph 会判断结点0 和2 是否存在结点中存在, 如不存在, 则会增加相应的结点。
大家可以根据自己的需要采用不同的图结构。
o JUNG:2016.9.8 – 2.1.1. 据说作者正在打算采用 的guava 重写这个工程;
o :2020.6.15 – 1.5.0. 这个是目前很活跃的一个图基础数据包, 里面也实现算法, 后面有时间去看下具体的实现。 Maven依赖的引用如下:
3.1. 算法代码
3.2. 验证代码
验证代码使用junit完成结果的验证。生成可变图graph里面的:(.()), 是为了保证关联边的读取时和输入的顺序一致, 以便得到和前面演算过程的一致性的结果.
4. 结论5. 参考
1. JohnE. 简介
2. 1986年图灵奖John E.发言： : OF A
3. 简介
4. dblp – Endre
5. Depth- and Graph
6. Guava Grpah
本文分享自华为云社区《史上最清晰的算法详解》，原文作者：。
点击关注，第一时间了解华为云新鲜技术~
———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载 点击查看详情
站 长 微 信： nanadh666
