如圖，所有的邊都是向下的，所以清晰地表示了這幅有向圖模型所代表的有優(yōu)先級(jí)限制的調(diào)度問題的一個(gè)解決方法：按照這個(gè)順序，該同學(xué)可以滿足先導(dǎo)課程限制的條件下修完所有課程。

有向圖中的環(huán)

如果任務(wù) x 必須在任務(wù) y 之前完成，而任務(wù) y 必須在任務(wù) z 之前完成，但任務(wù) z 又必須在任務(wù) x 之前完成，那肯定是有人搞錯(cuò)了，因?yàn)檫@三個(gè)限制條件是不可能被同時(shí)滿足的。一般來說，如果一個(gè)優(yōu)先級(jí)限制的問題中存在有向環(huán)，那么這個(gè)問題肯定是無解的。要檢查這種錯(cuò)誤，需要解決 有向環(huán)檢測：給定的有向圖中包含有向環(huán)嗎？如果有，按照路徑的方向從某個(gè)頂點(diǎn)并返回自己來找到環(huán)上的所有頂點(diǎn)。

一幅有向圖中含有環(huán)的數(shù)量可能是圖的大小的指數(shù)級(jí)別，因此我們只需找到一個(gè)環(huán)即可，而不是所有環(huán)。在任務(wù)調(diào)度和其他許多實(shí)際問題中不允許出現(xiàn)有向環(huán)，因此有向無環(huán)圖就變得很特殊。

基于深度優(yōu)先搜索可以解決有向環(huán)檢測的問題，因?yàn)橛上到y(tǒng)維護(hù)的遞歸調(diào)用的棧表示的正是“當(dāng)前”正在遍歷的有向路徑。一旦我們找到了一條有向邊 v -> w 且 w 已經(jīng)存在于棧中，就找到了一個(gè)環(huán)，因?yàn)闂１硎镜氖且粭l由 w 到 v 的有向路徑，而 v -> w 正好補(bǔ)全了這個(gè)環(huán)。如果沒有找到這樣的邊，就意味著這副有向圖是無環(huán)的。DirectedCycle 基于這個(gè)思想實(shí)現(xiàn)的：

namespace Digraphs
{
    public class DirectedCycle
    {
        private bool[] marked;
        private int[] edgeTo;
        private Stack<int> cycle;//有向環(huán)中的所有頂點(diǎn)（如果存在）
        private bool[] onStack;//遞歸調(diào)用的棧上的所有頂點(diǎn)

        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;
        }
    }
}

該類為標(biāo)準(zhǔn)的的遞歸 Dfs 方法添加了一個(gè)布爾類型的數(shù)組 onStack 來保存遞歸調(diào)用期間棧上的所有頂點(diǎn)。當(dāng)它找到一條邊 v -> w 且 w 在棧中時(shí)，它就找到了一個(gè)有向環(huán)。環(huán)上的所有頂點(diǎn)可以通過 edgeTo 中的鏈接得到。

在執(zhí)行 Dfs 時(shí)，查找的是一條由起點(diǎn)到 v 的有向路徑。要保存這條路徑，DirectedCycle 維護(hù)了一個(gè)由頂點(diǎn)索引的數(shù)組onStack，以標(biāo)記遞歸調(diào)用的棧上的所有頂點(diǎn)（在調(diào)用 Dfs 時(shí)將 onStack[ v ] 設(shè)為 true,在調(diào)用結(jié)束時(shí)將其設(shè)為 false）。DirectedCycle 同時(shí)也使用了一個(gè)edgeTo 數(shù)組，在找到有向環(huán)時(shí)返回環(huán)中的所有頂點(diǎn)。

頂點(diǎn)的深度優(yōu)先次序與拓?fù)渑判?/h3>

優(yōu)先級(jí)限制下的調(diào)度問題等價(jià)于計(jì)算有向無環(huán)圖中的所有頂點(diǎn)的拓?fù)渑判颍?/p>

下面算法的基本思想是深度優(yōu)先搜索正好只會(huì)訪問每個(gè)頂點(diǎn)一次。如果將 Dfs 的參數(shù)頂點(diǎn)保存在一個(gè)數(shù)據(jù)結(jié)構(gòu)中，遍歷這個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)際上就能訪問圖中的所有頂點(diǎn)，遍歷的順序取決于這個(gè)數(shù)據(jù)結(jié)構(gòu)的性質(zhì)以及是在遞歸調(diào)用之前還是之后進(jìn)行保存。在典型的應(yīng)用中，頂點(diǎn)一下三種排列順序：

• 前序：在遞歸調(diào)用之前將頂點(diǎn)加入隊(duì)列；
• 后序：在遞歸調(diào)用之后將頂點(diǎn)加入隊(duì)列；
• 逆后序：在遞歸調(diào)用之后將頂點(diǎn)壓入棧。

該類允許用例用各種順序遍歷深度優(yōu)先搜索經(jīng)過得頂點(diǎn)。這在高級(jí)得有向圖處理算法非常有用，因?yàn)樗阉鞯眠f歸性使得我們能夠證明這段計(jì)算得許多性質(zhì)。

namespace Digraphs
{
    public class DepthFirstOrder
    {
        private bool[] marked;
        private Queue<int> pre;//所有頂點(diǎn)的前序排列
        private Queue<int> post;//所有頂點(diǎn)的后序排列
        private Stack<int> reversePost;//所有頂點(diǎn)的逆后序排列

        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;
        }
    }
}

一幅有向無環(huán)圖得拓?fù)渑判蚣礊樗许旤c(diǎn)的逆后序排列。

拓?fù)渑判?/h3>

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;
        }
    }
}

這段使用DirectedCycle 檢測是否有環(huán)，使用DepthFirstOrder 返回有向圖的逆后序。

使用深度優(yōu)先搜索對(duì)有向無環(huán)圖進(jìn)行拓?fù)渑判蛩璧臅r(shí)間和 V+E 成正比。第一遍深度優(yōu)先搜索保證了不存在有向環(huán)，第二遍深度優(yōu)先搜索產(chǎn)生了頂點(diǎn)的逆后序排列。

在實(shí)際應(yīng)用中，拓?fù)渑判蚝陀邢颦h(huán)的檢測總是一起出現(xiàn)，因?yàn)橛邢颦h(huán)的檢測是排序的前提。例如，在一個(gè)任務(wù)調(diào)度應(yīng)用中，無論計(jì)劃如何安排，其背后的有向圖中包含的環(huán)意味著存在一個(gè)必須被糾正的嚴(yán)重錯(cuò)誤。因此，解決任務(wù)調(diào)度類應(yīng)用通常需要一下3步：

• 1.指明任務(wù)和優(yōu)先級(jí)條件；
• 2.不斷檢測并去除有向圖中的所有環(huán)，以確保存在可行方案；
• 3.使用拓?fù)渑判蚪鉀Q調(diào)度問題。

類似地，調(diào)度方案的任何變動(dòng)之后都需要再次檢查是否存在環(huán)，然后再計(jì)算新的調(diào)度安排。

5.有向圖中的強(qiáng)連通性

如果兩個(gè)頂點(diǎn) v 和 w 是相互可達(dá)的，則稱它們?yōu)閺?qiáng)連通的。也就是說，即存在一條從 v 到 w 的有向路徑，也存在一條從 w 到 v 的有向路徑。如果一幅有向圖中的任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱這副有向圖也是強(qiáng)連通的。

下面是強(qiáng)連通圖的例子，可以看到，環(huán)在強(qiáng)連通性的理解上起著重要的作用。

強(qiáng)連通分量

和無向圖中的連通性一樣，有向圖中的強(qiáng)連通性也是一種頂點(diǎn)之間的等價(jià)關(guān)系：

• 自反性：任意頂點(diǎn) v 和自己都是強(qiáng)連通的。
• 對(duì)稱性：如果 v 和 w 是強(qiáng)連通的，那么 w 和 v 也是。
• 傳遞性：如果 v 和 w 是強(qiáng)連通的且 w 和 x 也是強(qiáng)連通的，那么 v 和 x 也是強(qiáng)連通的。

作為一種等價(jià)關(guān)系，強(qiáng)連通性將所有頂點(diǎn)分為了一些等價(jià)類，每個(gè)等價(jià)類都是由相互均為強(qiáng)連通的頂點(diǎn)的最大子集組成。我們稱這些子集為強(qiáng)連通分量。如下圖，一個(gè)含有 V 個(gè)頂點(diǎn)的有向圖含有 1~ V個(gè)強(qiáng)連通分量——一個(gè)強(qiáng)連通圖只含有一個(gè)強(qiáng)連通分量，而一個(gè)有向無環(huán)圖則含有 V 個(gè)強(qiáng)連通分量。需要注意的是強(qiáng)連通分量的定義是基于頂點(diǎn)的，而不是邊。有些邊連接的兩個(gè)頂點(diǎn)都在同一個(gè)強(qiáng)連通分量中，而有些邊連接的兩個(gè)頂點(diǎn)則不在同一強(qiáng)連通分量中。

強(qiáng)連通分量API

設(shè)計(jì)一種平方級(jí)別的算法來計(jì)算強(qiáng)連通分量并不困難，單對(duì)于處理實(shí)際應(yīng)用中的大型圖來說，平方級(jí)別的時(shí)間和空間需求是不可接受的。

Kosaraju算法

在有向圖中如何高效地計(jì)算強(qiáng)連通分量？我們只需修改無向圖連通分量的算法 CC，KosarajuCC 算法如下，它將會(huì)完成一下任務(wù)：

1.在給定的一幅有向圖 G 中，使用 DepthFirstOrder 來計(jì)算它的反向圖 GR 的逆后序排列；

2.在 G 中進(jìn)行標(biāo)準(zhǔn)的深度優(yōu)先搜索，但是要按照剛才計(jì)算得到的順序而非標(biāo)準(zhǔn)的順序來訪問所有未被標(biāo)記的頂點(diǎn)；

3.在構(gòu)造函數(shù)中，所有在同一個(gè)遞歸 Dfs() 調(diào)用中被訪問到的頂點(diǎn)都在同一個(gè)強(qiáng)連通分量中，將它們按照和 CC 相同的方式識(shí)別出來。

namespace Digraphs
{
    public class KosarajuCC
    {
        private bool[] marked;//已訪問的頂點(diǎn)
        private int[] id;//強(qiáng)連通分量的標(biāo)識(shí)符
        private int count;//強(qiáng)連通分量的數(shù)量

        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;
        }
    }
}

Kosaraju 算法的預(yù)處理所需的時(shí)間和空間與 V+E 成正比且支持常數(shù)時(shí)間的有向圖強(qiáng)連通性的查詢。

再談可達(dá)性

在無向圖中如果兩個(gè)頂點(diǎn) V 和 W 是連通的，那么就既存在一條從 v 到 w 的路徑也存在一條從 w 到 v 的路徑。在有向圖中如果兩個(gè)頂點(diǎn) v 和 w 是強(qiáng)連通的，那么就既存在一條從 v 到 w 的路徑也存在另一條從 w 到 v 的路徑。但對(duì)于一對(duì)非強(qiáng)連通的頂點(diǎn)，也許存在一條從 v 到 w 的路徑，也許存在一條從 w 到 v 的路徑，也許兩條都不存在，但不可能兩條都存在。

頂點(diǎn)對(duì)的可達(dá)性：對(duì)于無向圖，等價(jià)于連通性問題；對(duì)于有向圖，它和強(qiáng)連通性有很大區(qū)別。 CC 實(shí)現(xiàn)需要線性級(jí)別的預(yù)處理時(shí)間才能支持常數(shù)時(shí)間的操作。在有向圖的相應(yīng)實(shí)現(xiàn)中能否達(dá)到這樣的性能？

有向圖 G 的傳遞閉包是由相同的一組頂點(diǎn)組成的另一幅有向圖，在傳遞閉包中存在一條從 v 指向 w 的邊當(dāng)且僅當(dāng)在 G 中 w 是從 v 可達(dá)的。

根據(jù)約定，每個(gè)頂點(diǎn)對(duì)于自己都是可達(dá)的，因此傳遞閉包會(huì)含有 V 個(gè)自環(huán)。上圖只有 22 條有向邊，但它的傳遞閉包含有可能的 169 條有向邊中的 102 條。一般來說，一幅有向圖的傳遞閉包中所含的邊都比原圖中多得多。例如，含有 V 個(gè)頂點(diǎn)和 V 條邊的有向環(huán)的傳遞閉包是一幅含有 V 的平方條邊的有向完全圖。因?yàn)閭鬟f閉包一般都是稠密的，我們通常都將它們表示為一個(gè)布爾值矩陣，其中 v 行 w 列的值為 true 當(dāng)且僅當(dāng) w 是從 v 可達(dá)的。與其計(jì)算一幅有向圖的傳遞閉包，不如使用深度優(yōu)先搜索來實(shí)現(xiàn)如下API：

下面的算法使用DirectedDFS 實(shí)現(xiàn)：

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);
        }
    }
}

該算法無論對(duì)于稀疏圖還是稠密圖，都是理想解決方案，但對(duì)于大型有向圖不適用，因?yàn)闃?gòu)造函數(shù)所需的空間和 V 的平方成正比，所需的時(shí)間和 V(V+ E) 成正比。

總結(jié)

到此這篇關(guān)于C#圖表算法之有向圖的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。