C#图表算法之有向图

namespace Digraphs
{
    public class Digraph
    {
        private int v;
        private int e;
        private List<int>[] adj;

        public Digraph(int V)
        {
            this.v = V;
            this.e = 0;
            adj = new List<int>[v];
            for (var i = 0; i < v; i++)
            {
                adj[i] = new List<int>();
            }
        }

        public int V()
        {
            return v;
        }

        public int E()
        {
            return e;
        }

        public List<int> Adj(int v)
        {
            return adj[v];
        }

        public void AddEdge(int v, int w)
        {
            adj[v].Add(w);
            e++;
        }

        public Digraph Reverse()
        {
            Digraph R = new Digraph(v);
            for (var i = 0; i < v; i++)
                foreach (var w in Adj(i))
                    R.AddEdge(w,i);

            return R;
        }
    }
}

namespace Digraphs
{
    public class DirectedDFS
    {
        private bool[] marked;

        public DirectedDFS(Digraph G, int s)
        {
            marked = new bool[G.V()];
            Dfs(G,s);
        }

        public DirectedDFS(Digraph G, IEnumerable<int> sources)
        {
            marked = new bool[G.V()];
            foreach (var s in sources)
            {
                if (!marked[s])
                    Dfs(G,s);
            }
        }

        private void Dfs(Digraph G, int V)
        {
            marked[V] = true;
            foreach (var w in G.Adj(V))
            {
                if (!marked[w])
                    Dfs(G,w);
            }
        }

        public bool Marked(int v)
        {
            return marked[v];
        }
    }
}

namespace Digraphs
{
    public class DirectedCycle
    {
        private bool[] marked;
        private int[] edgeTo;
        private Stack<int> cycle;//有向环中的所有顶点（如果存在）
        private bool[] onStack;//递归调用的栈上的所有顶点

        public DirectedCycle(Digraph G)
        {
            onStack = new bool[G.V()];
            edgeTo = new int[G.V()];
            marked = new bool[G.V()];

            for (int v = 0; v < G.V(); v++)
            {
                if (!marked[v])
                    Dfs(G,v);
            }
        }

        private void Dfs(Digraph G, int v)
        {
            onStack[v] = true;
            marked[v] = true;
            foreach (var w in G.Adj(v))
            {
                if (hasCycle())
                    return;
                else if (!marked[w])
                {
                    edgeTo[w] = v;
                    Dfs(G, w);
                }
                else if (onStack[w])
                {
                    cycle = new Stack<int>();
                    for (int x = v; x != w; x = edgeTo[x])
                        cycle.Push(x);
                    cycle.Push(w);
                    cycle.Push(v);
                }
            }
            onStack[v] = false;
        }

        private bool hasCycle()
        {
            return cycle != null;
        }

        public IEnumerable<int> Cycle()
        {
            return cycle;
        }
    }
}

namespace Digraphs
{
    public class DepthFirstOrder
    {
        private bool[] marked;
        private Queue<int> pre;//所有顶点的前序排列
        private Queue<int> post;//所有顶点的后序排列
        private Stack<int> reversePost;//所有顶点的逆后序排列

        public DepthFirstOrder(Digraph G)
        {
            marked = new bool[G.V()];
            pre = new Queue<int>();
            post = new Queue<int>();
            reversePost = new Stack<int>();

            for (var v = 0; v < G.V(); v++)
            {
                if (!marked[v])
                    Dfs(G,v);
            }
        }

        private void Dfs(Digraph G, int v)
        {
            pre.Enqueue(v);

            marked[v] = true;
            foreach (var w in G.Adj(v))
            {
                if (!marked[w])
                    Dfs(G,w);
            }

            post.Enqueue(v);
            reversePost.Push(v);
        }

        public IEnumerable<int> Pre()
        {
            return pre;
        }

        public IEnumerable<int> Post()
        {
            return post;
        }

        public IEnumerable<int> ReversePost()
        {
            return reversePost;
        }
    }
}

namespace Digraphs
{
    public class Topological
    {
        private IEnumerable<int> order;
        public Topological(Digraph G)
        {
            DirectedCycle cycleFinder = new DirectedCycle(G);
            if (cycleFinder.HasCycle())
            {
                DepthFirstOrder dfs = new DepthFirstOrder(G);
                order = dfs.ReversePost();
            }
        }

        public IEnumerable<int> Order()
        {
            return order;
        }

        public bool IsDAG()
        {
            return order != null;
        }
    }
}

namespace Digraphs
{
    public class KosarajuCC
    {
        private bool[] marked;//已访问的顶点
        private int[] id;//强连通分量的标识符
        private int count;//强连通分量的数量

        public KosarajuCC(Digraph G)
        {
            marked = new bool[G.V()];
            id = new int[G.V()];
            DepthFirstOrder order = new DepthFirstOrder(G.Reverse());
            foreach (var s in order.ReversePost())
            {
                if (!marked[s])
                {
                    Dfs(G,s);
                    count++;
                }
            }
        }

        private void Dfs(Digraph G, int v)
        {
            marked[v] = true;
            id[v] = count;
            foreach (var w in G.Adj(v))
            {
                if (!marked[w])
                    Dfs(G,w);
            }
        }

        public bool StronglyConnected(int v, int w)
        {
            return id[v] == id[w];
        }

        public int Id(int v)
        {
            return id[v];
        }

        public int Count()
        {
            return count;
        }
    }
}

namespace Digraphs
{
    public class TransitiveClosure
    {
        private DirectedDFS[] all;

        public TransitiveClosure(Digraph G)
        {
            all = new DirectedDFS[G.V()];
            for (var v = 0; v < G.V(); v++)
                all[v] = new DirectedDFS(G,v);
        }

        public bool Reachable(int v, int w)
        {
            return all[v].Marked(w);
        }
    }
}