C#圖表算法之無向圖

更新時間：2022年04月24日 15:35:15 作者：Ruby_Lu

這篇文章介紹了C#圖表算法之無向圖，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

頂點叫什么名字并不重要，但我們需要一個方法來指代這些頂點。一般使用 0 至 V-1 來表示一張含有 V 個頂點的圖中的各個頂點。這樣約定是為了方便使用數(shù)組的索引來編寫能夠高效訪問各個頂點信息的代碼。用一張符號表來為頂點的名字和 0 到 V-1 的整數(shù)值建立一一對應(yīng)的關(guān)系并不困難，因此直接使用數(shù)組索引作為結(jié)點的名稱更方便且不失一般性，也不會損失什么效率。

我們用 v-w 的記法來表示連接 v 和 w 的邊， w-v 是這條邊的另一種表示方法。

在繪制一幅圖時，用圓圈表示頂點，用連接兩個頂點的線段表示邊，這樣就能直觀地看出圖地結(jié)構(gòu)。但這種直覺有時可能會誤導(dǎo)我們，因為圖地定義和繪制地圖像是無關(guān)的，一組數(shù)據(jù)可以繪制不同形態(tài)的圖像。

特殊的圖

自環(huán)：即一條連接一個頂點和其自身的邊；

多重圖：連接同一對頂點的兩條邊成為平行邊，含有平行邊的圖稱為多重圖。

沒有平行邊的圖稱為簡單圖。

1.相關(guān)術(shù)語

當(dāng)兩個頂點通過一條邊相連時，稱這兩個頂點是相鄰得，并稱這條邊依附于這兩個頂點。某個頂點的度數(shù)即為依附于它的邊的總數(shù)。子圖是由一幅圖的所有邊的一個子集（以及它們所依附的所有頂點）組成的圖。許多計算問題都需要識別各種類型的子圖，特別是由能夠順序連接一系列頂點的邊所組成的子圖。

在圖中，路徑是由邊順序連接的一系列頂點。簡單路徑是一條沒有重復(fù)頂點的路徑。環(huán)是一條至少含有一條邊且起點和終點相同的路徑。簡單環(huán)是一條（除了起點和終點必須相同之外）不含有重復(fù)頂點和邊的環(huán)。路徑或環(huán)的長度為其中所包含的邊數(shù)。

當(dāng)兩個頂點之間存在一條連接雙方的路徑時，我們稱一個頂點和另一個頂點是連通的。

如果從任意一個頂點都存在一條路徑到達(dá)另一個任意頂點，我們稱這副圖是連通圖。一幅非連通的圖由若干連通的部分組成，它們都是其極大連通子圖。

一般來說，要處理一張圖需要一個個地處理它的連通分量（子圖）。

樹是一幅無環(huán)連通圖。互不相連的樹組成的集合稱為森林。連通圖的生成樹是它的一幅子圖，它含有圖中的所有頂點且是一棵樹。圖的生成森林是它的所有連通子圖的生成樹的集合。

樹的定義非常通用，稍作改動就可以變成用來描述程序行為（函數(shù)調(diào)用層次）模型和數(shù)據(jù)結(jié)構(gòu)。當(dāng)且僅當(dāng)一幅含有 V 個結(jié)點的圖 G 滿足下列 5 個條件之一時，它就是一棵樹：

G 有 V - 1 條邊且不含有環(huán)；
G 有 V - 1 條邊且是連通的；
G 是連通的，但刪除任意一條都會使它不再連通；
G 是無環(huán)圖，但添加任意一條邊都會產(chǎn)生一條環(huán)；
G 中的任意一對頂點之間僅存在一條簡單路徑；

圖的密度是指已經(jīng)連接的頂點對占所有可能被連接的頂點對的比例。在稀疏圖中，被連接的頂點對很少；而在稠密圖中，只有少部分頂點對之間沒有邊連接。一般來說，如果一幅圖中不同的邊的數(shù)量在頂點總數(shù) v 的一個小的常數(shù)倍以內(nèi)，那么我們認(rèn)為這幅圖是稀疏的，否則就是稠密的。

二分圖是一種能夠?qū)⑺薪Y(jié)點分為兩部分的圖，其中圖的每條邊所連接的兩個頂點都分別屬于不同的集合。

2.表示無向圖的數(shù)據(jù)結(jié)構(gòu)

圖的幾種表示方法

接下來要面對的圖處理問題就是用哪種數(shù)據(jù)結(jié)構(gòu)來表示圖并實現(xiàn)這份API，包含下面兩個要求：

1.必須為可能在應(yīng)用中碰到的各種類型圖預(yù)留出足夠的空間；
2.Graph 的實例方法的實現(xiàn)一定要快。

下面有三種選擇：

1.鄰接矩陣：我們可以使用一個 V 乘 V 的布爾矩陣。當(dāng)頂點 v 和 w 之間有連接的邊時，定義 v 行 w 列的元素值為 true，否則為 false。這種表示方法不符合第一個條件--含有上百萬個頂點的圖所需的空間是不能滿足的。
2.邊的數(shù)組：我們可以使用一個 Edge 類，它含有兩個 int 實例變量。這種表示方法很簡單但不滿足第二個條件--要實現(xiàn) Adj 需要檢查圖中的所有邊。
3.鄰接表數(shù)組：使用一個以頂點為索引的列表數(shù)組，其中每個元素都是和該頂點相連的頂點列表。

非稠密圖的標(biāo)準(zhǔn)表示成為鄰接表的數(shù)據(jù)結(jié)構(gòu)，它將每個頂點的所有相鄰頂點都保存在該頂點對應(yīng)的元素所指向的一張鏈表中。我們使用這個數(shù)組就是為了快速訪問給定頂點的鄰接頂點列表。這里使用 Bag 來實現(xiàn)這個鏈表，這樣我們就可以在常數(shù)時間內(nèi)添加新的邊或遍歷任意頂點的所有相鄰頂點。

要添加一條連接 v 與 w 的邊，我們將 w 添加到 v 的鄰接表中并把 v 添加到 w 的鄰接表中。因此在這個數(shù)據(jù)結(jié)構(gòu)中每條邊都會出現(xiàn)兩次。這種 Graph 的實現(xiàn)的性能特點：

1.使用的空間和 V+E 成正比；
2.添加一條邊所需的時間為常數(shù)；
3.遍歷頂點 v 的所有相鄰頂點所需的時間和 v 的度數(shù)成正比。

對于這些操作，這樣的特性已經(jīng)是最優(yōu)的了，而且支持平行邊和自環(huán)。注意，邊的插入順序決定了Graph 的鄰接表中頂點的出現(xiàn)順序。多個不同的鄰接表可能表示著同一幅圖。因為算法在使用 Adj() 處理所有相鄰的頂點時不會考慮它們在鄰接表中的出現(xiàn)順序，這種差異不會影響算法的正確性，但在調(diào)試或是跟蹤?quán)徑颖淼能壽E時需要注意這一點。

    public class Graph
    {
        private int v;
        private int e;
        private List<int>[] adj; //鄰接表(用List 代替  bag)

        /// <summary>
        /// 創(chuàng)建一個含有V個頂點但不含有邊的圖
        /// </summary>
        /// <param name="V"></param>
        public Graph(int V)
        {
            v = V;
            e = 0;
            adj = new List<int>[V];
            for (var i = 0; i < V; i++)
                adj[i] = new List<int>();
        }

        public Graph(string[] strs)
        {
            foreach (var str in strs)
            {
                var data = str.Split(' ');
                int v = Convert.ToInt32(data[0]);
                int w = Convert.ToInt32(data[1]);
                AddEdge(v,w);
            }
        }

        /// <summary>
        /// 頂點數(shù)
        /// </summary>
        /// <returns></returns>
        public int V()
        {
            return v;
        }

        /// <summary>
        /// 邊數(shù)
        /// </summary>
        /// <returns></returns>
        public int E()
        {
            return e;
        }

        /// <summary>
        /// 向圖中添加一條邊 v-w
        /// </summary>
        /// <param name="v"></param>
        /// <param name="w"></param>
        public void AddEdge(int v, int w)
        {
            adj[v].Add(w);
            adj[w].Add(v);
            e++;
        }

        /// <summary>
        /// 和v相鄰的所有頂點
        /// </summary>
        /// <param name="v"></param>
        /// <returns></returns>
        public IEnumerable<int> Adj(int v)
        {
            return adj[v];
        }

        /// <summary>
        /// 計算 V 的度數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <param name="V"></param>
        /// <returns></returns>
        public static int Degree(Graph G, int V)
        {
            int degree = 0;
            foreach (int w in G.Adj(V))
                degree++;
            return degree;
        }

        /// <summary>
        /// 計算所有頂點的最大度數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static int MaxDegree(Graph G)
        {
            int max = 0;
            for (int v = 0; v < G.V(); v++)
            {
                var d = Degree(G, v);
                if (d > max)
                    max = d;
            }
            return max;
        }

        /// <summary>
        /// 計算所有頂點的平均度數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static double AvgDegree(Graph G)
        {
            return 2.0 * G.E() / G.V();
        }

        /// <summary>
        /// 計算自環(huán)的個數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static int NumberOfSelfLoops(Graph G)
        {
            int count = 0;
            for (int v = 0; v < G.V(); v++)
            {
                foreach (int w in G.Adj(v))
                {
                    if (v == w)
                        count++;
                }
            }

            return count / 2; //每條邊都被計算了兩次
        }

        public override string ToString()
        {
            string s = V() + " vertices, " + E() + " edges\n";
            for (int v = 0; v < V(); v++)
            {
                s += v + ":";
                foreach (int w in Adj(v))
                {
                    s += w + " ";
                }
                s += "\n";
            }
            return s;
        }
    }

在實際應(yīng)用中還有一些操作可能有用，例如：

添加一個頂點；
刪除一個頂點。

實現(xiàn)這些操作的一種方法是，使用符號表 ST 來代替由頂點索引構(gòu)成的數(shù)組，這樣修改之后就不需要約定頂點名必須是整數(shù)了。可能還需要：

刪除一條邊；
檢查圖是否含有 v-w。

要實現(xiàn)這些方法，可能需要使用 SET 代替 Bag 來實現(xiàn)鄰接表。我們稱這種方法為鄰接集?，F(xiàn)在還不需要，因為：

不需要添加，刪除頂點和邊或是檢查一條邊是否存在；
上述操作使用頻率很低或者相關(guān)鏈表很短，可以直接使用窮舉法遍歷；
某些情況下會使性能損失 logV。

3.圖的處理算法的設(shè)計模式

因為我們會討論大量關(guān)于圖處理的算法，所以設(shè)計的首要目標(biāo)是將圖的表示和實現(xiàn)分離開來。為此，我們會為每個任務(wù)創(chuàng)建一個相應(yīng)的類，用例可以創(chuàng)建相應(yīng)的對象來完成任務(wù)。類的構(gòu)造函數(shù)一般會在預(yù)處理中構(gòu)造各種數(shù)據(jù)結(jié)構(gòu)，以有效地響應(yīng)用例的請求。典型的用例程序會構(gòu)造一幅圖，將圖作為參數(shù)傳遞給某個算法類的構(gòu)造函數(shù)，然后調(diào)用各種方法來獲取圖的各種性質(zhì)。

我們用起點 s 區(qū)分作為參數(shù)傳遞給構(gòu)造函數(shù)的頂點與圖中的其他頂點。在這份 API 中，構(gòu)造函數(shù)的任務(wù)就是找到圖中與起點連通的其他頂點。用例可以調(diào)用 marked 方法和 count 方法來了解圖的性質(zhì)。方法名 marked 指的是這種基本方法使用的一種實現(xiàn)方式：在圖中從起點開始沿著路徑到達(dá)其他頂點并標(biāo)記每個路過的頂點。

在 union-find算法已經(jīng)見過 Search API 的實現(xiàn)，它的構(gòu)造函數(shù)會創(chuàng)建一個 UF 對象，對圖中的每條邊進(jìn)行一次 union 操作并調(diào)用 connected(s,v) 來實現(xiàn) marked 方法。實現(xiàn) count 方法需要一個加權(quán)的 UF 實現(xiàn)并擴展它的API，以便使用 count 方法返回 sz[find(v)]。

下面的一種搜索算法是基于深度優(yōu)先搜索（DFS）的，它會沿著圖的邊尋找喝起點連通的所有頂點。

4.深度優(yōu)先搜索

要搜索一幅圖，只需要一個遞歸方法來遍歷所有頂點。在訪問其中一個頂點時：

1.將它標(biāo)記為已訪問；
2.遞歸地訪問它所有沒有被標(biāo)記過地鄰居頂點。

這種方法稱為深度優(yōu)先搜索（DFS）。

namespace Graphs
{
    /// <summary>
    /// 使用一個 bool 數(shù)組來記錄和起點連通地所有頂點。遞歸方法會標(biāo)記給定地頂點并調(diào)用自己來訪問該頂點地相鄰頂點列表中
    /// 所有沒有被標(biāo)記過地頂點。 如果圖是連通的，每個鄰接鏈表中的元素都會被標(biāo)記。
    /// </summary>
    public class DepthFirstSearch
    {
        private bool[] marked;
        private int count;

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

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

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

深度優(yōu)先搜索標(biāo)記與起點連通的所有頂點所需的時間和頂點的度數(shù)之和成正比。

這種簡單的遞歸模式只是一個開始 -- 深度優(yōu)先搜索能夠有效處理許多和圖有關(guān)的任務(wù)。

1.連通性。給定一幅圖，兩個給定的頂點是否連通？（兩個給定的頂點之間是否存在一條路徑?路徑檢測）圖中有多少個連通子圖？
2.單點路徑。給定一幅圖和一個起點 s ，從 s 到給定目的頂點 v 是否存在一條路徑？如果有，找出這條路徑。

5.尋找路徑

單點路徑的API：

構(gòu)造函數(shù)接受一個起點 s 作為參數(shù)，計算 s 到與 s 連通的每個頂點之間的路徑。在為起點 s 創(chuàng)建 Paths 對象之后，用例可以調(diào)用 PathTo 方法來遍歷從 s 到任意和 s 連通的頂點的路徑上的所有頂點。

實現(xiàn)

下面的算法基于深度優(yōu)先搜索，它添加了一個 edgeTo[ ] 整型數(shù)組，這個數(shù)組可以找到從每個與 s 連通的頂點回到 s 的路徑。它會記住每個頂點到起點的路徑，而不是記錄當(dāng)前頂點到起點的路徑。為了做到這一點，在由邊 v-w 第一次任意訪問 w 時，將edgeTo[w] = v 來記住這條路徑。換句話說， v-w 是從s 到 w 的路徑上最后一條已知的邊。這樣，搜索的結(jié)果是一棵以起點為根結(jié)點的樹，edgeTo[ ] 是一棵由父鏈接表示的樹。 PathTo 方法用變量 x 遍歷整棵樹，將遇到的所有頂點壓入棧中。

    public class DepthFirstPaths
    {
        private bool[] marked;
        private int[] edgeTo; //從起點到一個頂點的已知路徑上的最后一個頂點
        private int s;//起點

        public DepthFirstPaths(Graph G, int s)
        {
            marked = new bool[G.V()];
            edgeTo = new int[G.V()];
            this.s = s;
            Dfs(G,s);
        }

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

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

        public IEnumerable<int> PathTo(int v)
        {
            if (!HasPathTo(v))
                return null;
            Stack<int> path = new Stack<int>();
            for (int x = v; x != s; x = edgeTo[x])
                path.Push(x);
            path.Push(s);
            return path;
        }
    }

使用深度優(yōu)先搜索得到從給定起點到任意標(biāo)記頂點的路徑所需的時間與路徑長度成正比。

6.廣度優(yōu)先搜索

深度優(yōu)先搜索得到的路徑不僅取決于圖的結(jié)構(gòu)，還取決于圖的表示和遞歸調(diào)用的性質(zhì)。

單點最短路徑：給定一幅圖和一個起點 s ，從 s 到給定目的頂點 v 是否存在一條路徑？如果有，找出其中最短的那條（所含邊最少）。

解決這個問題的經(jīng)典方法叫做廣度優(yōu)先搜索（BFS）。深度優(yōu)先搜索在這個問題上沒有什么作用，因為它遍歷整個圖的順序和找出最短路徑的目標(biāo)沒有任何關(guān)系。相比之下，廣度又出現(xiàn)搜索正式為了這個目標(biāo)才出現(xiàn)的。

要找到從 s 到 v 的最短路徑，從 s 開始，在所有由一條邊就可以到達(dá)的頂點中尋找 v ，如果找不到就繼續(xù)在與 s 距離兩條邊的所有頂點中查找 v ,如此一直進(jìn)行。

在程序中，在搜索一幅圖時遇到有很多邊需要遍歷的情況時，我們會選擇其中一條并將其他邊留到以后再繼續(xù)搜索。在深度優(yōu)先搜索中，我們用了一個可以下壓棧。使用LIFO （后進(jìn)先出）的規(guī)則來描述下壓棧和走迷宮時先探索相鄰的

通道類似。從有待搜索的通道中選擇最晚遇到過的那條。在廣度優(yōu)先搜索中，我們希望按照與起點距離的順序來遍歷所有頂點，使用（FIFO，先進(jìn)先出）隊列來代替棧即可。我們將從有待搜索的通道中選擇最早遇到的那條。

實現(xiàn)

下面的算法使用了一個隊列來保存所有已經(jīng)被標(biāo)記過但其鄰接表還未被檢查過的頂點。先將頂點加入隊列，然后重復(fù)下面步驟知道隊列為空：

1.取隊列的下一個頂點 v 并標(biāo)記它；
2.將與 v 相鄰的所有未被標(biāo)記過的頂點加入隊列。

下面的 Bfs 方法不是遞歸。它顯示地使用了一個隊列。和深度優(yōu)先搜索一樣，它的結(jié)果也是一個數(shù)組 edgeTo[ ] ，也是一棵用父鏈接表示的根結(jié)點為 s 的樹。它表示了 s 到每個與 s 連通的頂點的最短路徑。

namespace Graphs
{
    /// <summary>
    /// 廣度優(yōu)先搜索
    /// </summary>
    public class BreadthFirstPaths
    {
        private bool[] marked;//到達(dá)該頂點的最短路徑已知嗎？
        private int[] edgeTo;//到達(dá)該頂點的已知路徑上的最后一個頂點
        private int s;//起點

        public BreadthFirstPaths(Graph G,int s)
        {
            marked = new bool[G.V()];
            edgeTo = new int[G.V()];
            this.s = s;
            Bfs(G,s);
        }

        private void Bfs(Graph G, int s)
        {
            Queue<int> queue = new Queue<int>();
            marked[s] = true;//標(biāo)記起點
            queue.Enqueue(s);//將它加入隊列
            while (queue.Count > 0)
            {
                int v = queue.Dequeue();//從隊列中刪去下一個頂點
                foreach (var w in G.Adj(v))
                {
                    if (!marked[w])//對于每個未標(biāo)記的相鄰頂點
                    {
                        edgeTo[w] = v;//保存最短路徑的最后一條邊
                        marked[w] = true;//標(biāo)記它，因為最短路徑已知
                        queue.Enqueue(w);//并將它添加到隊列中
                    }
                }
            }
        }

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

軌跡：

對于從 s 可達(dá)的任意頂點 v ,廣度優(yōu)先搜索都能找到一條從 s 到 v 的最短路徑，沒有其他從 s 到 v 的路徑所含的邊比這條路徑更少。

廣度優(yōu)先搜索所需的時間在最壞情況下和 V+E 成正比。

我們也可以使用廣度優(yōu)先搜索來實現(xiàn)已經(jīng)用深度優(yōu)先搜索實現(xiàn)的 Search API，因為它檢查所有與起點連通的頂點和邊的方法只取決于查找能力。

廣度優(yōu)先搜索和深度優(yōu)先搜索在搜索中都會先將起點存入數(shù)據(jù)結(jié)構(gòu)，然后重復(fù)以下步驟直到數(shù)據(jù)結(jié)構(gòu)清空：

1.取其中的下一個頂點并標(biāo)記它；
2.將 v 的所有相鄰而又未被標(biāo)記的頂點加入數(shù)據(jù)結(jié)構(gòu)。

這兩個算法的不同之處在于從數(shù)據(jù)結(jié)構(gòu)中獲取下一個頂點的規(guī)則（對于廣度優(yōu)先搜索來說是最早加入的頂點，對于深度優(yōu)先搜索來說是最晚加入的頂點）。這種差異得到了處理圖的兩種完全不同的視角，盡管無論使用哪種規(guī)則，所有與起點連通的頂點和邊都會被檢查到。

深度優(yōu)先搜索不斷深入圖中并在棧中保存了所有分叉的頂點；廣度優(yōu)先搜索則像扇面一般掃描圖，用一個隊列保存訪問過的最前端的頂點。深度優(yōu)先搜索探索一幅圖的方式是尋找離起點更遠(yuǎn)的頂點，只在碰到死胡同時才訪問進(jìn)出的頂點；廣度優(yōu)先搜索則首先覆蓋起點附近的頂點，只在臨近的所有頂點都被訪問了之后才向前進(jìn)。根據(jù)應(yīng)用的不同，所需要的性質(zhì)也不同。

7.連通分量

深度優(yōu)先搜索的下一個直接應(yīng)用就是找出一幅圖的所有連通分量。在 union-find中 “與......連通” 是一種等價關(guān)系，它能夠?qū)⑺许旤c切分成等價類（連通分量）。

實現(xiàn)

CC 的實現(xiàn)使用了marked 數(shù)組來尋找一個頂點作為每個連通分量中深度優(yōu)先搜索的起點。遞歸的深度優(yōu)先搜索第一次調(diào)用的參數(shù)是頂點 0 -- 它會標(biāo)記所有與 0 連通的頂點。然后構(gòu)造函數(shù)中的 for 循環(huán)會查找每個沒有被標(biāo)記的頂點并遞歸調(diào)用 Dfs 來標(biāo)記和它相鄰的所有頂點。另外，還使用了一個以頂點作為索引的數(shù)組 id[ ] ，值為連通分量的標(biāo)識符，將同一連通分量中的頂點和連通分量的標(biāo)識符關(guān)聯(lián)起來。這個數(shù)組使得 Connected 方法的實現(xiàn)變得非常簡單。

namespace Graphs
{
    public class CC
    {
        private bool[] marked;
        private int[] id;
        private int count;

        public CC(Graph G)
        {
            marked = new bool[G.V()];
            id = new int[G.V()];
            for (var s = 0; s < G.V(); s++)
            {
                if (!marked[s])
                {
                    Dfs(G,s);
                    count++;
                }
            }
        }

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

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

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

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

深度優(yōu)先搜索的預(yù)處理使用的時間和空間與 V + E 成正比且可以在常數(shù)時間內(nèi)處理關(guān)于圖的連通性查詢。由代碼可知每個鄰接表的元素都只會被檢查一次，共有 2E 個元素（每條邊兩個）。

union-find 算法

CC 中基于深度優(yōu)先搜索來解決圖連通性問題的方法與 union-find算法中的算法相比，理論上，深度優(yōu)先搜索更快，因為它能保證所需的時間是常數(shù)而 union-find算法不行；但在實際應(yīng)用中，這點差異微不足道。union-find算法其實更快，因為它不需要完整地構(gòu)造表示一幅圖。更重要的是，union-find算法是一種動態(tài)算法（我們在任何時候都能用接近常數(shù)的時間檢查兩個頂點是否連通，甚至是添加一條邊的時候），但深度優(yōu)先搜索則必須對圖進(jìn)行預(yù)處理。

因此，我們在只需要判斷連通性或是需要完成大量連通性查詢和插入操作混合等類似的任務(wù)時，更傾向使用union-find算法，而深度優(yōu)先搜索則適合實現(xiàn)圖的抽象數(shù)據(jù)類型，因為它能更有效地利用已有的數(shù)據(jù)結(jié)構(gòu)。

使用深度優(yōu)先搜索還可以解決檢測環(huán) 和雙色問題：

檢測環(huán)，給定的圖是無環(huán)圖嗎？

namespace Graphs
{
    public class Cycle
    {
        private bool[] marked;
        private bool hasCycle;

        public Cycle(Graph G)
        {
            marked = new bool[G.V()];
            for (var s = 0; s < G.V(); s++)
            {
                if (!marked[s])
                    Dfs(G,s,s);
            }
        }

        private void Dfs(Graph g, int v, int u)
        {
            marked[v] = true;
            foreach (var w in g.Adj(v))
            {
                if (!marked[w])
                    Dfs(g, w, v);
                else if (w != u)
                    hasCycle = true;
            }
        }

        public bool HasCycle()
        {
            return hasCycle;
        }
    }
}

是二分圖嗎？（雙色問題）

namespace Graphs
{
    public class TwoColor
    {
        private bool[] marked;
        private bool[] color;
        private bool isTwoColorable = true;

        public TwoColor(Graph G)
        {
            marked = new bool[G.V()];
            color = new bool[G.V()];
            for(var s = 0;s<G.V();s++)
            {
                if (!marked[s])
                    Dfs(G,s);
            }
        }

        private void Dfs(Graph g, int v)
        {
            marked[v] = true;
            foreach (var w in g.Adj(v))
            {
                if (!marked[w])
                {
                    color[w] = !color[v];
                    Dfs(g, w);
                }
                else if (color[w] == color[v])
                    isTwoColorable = false;
            }
        }

        public bool IsBipartite()
        {
            return isTwoColorable;
        }
    }
}

8.符號圖

在典型應(yīng)用中，圖都是通過文件或者網(wǎng)頁定義的，使用的是字符串而非整數(shù)來表示和指代頂點。為了適應(yīng)這樣的應(yīng)用，我們使用符號圖。符號圖的API：

這份API 定義一個構(gòu)造函數(shù)來讀取并構(gòu)造圖，用 name() 和 index() 方法將輸入流中的頂點名和圖算法使用的頂點索引對應(yīng)起來。

實現(xiàn)

需要用到3種數(shù)據(jù)結(jié)構(gòu)：

1.一個符號表 st ，鍵的類型為 string（頂點名），值的類型 int （索引）；
2.一個數(shù)組 keys[ ]，用作反向索引，保存每個頂點索引對應(yīng)的頂點名；
3.一個 Graph 對象 G，它使用索引來引用圖中頂點。

SymbolGraph 會遍歷兩遍數(shù)據(jù)來構(gòu)造以上數(shù)據(jù)結(jié)構(gòu)，這主要是因為構(gòu)造 Graph 對象需要頂點總數(shù) V。在典型的實際應(yīng)用中，在定義圖的文件中指明 V 和 E 可能會有些不便，而有了 SymbolGraph，就不需要擔(dān)心維護(hù)邊或頂點的總數(shù)。

namespace Graphs
{
    public class SymbolGraph
    {
        private Dictionary<string, int> st;//符號名 -> 索引
        private string[] keys;//索引 -> 符號名
        private Graph G;

        public SymbolGraph(string fileName, string sp)
        {
            var strs = File.ReadAllLines(fileName);
            st = new Dictionary<string, int>();

            //第一遍
            foreach (var str in strs)
            {
                var _strs = str.Split(sp);
                foreach (var _str in _strs)
                {
                    st.Add(_str,st.Count);
                }
            }

            keys = new string[st.Count];
            foreach (var name in st.Keys)
            {
                keys[st[name]] = name;
            }

            //第二遍 將每一行的第一個頂點和該行的其他頂點相連
            foreach (var str in strs)
            {
                var _strs = str.Split(sp);
                int v = st[_strs[0]];
                for (var i = 1; i < _strs.Length; i++)
                {
                    G.AddEdge(v,st[_strs[i]]);
                }
            }
        }

        public bool Contains(string s)
        {
            return st.ContainsKey(s);
        }

        public int Index(string s)
        {
            return st[s];
        }

        public string Name(int v)
        {
            return keys[v];
        }

        public Graph Gra()
        {
            return G;
        }
    }
}