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

2022-04-15 16:00:31

演演算法的主題思想:

1.優秀的演演算法因為能夠解決實際問題而變得更為重要；

2.高效演演算法的程式碼也可以很簡單；

3.理解某個實現的效能特點是一個挑戰；

4.在解決同一個問題的多種演演算法之間進行選擇時，科學方法是一種重要的工具；

5.迭代式改進能夠讓演演算法的效率越來越高效；

1. 動態連通性

動態連線：輸入是一對整數對的序列，其中每個整數代表某種型別的物件（或觸點），我們將整數對p q 解釋為意味著p連線到q。我們假設“連線到”是等價關係：

對稱性：如果p連線到q，則q 連線到p。
傳遞性：如果p連線到q且q 連線到r，則p連線到r。
自反性：p與p連線。

等價關係將物件劃分為多個等價類或連線的元件。等價類稱為連通分量或分量。
我們的目標是編寫一個程式，以從序列中過濾掉多餘的對：當程式從輸入中讀取整數對 p q時，只有在該對點不等價的情況下，才應將對寫入到輸出中，並且將p連線到q。如果等價，則程式應忽略整數對pq 並繼續讀取下對。

動態連通性問題的應用：

1.網路
2.變數名等價性
3.數學集合

在更高的抽象層次上，可以將輸入的所有整數看做屬於不同的數學集合。

2. 定義問題

設計演演算法的第一個任務就是精確地定義問題。

演演算法解決的問題越大，它完成任務所需的時間和空間可能越多。我們不可能預先知道這其間的量化關係，通常只會在發現解決問題很困難，或是代價巨大，或是發現演演算法所提供的資訊比原問題所需要的更加有用時修改問題。例如，連通性問題只要求我們的程式能夠判斷出給定的整數對是否相連，但並沒有要求給出兩者之間的通路上的所有連線。這樣的要求更難，並會得出另一組不同的演演算法。

為了定義和說明問題，先設計一份API 來封裝基本操作: 初始化，連線兩個觸點，查詢某個觸點的分量，判斷兩個觸點是否屬於同一分量，分量的數量：

    /// <summary>
    /// 動態連通API
    /// </summary>
    public interface IUnionFind
    {
        /// <summary>
        /// 連線
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        void Union(int p, int q);

        /// <summary>
        /// 查詢觸點 p 的分量識別符號
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        int Find(int p);

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

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

為解決動態連通性問題設計演演算法的任務轉化為實現這份API：

1. 定義一種資料結構表示已知的連線；
2. 基於此資料結構高效的實現API的方法；

資料結構的性質會直接影響演演算法的效率。這裡，以觸點為索引，觸點和連線分量都是用 int 值表示，將會使用分量中某個觸點的值作為分量的識別符號。所以，一開始，每個觸點都是隻含有自己的分量，分量識別符號為觸點的值。由此，可以初步實現一部分方法：

    public class FirstUnionFind:IUnionFind
    {
        private int[] id;//* 分量id 以觸點作為索引
        private int count;//分量數量

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

        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 的成本模型是陣列的存取次數(無論讀寫)。

3. quick-find演演算法實現

quick-find 演演算法是保證當且僅當 id[p] 等於 id[q] 時，p 和 q 是連通的。也就是說，在同一個連通分量中的所有觸點在 id[ ] 中的值全部相等。

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

    public class QuickFindUF: IUnionFind
    {
        private int[] id;//* 分量id 以觸點作為索引
        private int count;//分量數量

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

        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("連通分量數量："+count);
        }
    }

演演算法分析

Find() 方法只需存取一次陣列，所以速度很快。但是對於處理大型問題，每對輸入 Union() 方法都需要掃描整個陣列。

每一次歸併兩個分量的 Union() 方法存取陣列的次數在 N+3 到 2N+1 之間。由程式碼可知，兩次 Find 操作存取兩次陣列，掃描陣列會存取N次，改變其中一個分量中所有觸點的值需要存取 1 到 N - 1 次（最好情況是該分量中只有一個觸點，最壞情況是該分量中有 N - 1個觸點），2+N+N-1。

如果使用quick-find 演演算法來解決動態連通性問題並且最後只得到一個連通分量，至少需要呼叫 N-1 次Union() 方法，那麼至少需要 (N+3)(N-1) ~ N^2 次存取陣列，是平方級別的。

4. quick-union演演算法實現

quick-union 演演算法重點提高 union 方法的速度，它也是基於相同的資料結構 -- 已觸點為索引的 id[ ] 陣列，但是 id[ ] 的值是同一分量中另一觸點的索引(名稱)，也可能是自己（根觸點）——這種聯絡成為連結。

在實現 Find() 方法時，從給定觸點，連結到另一個觸點，知道到達根觸點，即連結指向自己。同時修改 Union() 方法，分別找到 p q 的根觸點，將其中一個根觸點連結到根觸點。

    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; // 第一個 i 作為觸點，第二個 i 作為觸點的值
            }
        }

        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("連通分量數量：" + count); 
        }
    }

森林表示

id[ ] 陣列用父連結的形式表示一片森林，用節點表示觸點。無論從任何觸點所對應的節點隨著連結查詢，最後都將到達含有該節點的根節點。初始化陣列之後，每個節點的連結都指向自己。

演演算法分析

定義：一棵樹的大小是它的節點的數量。樹中一個節點的深度是它到根節點的路徑上連結數。樹的高度是它的所有節點中的最大深度。

quick-union 演演算法比 quick-find 演演算法更快，因為它對每對輸入不需要遍歷整個陣列。

分析quick-union 演演算法的成本比 quick-find 演演算法的成本要困難，因為quick-union 演演算法依賴於輸入的特點。在最好的情況下，find() 方法只需存取一次陣列就可以得到一個觸點的分量表示；在最壞情況下，需要 2i+1 次陣列存取(i 時觸點的深度)。由此得出，該演演算法解決動態連通性問題，在最佳情況下的執行時間是線性級別，最壞情況下的輸入是平方級別。解決了quick-find 演演算法中 union() 方法總是線性級別，解決動態連通性問題總是平方級別。

quick-union 演演算法中 find() 方法存取陣列的次數為 1(到達根節點只需存取一次) 加上給定觸點所對應節點的深度的兩倍（while 迴圈，一次讀，一次寫）。union() 存取兩次 find() ，如果兩個觸點不在同一分量還需加一次寫陣列。

假設輸入的整數對是有序的 0-1， 0-2，0-3 等，N-1 對之後N個觸點將全部處於相同的集合之中，且得到的樹的高度為 N-1。由上可知，對於整數對 0-i , find() 存取陣列的次數為 2i + 1,因此，處理 N 對整數對所需的所有存取陣列的總次數為 3+5+7+ ......+(2N+1) ~ n^2

5.加權 quick-union 演演算法實現

簡單改動就可以避免 quick-union演演算法出現最壞情況。quick-union演演算法 union 方法是隨意將一棵樹連線到另一棵樹，改為總是將小樹連線到大樹，這需要記錄每一棵樹的大小，稱為加權quick-union演演算法。

程式碼：

    public class WeightedQuickUnionUF: IUnionFind
    {
        int[] sz;//以觸點為索引的 各個根節點對應的分量樹大小
        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; // 第一個 i 作為觸點，第二個 i 作為觸點的值
                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("連通分量數量：" + count);
        }
    }