疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

拓扑排序 两种实现方式


 

拓扑排序是无环有向图很重要的应用,在任务调度等方面有很广泛的应用!
首先能拓扑排序的有向图,必然无环!
所以对于给定的一个有向图,首先判定网中是否存在环!
1.删除前驱法。
1)在有向图中选择一个没有前驱的顶点,并输出之
2)从图中删除该顶点和所有以它为尾的弧
import java.util.*;
public class TopologicalSort{
   //有向图G采用邻接表存储结构
   //若G无回路,则输出G的顶点的一个拓扑序列,并返回OK;否则error
   private static int[] indegree;
   public static void FindInDegree(DiGraph G){//对各顶点求入度
    indegree=new int[G.V()];
    for(int i=0;i<G.V();i++){
       Iterator<Integer> Dfsit=G.adj(i);
  while(Dfsit.hasNext()){
  int w=Dfsit.next();
  indegree[w]++;
  }  
   }
   }
   public static void Topolog(DiGraph G){
     FindInDegree(G);
     MyStack<Integer> stack=new MyStack<Integer>();
for(int i=0;i<G.V();i++)//入度为0进栈
   if(indegree[i]==0)
stack.push(i);
   int count=0;//对输出的顶点计数
    while(!stack.isEmpty()){
         int t=stack.pop();
         System.out.print(t+" ");
count++; //输出顶点,并计数
       Iterator<Integer> Dfsit=G.adj(t);
  while(Dfsit.hasNext()){
  int w=Dfsit.next();
  if((--indegree[w])==0)//对t每个邻接点的入度减1
   stack.push(w);//如果入度减为0,则进栈
  }
    }
    if(count<G.V())
      System.out.println("拓扑排序不存在");
else
        System.out.println("拓扑排序成功");
  }
    public static void main(String[] args){
 DiGraph demo6=new DiGraph();
 Topolog(demo6);
}
  }
   
当有向图无环时,也可深度优先搜索遍历进行拓扑排序,因为图中无环,则由图中某点出发进行深度优先搜索遍历,最早推出DFS函数的顶点即为出度为0的顶点,是拓扑排序有序数列的最后一个顶点。由此,按退出DFS函数的先后记录下来的顶点序列即为逆向拓扑有序序列!
import java.util.Iterator;
 
public class TopologicalSort2 {
   static boolean[] marked;//这里只是声明引用,并没有创建对象
   int[] edgeTo;//可以不初始化,但是必须也要建立对象与引用间的的联系
   int s;
   private static MyStack<Integer> stack=new MyStack<Integer>();
   
   TopologicalSort2(DiGraph G){
  marked=new boolean[G.V()];//此处才为真正的创建对象,并连接对象和引用
  edgeTo=new int[G.V()];
  for(int i=0;i<G.V();i++)
   if(!marked[i])
   DFS(G,i);
   }
   public void DFS(DiGraph G,int v){
  marked[v]=true;
  Iterator<Integer> Dfsit=G.adj(v);
  while(Dfsit.hasNext()){
  int w=Dfsit.next();
  if(!marked[w]){
  DFS(G,w);
  edgeTo[w]=v;
  }
       }
  stack.push(v);//逆后序序列,即为拓扑序列
   }
   public static void main(String[] args){
 DiGraph demo6=new DiGraph();
 new TopologicalSort2(demo6);
 while(!stack.isEmpty())
  System.out.print(stack.pop()+" ");
 
 
   }
   }