有向图3----顶点排序和拓扑排序

拓扑排序：给定一幅有向图，将所有顶点排序，使得所有有向边均从排在前面的元素指向排在后面的元素

有向图DAG：一幅不含有向环的有向图

当且仅当一幅有向图是无环图时，才能进行拓扑排序

顶点排序

进行深度优先搜索DFS时，每个顶点会遍历一遍，其中顶点访问的顺序有三种：

前序：顶点访问的顺序   递归之前保存在队列中

后序：顶点完成相邻顶点访问的顺序   递归之后保存在队列中

逆后序：顶点完成相邻顶点访问的逆顺序   递归之后保存在栈中

对于下图进行顶点排序

                                                            

临接表：

0: 6--->5--->1 1: 2: 3--->0 3: 5 4: 5: 4 6: 9--->4 7: 6 8: 7 9: 12--->11--->10 10: 11: 12 12:

前序：

[0, 6, 9, 12, 11, 10, 4, 5, 1, 2, 3, 7, 8]

后序

[12, 11, 10, 9, 4, 6, 5, 1, 0, 3, 2, 7, 8]

逆后序

[8, 7, 2, 3, 0, 1, 5, 6, 4, 9, 10, 11, 12]

代码实现：

package com.digraph; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack; import com.graph.Graph; import com.swt.GraphUtils; //有向图 dfs 顶点排序 //dfs搜索每个顶点会访问一遍 顶点的排序顺序 public class DepthFirstOrder { private boolean[] marked; //dfs过程中 顶点访问顺序 private Queue<Integer> pre; //dfs过程中 某个顶点率先完成所有相邻顶点的访问顺序 private Queue<Integer> post; //dfs过程中 某个顶点率先完成所有相邻顶点的逆序访问顺序 private Stack<Integer> reversePost; public DepthFirstOrder(Digraph g){ marked = new boolean[g.V()]; pre = new LinkedList<>(); post = new LinkedList<>(); reversePost = new Stack<>(); for(int v=0; v<g.V(); v++){ if(!marked[v]){ dfs(g, v); } } } private void dfs(Digraph g, int v) { marked[v] = true; //访问该顶点则加入pre队列 pre.add(v); for(int w : g.adj(v)){ if(!marked[w]){ dfs(g, w); } } //顶点v所有相邻顶点都访问完毕则加入队列，由于递归其首先访问完成的在队列的最前面，最先输出 post.add(v); //顶点v所有相邻顶点都访问完毕则加入栈 首先完成的在栈最下面，最后输出 reversePost.push(v); } public Iterable<Integer> pre(){ return this.pre; } public Iterable<Integer> post(){ return this.post; } public Iterable<Integer> reversePost(){ List<Integer> l = new ArrayList<>(); while(!this.reversePost.isEmpty()){ l.add(this.reversePost.pop()); } return l; } }

基于顶点排序实现拓扑排序

顶点排序的逆后序顺序即为顶点的拓扑排序

顶点排序，进行dfs  假定某一条边v-->w，则有先调用dfs(v)，再调用dfs(w)，其中dfs(w)先完成，即后序顺序w在v之前，而逆后序顺序v在w之前，因此逆后序即为拓扑排序

首先判断是否有环，然后利用dfs深度优先搜索，进行顶点排序，返回逆后序顺序

//拓扑排序 顶点排序逆后序实现方式 public class Topological { private Iterable<Integer> order; public Topological(Digraph g){ DirectedCycle dc = new DirectedCycle(g); if(!dc.hasCycle()){ DepthFirstOrder dfo = new DepthFirstOrder(g); this.order = dfo.reversePost(); } } public Iterable<Integer> order(){ return this.order; } public boolean isDAG(){ return order != null; } public static void main(String[] args) { Digraph g = GraphUtils.getDiGraphPointG2().getG(); System.out.println(g.toString()); Topological t = new Topological(g); System.out.println(t.order()); } }

基于队列实现拓扑排序

给定一张有向图，研究一下图的入度以及出度性质。给定Degrees来实现某一个顶点的出入度，以及图的起始点集合和终点集合。

起始点即为入度=0的顶点，终点即为出度=0顶点

//研究一张图的入度出度问题 public class Degrees { private int[] outdegree; private int[] indegree; public Degrees(Digraph g){ outdegree = new int[g.V()]; indegree = new int[g.V()]; for(int v=0; v<g.V(); v++){ for(int w : g.adj(v)){ indegree[w]++; outdegree[v]++; } } } //v入度 public int indegree(int v){ return indegree[v]; } //v出度 public int outdegree(int v){ return outdegree[v]; } //起始点结合 入度=0 Iterable<Integer> sources(){ List<Integer> l = new ArrayList<>(); for(int v=0; v<indegree.length; v++){ if(indegree[v]==0) l.add(v); } return l; } //终点集合 出度=0 Iterable<Integer> sinks(){ List<Integer> l = new ArrayList<>(); for(int v=0; v<outdegree.length; v++){ if(outdegree[v]==0) l.add(v); } return l; } public int[] indegree(){ return this.indegree; } public int[] outdegree(){ return this.outdegree; } //映射概念 形成自环 每个顶点出度为1 public boolean isMap(){ for(Integer out : outdegree){ if(out != 1) return false; } return true; } public static void main(String[] args) { Digraph g = GraphUtils.getDiGraphPointG2().getG(); System.out.println(g.toString()); Degrees d = new Degrees(g); System.out.println(d.isMap()); System.out.println(d.sources()); System.out.println(d.sinks()); System.out.println(d.indegree(0) + " " + d.outdegree(0)); } }

给定一张有向图，获取其起始点集合加入到队列中，并保存每个顶点的入度数据，从队列中取出一个元素，将该元素的所有相邻元素入度减一，如果某个相邻元素入度为0，则加入到队列中，重复直到队列为空，此时出队的顺序即为拓扑排序顺序；

//拓扑排序队列实现方式 public class TopologicalQueue { private List<Integer> order = new ArrayList<>(); //所有顶点入度索引数组 private int[] indegree; //队列 private Queue<Integer> q = new LinkedList<>(); private boolean isDAG; public TopologicalQueue(Digraph g){ //判断有无环 DirectedCycle dc = new DirectedCycle(g); if(!dc.hasCycle()){ this.isDAG = true; } //求出图中所有入度=0顶点 Degrees d = new Degrees(g); this.indegree = d.indegree(); for(Integer s : d.sources()){ q.add(s); order.add(s); } //将入度为零顶点s的所有相邻顶点入度-1 如果-1之后==0，则加入到队列中去 //重复此过程，直到队列为空 //队列中元素访问顺序即为一种拓扑排序 while(!q.isEmpty()){ int s = q.poll(); for(int v : g.adj(s)){ indegree[v]--; if(indegree[v]==0){ q.add(v); order.add(v); } } } } public Iterable<Integer> order(){ return this.order; } public boolean isDAG(){ return this.isDAG; } public static void main(String[] args) { Digraph g = GraphUtils.getDiGraphPointG2().getG(); System.out.println(g.toString()); TopologicalQueue t = new TopologicalQueue(g); System.out.println(t.isDAG()); System.out.println(t.order()); } }