大佬教程收集整理的这篇文章主要介绍了【数据结构】有向图，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
在有向图中，边是单向的：每条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图：比如任务調度的依赖关系，社交网络的任务关系等等都是天然的有向图。
以下概念都是针对有向图的：
（1）==有向图==：一幅有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
（2）==顶点的出度==：该顶点指出的边的总数。
（3）==顶点的入度==：指向该顶点的边的总数。
（4）比如对于有序对(w,v) 一般代表w->v 的一条有向边。
（5）==有向路径==：由一系列顶点组成，其中每个顶点都存在一条有向边从它指向序列中的下一个顶点。
（6）==有向环==：为一条至少含有一条边且起点和终点相同的有向路径。
（7）==简单有向环==：是一条除了起点和终点外，不含有重复的顶点和边的环。
首先定义有向图的API接口，DiGraph 本质上和Graph是一样的。
| public class Digraph | |
|---|---|
| Digraph(int v) | 创建一幅含有v个顶点，但是没有边的有向图 |
| Digraph(In in) | 从输入流中读取一幅有向图 |
| int E() | 边的总数 |
| int V() | 边的总数 |
| void addEdge(int v,int w) | 添加一条有向边v ->w |
Iterble<Integer>adj(int v) |
由顶点v出发的有向边所连接的所有顶点 |
| Digraph reverse() | 该图的反向图 |
| String toString() | 对象的字符串表示形式 |
和无向图的表示类似，我们还是使用 ==邻接表== 来存储有向图，其中边 v—>w 表示为顶点v所对应的邻接链表中包含一个w顶点。
上面的API中给出了reverse() 方法，将有向图中的所有有向边反转，并生成副本。
使用邻接表来存储有向图，用数组来表示图中的每个节点的集合，并且数组的下标就表示节点的标识符。
下面就是有向图的实现方式：
package com.example.algorithm4.graphs;
import edu.prinCETon.cs.algs4.bag;
/** * 有向图的实现 * * @author 惜暮 * @email chris.lyt@alibaba-inc.com * @date 2017/12/7 */
public class DiGraph {
/** * 节点的总个数 */
private final int V;
/** * 边的总个数 */
private int E;
/** * 有向图的邻接表表示法 */
private Bag<Integer>[] adj;
/** * 创建一个含有V个节点，但是0条边的有向图 * @param V */
public DiGraph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[])new Bag[V];
for (int i=0; i<this.V; i++){
adj[V] = new Bag<>();
}
}
public int E(){
return this.E;
}
public int V(){
return this.V;
}
/** * 添加一条 v-->w 的边 * @param v 有向边的源在数组中的标识符 * @param w 有向边的终在数组中的标识符 */
public void addEgge(int v,int w){
adj[v].add(w);
this.E++;
}
/** * 节点v 的所有出度的终顶点 * @param v 节点v 的标识符 * @return */
public Iterable<Integer> adj(int v){
return adj[v];
}
/** * 此有向图反转之后的副本 * @return */
public DiGraph reverse(){
DiGraph reverse = new DiGraph(this.V);
for(int i=0 ;i<this.V; i++){
for (int w : adj[i]){
//边反转
reverse.addEgge(w,i);
}
}
return reverse;
}
}
有向图的邻接表表示和无向图的邻接表表示区别不大，仅仅在于边的处理上有一点区别。如果对于有向图的结点的标识我们也想用字符串来表示呢？其实现方法几乎和无向图一样，增加一个Map用来保存顶点的符号到数组下表的映射关系，然后用字符数组保存所有的符号，数组下标天然表示每个顶点的index。 代码实现上只需要把SymbolGraph中的Graph替换成DiGraph就可，下面也给出实现代码：
package com.example.algorithm4.graphs;
import edu.prinCETon.cs.algs4.In;
import edu.prinCETon.cs.algs4.ST;
/** * 符号有向图的实现 * @author 惜暮 * @email chris.lyt@alibaba-inc.com * @date 2017/12/7 */
public class SymbolDiGraph {
private ST<String,Integer> st; // map,顶点符号名 -> 数组索引
private String[] keys; // 数组索引 -> 顶点符号名
private DiGraph G; // 图
/** * 构造一颗符号有向图 * @param stream 顶点边的数据源 * @param sp 顶点分隔符 */
public SymbolDiGraph(String stream,String sp) {
st = new ST<>();
In in = new In(stream); // First pass
while (in.hasNextLine()) {// builds the index
String[] a = in.readLine().split(sp); // by reading Strings
for (int i = 0; i < a.length; i++) {// to associate each
if (!st.contains(a[i])) {// disTinct String
st.put(a[i],st.size()); // with an index.
}
}
}
keys = new String[st.size()]; //建立索引 --> 结点符号
for (String name : st.keys()) {// to get String keys
keys[st.get(Name)] = name; // is an array.
}
// 创建符号图
G = new DiGraph(st.size());
in = new In(stream); // Second pass
while (in.hasNextLine()) {// builds the graph
String[] a = in.readLine().split(sp); // by connecTing the
int v = st.get(a[0]); // source vertex
for (int i = 1; i < a.length; i++) {// on each line
G.addEdge(v,st.get(a[i])); // to all the others.
}
}
}
public Boolean contains(String s) {
return st.contains(s);
}
public int index(String s) {
return st.get(s);
}
public String name(int v) {
return keys[v];
}
public DiGraph G() {
return G;
}
}
我们在无向图中介绍的第一个算法就是DFS，其实无向图是很多算法的基础，解决了单点连通性的问题，可以判断无向图中指定的两个顶点是否连通。其思想对于有向图同样适用~
针对以上问题，设计DirectedDFS 算法的API：
| public class DirectedDFS | |
|---|---|
| DirectedDFS(DiGraph G,int s) | 在G中找到从s可达的所有顶点 |
DirectedDFS(DiGraph G,Iterable<Integer> sources) |
在G中找到从sources的所有顶点中可达的所有顶点 |
| Boolean reachable(int v) | d顶点v是可达的嘛 |
下面是有向图的可达性算法的实现：
package com.example.algorithm4.graphs;
/** * 有向图的深度优先遍历 * * @author 惜暮 * @email chris.lyt@alibaba-inc.com * @date 2017/12/7 */
public class DirectedDFS {
/** * 从起点s开始DFS访问过的路径标记 */
private Boolean[] marked;
public DirectedDFS(Digraph digraph,int s) {
this.marked = new Boolean[digraph.V()];
dfs(digraph,s);
}
public DirectedDFS(Digraph digraph,Iterable<Integer> sources) {
this.marked = new Boolean[digraph.V()];
for(int s : sources){
if (!marked[s]){
dfs(digraph,s);
}
}
}
/** * 从节点v 开始有向图的DFS * * @param digraph 有向图 * @param v 结点 */
private void dfs(Digraph digraph,int v){
this.marked[v] = true;
for (int w : digraph.adj(v)){
if(!this.marked[w]){
dfs(digraph,w);
}
}
}
public Boolean @H_209_122@marked(int v){
return marked[v];
}
}
这份深度优先搜索能够实现判断一个或则一组(多点可达性)顶点能到达哪些其他顶点。
多点可达性的一个重要的实际应用是在典型的内存管理上，比如JVM内存管理，在一幅有向图中，一个顶点代表一个对象，一条边代表一个对象对另外一个对象的引用。 有向图的模型很好的可以应用在JVM内存管理上面。当从根节点遍历时候，那么不可达的顶点就代表不会再被使用，就可以被回收以释放内存。
标记-清除的垃圾回收算法会为每个对象保存一个位作为垃圾回收之用，然后周期性的运行一个类似于DirectedDFS的有向图可达性算法来标记所有可以被访问到的对象，然后清理所有对象，回收没有被标记的对象，以达到释放内存的目的。
DepthFirstPaths 和 BreadthFirstPaths 也都是有向图处理中的重要算法。可以用处理下面问题：
下图给出了一个使用深度优先遍历在一幅有向图中寻找能够从顶点0到达的所有顶点的轨迹的示意图：
在有向图的应用场景中对于有向环的检测十分重要，因为有向环就代表着死循环，然后实际的项目中由于依赖关系的复杂，几乎不可能肉眼检测有向环，所以检测有向环是否存在就至关重要。
对于有向环的检测主要有两种方法：DSF和拓扑排序。下面以实际例子来分析
一个广泛使用的模型就是给定一组任务并安排它们的执行顺序，限制条件是这些任务的执行方法和起始时间。限制条件可能还包括任务的耗时以及消耗的其他资源。最重要的一种限制条件叫做优先级限制，它指明了哪些任务必须在哪些任务之前完成。 不同类型的限制条件会产生不同类型不同难度的调度问题
下面以一个正在安排课程的大学生为例，有些课程是其余课程的先导课程：如图：
再假设该学生一次只能修一门课，问题就可以抽象成以下模型：
优先级限制下的調度问题：给定一组需要完成的任务，以及一组关于任务完成的先后次序的优先级顺序。在满足条件下以最优方案完成任务。为了简化模型，以数字标识顶点，顶点代表任务。可以等价成下图:
上面的实例的拓扑排序图如下：所有边都朝下，清晰描绘了这幅有向图模型代表的优先级限制下調度问题的解决方法：
拓扑排序有很多典型的应用，比如任务調度，继承等等。
有向环的检测，我们可以借助于DFS算法，也可以借助拓扑排序。算法DirectedCycle 实现了环的检测，API如下:
| public class DirectedCycle | |
|---|---|
| DirectedCycle(Digraph digraph) | 寻找有向环的构造函数 |
| Boolean hasCycle() | digraph是否有环 |
Iterable<Integer> cycle() |
有向环中的所有顶点 |
下图是一个在有向环中寻找环的过程示意图：
算法实现如下：
package com.example.algorithm4.graphs;
import java.util.Stack;
/** * 有向图环的检测：DFS算法 * * @author 惜暮 * @email chris.lyt@alibaba-inc.com * @date 2017/12/7 */
public class DirectedCycle {
/** * 从起点开始DFS访问过的路径标记 */
private Boolean[] marked;
/** * 从起点到一个顶点v的已知路径上的最后一个顶点 */
private int[] edgeTo;
/** * 如果存在有向环，就保存有向环中的所有顶点。 */
private Stack<Integer> cycle;
/** * 递归调用栈上的所有顶点 * 这里类似于Java里面的一个set，里面保存了所有已经访问过的顶点 */
private Boolean[] onStack;
/** * 构造器 * * @param digraph 有向图 */
public DirectedCycle(Digraph digraph) {
this.marked = new Boolean[digraph.V()];
this.edgeTo = new int[digraph.V()];
this.onStack = new Boolean[digraph.V()];
for (int v=0; v<digraph.V(); v++) {
if( !marked[v] ) {
dfs(digraph,v);
}
}
}
/** * 从节点v 开始有向图的DFS * * @param digraph 有向图 * @param v 结点 */
private void dfs(Digraph digraph,int v){
// 标记当前结点在堆栈路径上
this.onStack[v] = true;
this.marked[v] = true;
for (int w : digraph.adj(v)){
// 如果当前图已经有环就直接返回
if (this.hasCycle(w)){
return;
} else if(!this.marked[w]){
// 如果当前结点没有被标记过，递归dfs
edgeTo[w] = v;
dfs(digraph,w);
} else if (onStack[w]){
// (1)当前结点被标记过来了，(2)而且在已经访问过得堆栈上，则存在环
cycle = new Stack<>();
for(int x = v; x!=w; x = this.edgeTo[x]) {
cycle.push(X);
}
cycle.push(w);
cycle.push(v);
}
}
// 递归回溯时，当前结点重置为不在环的堆栈上。
this.onStack[v] = false;
}
public Boolean hasCycle(int v){
return cycle!=null;
}
public Iterable<Integer> cycle(){
return cycle;
}
}
上面检测有向图是否有环的算法采用标准的递归dfs算法，添加了一个布尔型数组onStack[] 来保存递归调用期间栈上面的所有顶点。当找到一条边 v->w 且w在栈中时，就代表找到了有向环。环上所有顶点都可以通过edgeTo[]数组得到。
在优先级限制下的調度问题等价于计算有向无环图中的所有顶点的拓扑排序，因此给出如下API：
| public class Topological | |
|---|---|
| Topological(Digraph digraph) | 拓扑排序的构造函数 |
| Boolean isDAG() | 图digraph是有向无环图嘛？ |
Iterable<Integer> order() |
拓扑排序的所有顶点 |
首先我们先来看看 ==有向图中基于深度优先搜索的顶点排序== 的DepthFirstOrder算法。
其基本思想是：深度优先搜索正好只会访问每个顶点一次，如果将dfs()的参数顶点保存在一个数据结构中，遍历这个数据结构实际上就能访问图中的所有顶点，遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是调用之后进行保存。在应用中我们关注的是以下3种排列顺序：
下图是用DepthFirstOrder 算法处理有序无环图产生的轨迹。实现简单，支持处理图的高级算法中十分有用的pre()、post()和reversePost()方法。 例如Topological类中order()方法就调用了reversePost()方法。
算法实现如下：
package com.example.algorithm4.graphs;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/** * 有向图中基于深度优先搜索的顶点排序 * * @author 惜暮 * @email chris.lyt@alibaba-inc.com * @date 2017/12/7 */
public class DepthFirstOrder {
/** * 从起点开始DFS访问过的路径标记 */
private Boolean[] marked;
/** * 所有顶点的前序排列 */
private Queue<Integer> pre;
/** * 所有顶点的后序排列 */
private Queue<Integer> post;
/** * 所有顶点的逆后序排列 */
private Stack<Integer> reversePost;
public DepthFirstOrder(Digraph digraph) {
marked = new Boolean[digraph.V()];
pre = new LinkedList<>();
post = new LinkedList<>();
reversePost = new Stack<>();
for (int v=0; v<digraph.V(); v++){
if ( !marked[v] ) {
dfs(digraph,int v){
pre.add(v);
this.marked[v] = true;
for (int w : digraph.adj(v)){
if(!this.marked[w]){
dfs(digraph,w);
}
}
post.add(v);
reversePost.push(v);
}
public Iterable<Integer> pre(){
return pre;
}
public Iterable<Integer> post(){
return post;
}
public Iterable<Integer> reversePost(){
return reversePost;
}
}
该类允许使用各种顺序遍历DFS经过的顶点。这在高级的有向图处理算法中非常有用，因为搜索的递归性是的我们能够证明这段计算的许多性质。
下面给出拓扑排序==Topological==的实现算法：
package com.example.algorithm4.graphs;
/** * 有向无环图的 拓扑排序 * * @author 惜暮 * @email chris.lyt@alibaba-inc.com * @date 2017/12/7 */
public class Topological {
/** * 顶点的拓扑排序 */
private Iterable<Integer> order;
public Topological(Digraph digraph){
DirectedCycle cycleFinder = new DirectedCycle(digraph);
if( !cycleFinder.hasCycle() ) {
DepthFirstOrder dfs = new DepthFirstOrder(digraph);
order = dfs.reversePost();
}
}
public Iterable<Integer> order() {
return order;
}
public Boolean isDAG(){
return order!=null;
}
}
Topological的实现借助了DirectedCycle 检测环是否存在，借助DepthFirstOrder的逆后续来获取拓扑排序。
下面给出了一个示例 DAG 的逆后续是拓扑排序的轨迹图：
有向图的强连通性也是一种顶点之间的平等关系，因为其有着如下性质：
强连通分量就是：有向图的极大强连通子图
最典型应用就是网络，以顶点代表网页，超链接代表边。 下面给强连通分量的API：
| public class SCC | |
|---|---|
| SCC(Digraph digraph) | 预处理构造函数 |
| Boolean stronglyConnected(int v,int w) | v和w是强连通的吗？ |
| int count() | 图中强连通分量的总数 |
| int id(int v) | v所在强连通分量的标识符(0至count()-1 之间) |
以上是大佬教程为你收集整理的【数据结构】有向图全部内容，希望文章能够帮你解决【数据结构】有向图所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。