演算法（第四版）C#題解——1.5

寫在前面整個項目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp這一節內容可能會用到的庫文件有 Measurement 和 TestCase，同樣在 Github 上可以找到。善用 Ctrl + F... ...

寫在前面

整個項目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp

這一節內容可能會用到的庫文件有 Measurement 和 TestCase，同樣在 Github 上可以找到。

善用 Ctrl + F 查找題目。

習題&題解

1.5.1

題目

使用 quick-find 演算法處理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。
對於輸入的每一對整數，給出 id[] 數組的內容和訪問數組的次數。

解答

quick-find 的官方實現：QuickFindUF.java。

只要實現相應並查集，然後輸入內容即可。

增加一個記錄訪問數組次數的類成員變數，在每次訪問數組的語句執行後自增即可。

樣例輸出：

0 1 2 3 4 5 6 7 8 0 數組訪問：13
0 1 2 4 4 5 6 7 8 0 數組訪問：13
0 1 2 4 4 8 6 7 8 0 數組訪問：13
0 1 2 4 4 8 6 2 8 0 數組訪問：13
0 1 1 4 4 8 6 1 8 0 數組訪問：14
0 1 1 4 4 1 6 1 1 0 數組訪問：14
4 1 1 4 4 1 6 1 1 4 數組訪問：14
1 1 1 1 1 1 6 1 1 1 數組訪問：16

代碼

QuickFindUF.cs，這個類繼承了 UF.cs，重新實現了 Union() 和 Find() 等方法。

關於 UF.cs 可以參見原書中文版 P138 或英文版 P221 的演算法 1.5。

namespace UnionFind
{
    /// <summary>
    /// 用 QuickFind 演算法實現的並查集。
    /// </summary>
    public class QuickFindUF : UF
    {
        public int ArrayVisitCount { get; private set; } //記錄數組訪問的次數。

        /// <summary>
        /// 新建一個使用 quick-find 實現的並查集。
        /// </summary>
        /// <param name="n">並查集的大小。</param>
        public QuickFindUF(int n) : base(n) { }

        /// <summary>
        /// 重置數組訪問計數。
        /// </summary>
        public void ResetArrayCount()
        {
            this.ArrayVisitCount = 0;
        }
        
        /// <summary>
        /// 尋找 p 所在的連通分量。
        /// </summary>
        /// <param name="p">需要尋找的結點。</param>
        /// <returns>返回 p 所在的連通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            this.ArrayVisitCount++;
            return this.parent[p];
        }

        /// <summary>
        /// 判斷兩個結點是否屬於同一個連通分量。
        /// </summary>
        /// <param name="p">需要判斷的結點。</param>
        /// <param name="q">需要判斷的另一個結點。</param>
        /// <returns>如果屬於同一個連通分量則返回 true，否則返回 false。</returns>
        public override bool IsConnected(int p, int q)
        {
            Validate(p);
            Validate(q);
            this.ArrayVisitCount += 2;
            return this.parent[p] == this.parent[q];
        }

        /// <summary>
        /// 將兩個結點所在的連通分量合併。
        /// </summary>
        /// <param name="p">需要合併的結點。</param>
        /// <param name="q">需要合併的另一個結點。</param>
        public override void Union(int p, int q)
        {
            Validate(p);
            Validate(q);
            int pID = this.parent[p];
            int qID = this.parent[q];
            this.ArrayVisitCount += 2;

            // 如果兩個結點同屬於一個連通分量，那麼什麼也不做。
            if (pID == qID)
            {
                return;
            }

            for (int i = 0; i < this.parent.Length; ++i)
            {
                if (this.parent[i] == pID)
                {
                    this.parent[i] = qID;
                    this.ArrayVisitCount++;
                }
            }

            this.ArrayVisitCount += this.parent.Length;
            this.count--;
            return;
        }

        /// <summary>
        /// 獲得 parent 數組。
        /// </summary>
        /// <returns>id 數組。</returns>
        public int[] GetParent()
        {
            return this.parent;
        }
    }
}

Main 方法：

using System;
using UnionFind;

namespace _1._5._1
{
    /*
     * 1.5.1
     * 
     * 使用 quick-find 演算法處理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。
     * 對於輸入的每一對整數，給出 id[] 數組的內容和訪問數組的次數。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var quickFind = new QuickFindUF(10);

            foreach (string s in input)
            {
                quickFind.ResetArrayCount();

                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                int[] id = quickFind.GetParent();
                quickFind.Union(p, q);
                foreach (int root in id)
                {
                    Console.Write(root + " ");
                }
                Console.WriteLine("數組訪問：" + quickFind.ArrayVisitCount);
            }
        }
    }
}

1.5.2

題目

使用 quick-union 演算法（請見 1.5.2.3 節代碼框）完成練習 1.5.1。
另外，在處理完輸入的每對整數之後畫出 id[] 數組表示的森林。

解答

quick-union 的官方實現：QuickUnionUF.java。

和上題一樣的方式，增加一個記錄訪問數組次數的類成員變數，在每次訪問數組的語句執行後自增即可。

程式輸出的森林，用縮進表示子樹：

|---- 0
    |---- 9
|---- 1
|---- 2
|---- 3
|---- 4
|---- 5
|---- 6
|---- 7
|---- 8
數組訪問：1
|---- 0
    |---- 9
|---- 1
|---- 2
|---- 4
    |---- 3
|---- 5
|---- 6
|---- 7
|---- 8
數組訪問：1
|---- 0
    |---- 9
|---- 1
|---- 2
|---- 4
    |---- 3
|---- 6
|---- 7
|---- 8
    |---- 5
數組訪問：1
|---- 0
    |---- 9
|---- 1
|---- 2
    |---- 7
|---- 4
    |---- 3
|---- 6
|---- 8
    |---- 5
數組訪問：1
|---- 0
    |---- 9
|---- 1
    |---- 2
        |---- 7
|---- 4
    |---- 3
|---- 6
|---- 8
    |---- 5
數組訪問：1
|---- 0
    |---- 9
|---- 1
    |---- 2
        |---- 7
    |---- 8
        |---- 5
|---- 4
    |---- 3
|---- 6
數組訪問：7
|---- 1
    |---- 2
        |---- 7
    |---- 8
        |---- 5
|---- 4
    |---- 0
        |---- 9
    |---- 3
|---- 6
數組訪問：3
|---- 1
    |---- 2
        |---- 7
    |---- 4
        |---- 0
            |---- 9
        |---- 3
    |---- 8
        |---- 5
|---- 6
數組訪問：3

代碼

QuickUnionUF.cs，這個類繼承了 UF.cs，重新實現了 Union() 和 Find() 等方法。

關於 UF.cs 可以參見原書中文版 P138 或英文版 P221 的演算法 1.5。

namespace UnionFind
{
    /// <summary>
    /// 用 QuickUnion 演算法實現的並查集。
    /// </summary>
    public class QuickUnionUF : UF
    {
        public int ArrayVisitCount { get; private set; } //記錄數組訪問的次數。

        /// <summary>
        /// 建立使用 QuickUnion 的並查集。
        /// </summary>
        /// <param name="n">並查集的大小。</param>
        public QuickUnionUF(int n) : base(n) { }

        /// <summary>
        /// 重置數組訪問計數。
        /// </summary>
        public virtual void ResetArrayCount()
        {
            this.ArrayVisitCount = 0;
        }

        /// <summary>
        /// 獲得 parent 數組。
        /// </summary>
        /// <returns>返回 parent 數組。</returns>
        public int[] GetParent()
        {
            return this.parent;
        }

        /// <summary>
        /// 尋找一個結點所在的連通分量。
        /// </summary>
        /// <param name="p">需要尋找的結點。</param>
        /// <returns>該結點所屬的連通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            while (p != this.parent[p])
            {
                p = this.parent[p];
                this.ArrayVisitCount += 2;
            }
            return p;
        }

        /// <summary>
        /// 將兩個結點所屬的連通分量合併。
        /// </summary>
        /// <param name="p">需要合併的結點。</param>
        /// <param name="q">需要合併的另一個結點。</param>
        public override void Union(int p, int q)
        {
            int rootP = Find(p);
            int rootQ = Find(q);
            if (rootP == rootQ)
            {
                return;
            }

            this.parent[rootP] = rootQ;
            this.ArrayVisitCount++;
            this.count--;
        }
    }

}

Main 方法

using System;
using UnionFind;

namespace _1._5._2
{
    /*
     * 1.5.2
     * 
     * 使用 quick-union 演算法（請見 1.5.2.3 節代碼框）完成練習 1.5.1。
     * 另外，在處理完輸入的每對整數之後畫出 id[] 數組表示的森林。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var quickUnion = new QuickUnionUF(10);

            foreach (string s in input)
            {
                quickUnion.ResetArrayCount();
                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                quickUnion.Union(p, q);
                int[] parent = quickUnion.GetParent();
                for (int i = 0; i < parent.Length; ++i)
                {
                    if (parent[i] == i)
                    {
                        Console.WriteLine("|---- " + i);
                        DFS(parent, i, 1);
                    }
                }
                Console.WriteLine("數組訪問：" + quickUnion.ArrayVisitCount);
            }
        }

        static void DFS(int[] parent, int root, int level)
        {
            for (int i = 0; i < parent.Length; ++i)
            {
                if (parent[i] == root && i != root)
                {
                    for (int j = 0; j < level; ++j)
                    {
                        Console.Write("    ");
                    }
                    Console.WriteLine("|---- " + i);
                    DFS(parent, i, level + 1);
                }
            }
        }
    }
}

1.5.3

題目

使用加權 quick-union 演算法（請見演算法 1.5）完成練習 1.5.1 。

解答

加權 quick-union 的官方實現：WeightedQuickUnionUF.java。

樣例輸出：

9 1 2 3 4 5 6 7 8 9 數組訪問：3
9 1 2 3 3 5 6 7 8 9 數組訪問：3
9 1 2 3 3 5 6 7 5 9 數組訪問：3
9 1 7 3 3 5 6 7 5 9 數組訪問：3
9 7 7 3 3 5 6 7 5 9 數組訪問：5
9 7 7 3 3 7 6 7 5 9 數組訪問：3
9 7 7 9 3 7 6 7 5 9 數組訪問：5
9 7 7 9 3 7 6 7 5 7 數組訪問：9

代碼

WeightedQuickUnionUF.cs，這個類繼承了 QuickUnion.cs，重新實現了 Union() 和 Find() 等方法。

關於 QuickUnion.cs 可以參見 1.5.2 的代碼部分。

namespace UnionFind
{
    /// <summary>
    /// 使用加權 quick-union 演算法的並查集。
    /// </summary>
    public class WeightedQuickUnionUF : QuickUnionUF
    {
        protected int[] size; // 記錄各個樹的大小。

        public int ArrayParentVisitCount { get; private set; } // 記錄 parent 數組的訪問次數。
        public int ArraySizeVisitCount { get; private set; } //記錄 size 數組的訪問次數。

        /// <summary>
        /// 建立使用加權 quick-union 的並查集。
        /// </summary>
        /// <param name="n">並查集的大小。</param>
        public WeightedQuickUnionUF(int n) : base(n)
        {
            this.size = new int[n];
            for (int i = 0; i < n; ++i)
            {
                this.size[i] = 1;
            }
            this.ArrayParentVisitCount = 0;
            this.ArraySizeVisitCount = 0;
        }

        /// <summary>
        /// 清零數組訪問計數。
        /// </summary>
        public override void ResetArrayCount()
        {
            this.ArrayParentVisitCount = 0;
            this.ArraySizeVisitCount = 0;
        }

        /// <summary>
        /// 獲取 size 數組。
        /// </summary>
        /// <returns>返回 size 數組。</returns>
        public int[] GetSize()
        {
            return this.size;
        }

        /// <summary>
        /// 尋找一個結點所在的連通分量。
        /// </summary>
        /// <param name="p">需要尋找的結點。</param>
        /// <returns>該結點所屬的連通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            while (p != this.parent[p])
            {
                p = this.parent[p];
                this.ArrayParentVisitCount += 2;
            }
            this.ArrayParentVisitCount++;
            return p;
        }

        /// <summary>
        /// 將兩個結點所屬的連通分量合併。
        /// </summary>
        /// <param name="p">需要合併的結點。</param>
        /// <param name="q">需要合併的另一個結點。</param>
        public override void Union(int p, int q)
        {
            int rootP = Find(p);
            int rootQ = Find(q);
            if (rootP == rootQ)
            {
                return;
            }

            if (this.size[rootP] < this.size[rootQ])
            {
                this.parent[rootP] = rootQ;
                this.size[rootQ] += this.size[rootP];
            }
            else
            {
                this.parent[rootQ] = rootP;
                this.size[rootP] += this.size[rootQ];
            }
            this.ArrayParentVisitCount++;
            this.ArraySizeVisitCount += 4;
            this.count--;
        }
    }
}

Main 方法

using System;
using UnionFind;

namespace _1._5._3
{
    /*
     * 1.5.3
     * 
     * 使用加權 quick-union 演算法（請見演算法 1.5）完成練習 1.5.1 。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var weightedQuickUnion = new WeightedQuickUnionUF(10);

            foreach (string s in input)
            {
                weightedQuickUnion.ResetArrayCount();
                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                weightedQuickUnion.Union(p, q);
                int[] parent = weightedQuickUnion.GetParent();
                for (int i = 0; i < parent.Length; ++i)
                {
                    Console.Write(parent[i] + " ");
                }
                Console.WriteLine("數組訪問：" + weightedQuickUnion.ArrayParentVisitCount);
            }
        }
    }
}

1.5.4

題目

在正文的加權 quick-union 演算法示例中，對於輸入的每一對整數（包括對照輸入和最壞情況下的輸入），給出 id[] 和 sz[] 數組的內容以及訪問數組的次數。

解答

對照輸入和最壞輸入均在書中出現，中文版見：P146，英文版見：P229。

樣例輸出：

4 3
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 5 6 7 8 9
size:   1 1 1 1 2 1 1 1 1 1
parent visit count:3
size visit count:4

3 8
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 5 6 7 4 9
size:   1 1 1 1 3 1 1 1 1 1
parent visit count:5
size visit count:4

6 5
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 6 6 7 4 9
size:   1 1 1 1 3 1 2 1 1 1
parent visit count:3
size visit count:4

9 4
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 6 6 7