有向图—拓扑排序,Kosaraju算法

in 数据结构 with 0 comment

有向图基本算法

  1. 对于有向图的结构,和无向图类似,甚至更简单,有疑问请留言。
    1>有向图的数据结构
package graphTheory;
/**
  * @author luoz 
  * @date 2016年9月19日 下午9:26:21 
**/
public class Digraph {
    
    private final int V;
    private int E;
    private Bag<Integer>[] adj;
    
    public Digraph(int V)
    {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[])new Bag[V];
        for(int i = 0;i<V;i++)
            adj[i] = new Bag<>();
    }
    
    public int V()
    {
        return V;
    }
    public int E()
    {
        return E;
    }
    
    public void addEdge(int v,int w)
    {
        adj[v].add(w);
        E++;
    }
    
    public Iterable<Integer> adj(int v)
    {
        return adj[v];
    }
    
    public Digraph reverse()
    {
        Digraph g = new Digraph(V);
        for(int j = 0; j<V;j++)
            for(int w : adj[j])
                g.addEdge(w,j);
        return g;
    }
}
  1. 基于深度优先遍历的顶点排序
    1>前序:在递归调用之前将顶点加入队列;

2>后序:在递归调用之后将顶点加入队列;
3>逆后序:在递归调用之后将顶点压入栈;

package graphTheory;

import java.util.*;
import javax.management.Query;

/**
  * @author luoz 
  * @date 2016年9月19日 下午10:11:48 
**/
public class DepthFirstOrder {
    
    private boolean[] marked;
    //pre order
    private Queue<Integer> pre;
    //postorder
    private Queue<Integer> post;
    //reverse postorder
    private Stack<Integer> repost;
    
    public DepthFirstOrder(Digraph g)
    {
        marked = new boolean[g.V()];
        pre = new LinkedList<>();
        post =  new LinkedList<>();
        repost = new Stack<>();
        for(int i = 0;i<g.V();i++)
            if(!marked[i])
                dfs(g,i);
    }
    
    private void dfs(Digraph g,int v)
    {
        pre.add(v);
        marked[v] = true;
        for(int w : g.adj(v))
            if(!marked[w])
                dfs(g,w);
        post.add(v);
        repost.add(v);
    }
    
    public Iterable<Integer> pre()
    {
        return pre;
    }
    
    public Iterable<Integer> post()
    {
        return post;
    }
    
    public Iterable<Integer> reversepost() {
        return repost;
    }
}
  1. 检测有无环
package graphTheory;

import java.io.File;
import java.util.Stack;

/**
  * @author  luoz 
  * @date 2016年9月19日 下午9:48:41 
**/
public class DirectedCycle {
    
    private boolean[] marked;
    private int[] edgeTo;
    
    //All vertices of a directed loop
    private Stack<Integer> cycle;
    //resursion all vertices of the cycle 
    private boolean[] onStack;
    
    private boolean marked(int v)
    {
        return marked[v];
    }
    
    public boolean hasCycle()
    {
        return cycle != null;
    }
    
    public DirectedCycle(Digraph g)
    {
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
        onStack = new boolean[g.V()];
        for(int i = 0;i<g.V();i++)
            if(!marked[i])
                dfs(g,i);
    }
    
    private void dfs(Digraph g,int v)
    {
        marked[v] = true;
        onStack[v] = true;
        for(int w : g.adj(v))
        {
            if(this.hasCycle())
                return;
            else if(!marked[w])
            {
                edgeTo[w] = v;
                dfs(g,w);
            }
            else if(onStack[w])
            {
                cycle = new Stack<Integer>();
                for(int i = v; i != w; i = edgeTo[i])
                    cycle.push(i);
                cycle.push(w);
                cycle.push(v);
            }
            onStack[v] = false;
        }        
    }
    
    public Iterable<Integer> cycle()
    {
        return cycle;
    }
    /*测试代码,从文件中读取的,可以自己写测试代码*/
    public static void main(String[] args) {
        FileIo fileio = new FileIo();
        String s = fileio.characterReader(new File("cycle.txt"));
        String[] st = s.split(",");
        
        Digraph g = new Digraph(13);
        
        int E = st.length;
        for(int i = 0;i<E;i++)
        {
            String[] str = st[i].split(" ");
            g.addEdge(Integer.parseInt(str[0]),Integer.parseInt(str[1]));            
        }
        DirectedCycle cc = new DirectedCycle(g);
        System.out.println(cc.hasCycle());
        System.out.println(cc.cycle);
    }

}

拓扑排序

拓扑排序只针对有向无环图。
一幅有向无环图的拓扑排序,也就是所有顶点的逆后序排列。

package graphTheory;

/**
  * @author  luoz
  * @date 2016年9月20日 上午8:30:05 
**/
public class Topological {
    
    private Iterable<Integer> order;
    
    public Topological(Digraph g)
    {
        DirectedCycle hascycle = new DirectedCycle(g);
        if(!hascycle.hasCycle())
        {
            DepthFirstOrder df = new DepthFirstOrder(g);
            order = df.reversepost();
        }    
    }
    
    public Iterable<Integer> order()
    {
        return order;
    }
}

Kosaraju算法

计算强连通分量的算法。
主要运用了图G的反转和顶点排序的逆后序。

package graphTheory;
/**
  * @author  luoz
  * @date 2016年9月20日 上午9:08:53 
**/
public class KosarajuSCC {
    
    private boolean[] marked;
    private int[] id;
    private int count;
    
    public KosarajuSCC(Digraph g)
    {
        marked = new boolean[g.V()];
        id = new int[g.V()];
        //
        DepthFirstOrder df = new DepthFirstOrder(g.reverse()); 
        for(int i : df.reversepost())  
            if(!marked[i])
            {
                dfs(g,i);
                count++;
            }
    }
    private void dfs(Digraph g,int v)
    {
        marked[v] = true;
        id[v] = count;
        for(int w :g.adj(v))
            if(!marked[w])
                dfs(g,w);
    }
    public int count()
    {
        return count;
    }
    
    public boolean connected(int v,int w)
    {
        return id[v] == id[w];
    }
}

算法第四版

Responses