C#并查集(union-find)算法詳解

更新時(shí)間：2022年04月15日 11:56:54 投稿：yangbin

本文詳細(xì)講解了C#并查集(union-find)算法，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

算法的主題思想:

1.優(yōu)秀的算法因?yàn)槟軌蚪鉀Q實(shí)際問題而變得更為重要；

2.高效算法的代碼也可以很簡單；

3.理解某個(gè)實(shí)現(xiàn)的性能特點(diǎn)是一個(gè)挑戰(zhàn)；

4.在解決同一個(gè)問題的多種算法之間進(jìn)行選擇時(shí)，科學(xué)方法是一種重要的工具；

5.迭代式改進(jìn)能夠讓算法的效率越來越高效；

1. 動(dòng)態(tài)連通性

動(dòng)態(tài)連接：輸入是一對(duì)整數(shù)對(duì)的序列，其中每個(gè)整數(shù)代表某種類型的對(duì)象（或觸點(diǎn)），我們將整數(shù)對(duì)p q 解釋為意味著p連接到q。我們假設(shè)“連接到”是等價(jià)關(guān)系：

對(duì)稱性：如果p連接到q，則q 連接到p。
傳遞性：如果p連接到q且q 連接到r，則p連接到r。
自反性：p與p連接。

等價(jià)關(guān)系將對(duì)象劃分為多個(gè)等價(jià)類或連接的組件。等價(jià)類稱為連通分量或分量。
我們的目標(biāo)是編寫一個(gè)程序，以從序列中過濾掉多余的對(duì)：當(dāng)程序從輸入中讀取整數(shù)對(duì) p q時(shí)，只有在該對(duì)點(diǎn)不等價(jià)的情況下，才應(yīng)將對(duì)寫入到輸出中，并且將p連接到q。如果等價(jià)，則程序應(yīng)忽略整數(shù)對(duì)pq 并繼續(xù)讀取下對(duì)。

動(dòng)態(tài)連通性問題的應(yīng)用：

1.網(wǎng)絡(luò)
2.變量名等價(jià)性
3.數(shù)學(xué)集合

在更高的抽象層次上，可以將輸入的所有整數(shù)看做屬于不同的數(shù)學(xué)集合。

2. 定義問題

設(shè)計(jì)算法的第一個(gè)任務(wù)就是精確地定義問題。

算法解決的問題越大，它完成任務(wù)所需的時(shí)間和空間可能越多。我們不可能預(yù)先知道這其間的量化關(guān)系，通常只會(huì)在發(fā)現(xiàn)解決問題很困難，或是代價(jià)巨大，或是發(fā)現(xiàn)算法所提供的信息比原問題所需要的更加有用時(shí)修改問題。例如，連通性問題只要求我們的程序能夠判斷出給定的整數(shù)對(duì)是否相連，但并沒有要求給出兩者之間的通路上的所有連接。這樣的要求更難，并會(huì)得出另一組不同的算法。

為了定義和說明問題，先設(shè)計(jì)一份API 來封裝基本操作: 初始化，連接兩個(gè)觸點(diǎn)，查找某個(gè)觸點(diǎn)的分量，判斷兩個(gè)觸點(diǎn)是否屬于同一分量，分量的數(shù)量：

    /// <summary>
    /// 動(dòng)態(tài)連通API
    /// </summary>
    public interface IUnionFind
    {
        /// <summary>
        /// 連接
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        void Union(int p, int q);

        /// <summary>
        /// 查找觸點(diǎn) p 的分量標(biāo)識(shí)符
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        int Find(int p);

        /// <summary>
        /// 判斷兩個(gè)觸點(diǎn)是否處于同一分量
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        bool Connected(int p, int q);

        /// <summary>
        /// 連通分量的數(shù)量
        /// </summary>
        /// <returns></returns>
        int Count();
    }

為解決動(dòng)態(tài)連通性問題設(shè)計(jì)算法的任務(wù)轉(zhuǎn)化為實(shí)現(xiàn)這份API：

1. 定義一種數(shù)據(jù)結(jié)構(gòu)表示已知的連接；
2. 基于此數(shù)據(jù)結(jié)構(gòu)高效的實(shí)現(xiàn)API的方法；

數(shù)據(jù)結(jié)構(gòu)的性質(zhì)會(huì)直接影響算法的效率。這里，以觸點(diǎn)為索引，觸點(diǎn)和連接分量都是用 int 值表示，將會(huì)使用分量中某個(gè)觸點(diǎn)的值作為分量的標(biāo)識(shí)符。所以，一開始，每個(gè)觸點(diǎn)都是只含有自己的分量，分量標(biāo)識(shí)符為觸點(diǎn)的值。由此，可以初步實(shí)現(xiàn)一部分方法：

    public class FirstUnionFind:IUnionFind
    {
        private int[] id;//* 分量id 以觸點(diǎn)作為索引
        private int count;//分量數(shù)量

        public FirstUnionFind(int n)
        {
            count = n;
            id = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個(gè) i 作為觸點(diǎn)，第二個(gè) i 作為觸點(diǎn)的值
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            
        }

        public void Union(int p, int q)
        {
            
        }
    }

Union-find 的成本模型是數(shù)組的訪問次數(shù)(無論讀寫)。

3. quick-find算法實(shí)現(xiàn)

quick-find 算法是保證當(dāng)且僅當(dāng) id[p] 等于 id[q] 時(shí)，p 和 q 是連通的。也就是說，在同一個(gè)連通分量中的所有觸點(diǎn)在 id[ ] 中的值全部相等。

所以Find 方法只需返回id[q]，Union 方法需要先判斷Find(p) 是否等于Find(q) ,若相等直接返回；若不相等，需要將 q 所在的連通分量中所有觸點(diǎn)的 id [ ] 值全部更新為 id[p]。

    public class QuickFindUF: IUnionFind
    {
        private int[] id;//* 分量id 以觸點(diǎn)作為索引
        private int count;//分量數(shù)量

        public QuickFindUF(int n)
        {
            count = n;
            id = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個(gè) i 作為觸點(diǎn)，第二個(gè) i 作為觸點(diǎn)的值
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            return id[p];
        }

        public void Union(int p, int q)
        {
            var pID = Find(p);
            var qID = Find(q);

            if (pID == qID)
                return;

            for (var i = 0; i < id.Length; i++)
            {
                if (id[i] == qID)
                    id[i] = pID;
            }
            count--; //連通分量減少
        }

        public void Show()
        {
            for(var i = 0;i<id.Length;i++)
                Console.WriteLine("索引："+i+",值："+ id[i] );
            Console.WriteLine("連通分量數(shù)量："+count);
        }
    }

算法分析

Find() 方法只需訪問一次數(shù)組，所以速度很快。但是對(duì)于處理大型問題，每對(duì)輸入 Union() 方法都需要掃描整個(gè)數(shù)組。

每一次歸并兩個(gè)分量的 Union() 方法訪問數(shù)組的次數(shù)在 N+3 到 2N+1 之間。由代碼可知，兩次 Find 操作訪問兩次數(shù)組，掃描數(shù)組會(huì)訪問N次，改變其中一個(gè)分量中所有觸點(diǎn)的值需要訪問 1 到 N - 1 次（最好情況是該分量中只有一個(gè)觸點(diǎn)，最壞情況是該分量中有 N - 1個(gè)觸點(diǎn)），2+N+N-1。

如果使用quick-find 算法來解決動(dòng)態(tài)連通性問題并且最后只得到一個(gè)連通分量，至少需要調(diào)用 N-1 次Union() 方法，那么至少需要 (N+3)(N-1) ~ N^2 次訪問數(shù)組，是平方級(jí)別的。

4. quick-union算法實(shí)現(xiàn)

quick-union 算法重點(diǎn)提高 union 方法的速度，它也是基于相同的數(shù)據(jù)結(jié)構(gòu) -- 已觸點(diǎn)為索引的 id[ ] 數(shù)組，但是 id[ ] 的值是同一分量中另一觸點(diǎn)的索引(名稱)，也可能是自己（根觸點(diǎn)）——這種聯(lián)系成為鏈接。

在實(shí)現(xiàn) Find() 方法時(shí)，從給定觸點(diǎn)，鏈接到另一個(gè)觸點(diǎn)，知道到達(dá)根觸點(diǎn)，即鏈接指向自己。同時(shí)修改 Union() 方法，分別找到 p q 的根觸點(diǎn)，將其中一個(gè)根觸點(diǎn)鏈接到根觸點(diǎn)。

    public class QuickUnionUF : IUnionFind
    {
        private int[] id;
        private int count;

        public QuickUnionUF(int n)
        {
            count = n;
            id = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個(gè) i 作為觸點(diǎn)，第二個(gè) i 作為觸點(diǎn)的值
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            while (p != id[p])
                p = id[p];
            return p;
        }

        public void Union(int p, int q)
        {
            var pRoot = Find(p);
            var qRoot = Find(q);

            if (pRoot == qRoot)
                return;

            id[pRoot] =qRoot;
            count--; //連通分量減少  
        }
        public void Show() 
        { 
            for (var i = 0; i < id.Length; i++) 
            Console.WriteLine("索引：" + i + ",值：" + id[i]); 
            Console.WriteLine("連通分量數(shù)量：" + count); 
        }
    }

森林表示

id[ ] 數(shù)組用父鏈接的形式表示一片森林，用節(jié)點(diǎn)表示觸點(diǎn)。無論從任何觸點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)隨著鏈接查找，最后都將到達(dá)含有該節(jié)點(diǎn)的根節(jié)點(diǎn)。初始化數(shù)組之后，每個(gè)節(jié)點(diǎn)的鏈接都指向自己。

算法分析

定義：一棵樹的大小是它的節(jié)點(diǎn)的數(shù)量。樹中一個(gè)節(jié)點(diǎn)的深度是它到根節(jié)點(diǎn)的路徑上鏈接數(shù)。樹的高度是它的所有節(jié)點(diǎn)中的最大深度。

quick-union 算法比 quick-find 算法更快，因?yàn)樗鼘?duì)每對(duì)輸入不需要遍歷整個(gè)數(shù)組。

分析quick-union 算法的成本比 quick-find 算法的成本要困難，因?yàn)閝uick-union 算法依賴于輸入的特點(diǎn)。在最好的情況下，find() 方法只需訪問一次數(shù)組就可以得到一個(gè)觸點(diǎn)的分量表示；在最壞情況下，需要 2i+1 次數(shù)組訪問(i 時(shí)觸點(diǎn)的深度)。由此得出，該算法解決動(dòng)態(tài)連通性問題，在最佳情況下的運(yùn)行時(shí)間是線性級(jí)別，最壞情況下的輸入是平方級(jí)別。解決了quick-find 算法中 union() 方法總是線性級(jí)別，解決動(dòng)態(tài)連通性問題總是平方級(jí)別。

quick-union 算法中 find() 方法訪問數(shù)組的次數(shù)為 1(到達(dá)根節(jié)點(diǎn)只需訪問一次) 加上給定觸點(diǎn)所對(duì)應(yīng)節(jié)點(diǎn)的深度的兩倍（while 循環(huán)，一次讀，一次寫）。union() 訪問兩次 find() ，如果兩個(gè)觸點(diǎn)不在同一分量還需加一次寫數(shù)組。

假設(shè)輸入的整數(shù)對(duì)是有序的 0-1， 0-2，0-3 等，N-1 對(duì)之后N個(gè)觸點(diǎn)將全部處于相同的集合之中，且得到的樹的高度為 N-1。由上可知，對(duì)于整數(shù)對(duì) 0-i , find() 訪問數(shù)組的次數(shù)為 2i + 1,因此，處理 N 對(duì)整數(shù)對(duì)所需的所有訪問數(shù)組的總次數(shù)為 3+5+7+ ......+(2N+1) ~ n^2

5.加權(quán) quick-union 算法實(shí)現(xiàn)

簡單改動(dòng)就可以避免 quick-union算法出現(xiàn)最壞情況。quick-union算法 union 方法是隨意將一棵樹連接到另一棵樹，改為總是將小樹連接到大樹，這需要記錄每一棵樹的大小，稱為加權(quán)quick-union算法。

代碼：

    public class WeightedQuickUnionUF: IUnionFind
    {
        int[] sz;//以觸點(diǎn)為索引的 各個(gè)根節(jié)點(diǎn)對(duì)應(yīng)的分量樹大小
        private int[] id;
        private int count;

        public WeightedQuickUnionUF(int n)
        {
            count = n;
            id = new int[n];
            sz = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個(gè) i 作為觸點(diǎn)，第二個(gè) i 作為觸點(diǎn)的值
                sz[i] = 1;
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            while (p != id[p])
                p = id[p];
            return p;
        }

        public void Union(int p, int q)
        {
            var pRoot = Find(p);
            var qRoot = Find(q);

            if (pRoot == qRoot)
                return;

            if (sz[pRoot] < sz[qRoot])
            {
                id[pRoot] = qRoot;
            }
            else
            {
                id[qRoot] = pRoot;
            }
                
            count--; //連通分量減少
        }

        public void Show()
        {
            for (var i = 0; i < id.Length; i++)
                Console.WriteLine("索引：" + i + ",值：" + id[i]);
            Console.WriteLine("連通分量數(shù)量：" + count);
        }
    }

算法分析

加權(quán) quicj-union 算法最壞的情況：

這種情況，將要被歸并的樹的大小總是相等的（且總是 2 的冥），都含有 2^n 個(gè)節(jié)點(diǎn)，高度都正好是 n 。當(dāng)歸并兩個(gè)含有 2^n 個(gè)節(jié)點(diǎn)的樹時(shí)，得到的樹含有 2 ^ n+1 個(gè)節(jié)點(diǎn)，高度增加到 n+1 。

節(jié)點(diǎn)大?。?1　　2　　4　　8　　2^k = N

高度： 0　　1　　2　　3　　k

k = logN

所以加權(quán) quick-union 算法可以保證對(duì)數(shù)級(jí)別的性能。

對(duì)于 N 個(gè)觸點(diǎn)，加權(quán) quick-union 算法構(gòu)造的森林中的任意節(jié)點(diǎn)的深度最多為logN。

對(duì)于加權(quán) quick-union 算法和N 個(gè)觸點(diǎn)，在最壞情況下 find，connected 和 union 方法的成本的增長量級(jí)為 logN。

對(duì)于動(dòng)態(tài)連通性問題，加權(quán) quick-union 算法是三種算法中唯一可以用于解決大型問題的算法。加權(quán) quick-union 算法處理 N 個(gè)觸點(diǎn)和 M 條連接時(shí)最多訪問數(shù)組 c M logN 次，其中 c 為常數(shù)。

三個(gè)算法處理一百萬個(gè)觸點(diǎn)運(yùn)行時(shí)間對(duì)比：