具有可重組態匯流排系統之處理器陣列(Processor Arrays with Reconfigurable Bus Systems簡稱PARBS)，是一種平行計算的模 型，它具有一個處理器陣列和一個可重組態匯流排。這個平行計 算的模型，可以有效率地﹑快速地解決許多問題。例如[1]﹑[2] ﹑[3]﹑[4]﹑[5]﹑[6]﹑[17]與[18]都是使用PARBS模型，來發 展快速的或常數時間的平行演算法。然而，現存的一些演算法對 於最小擴張樹問題(the minimum spanning tree problem)，在 這個計算模型上需要用O(log n)的時間。例如[2]，需要用 O(log n)的時間，和O(n^4)個處理器的PARBS來解決最小擴張樹 問題。在林順喜博士的論文中，最小擴張樹問題可以在O(log n) 的時間內，用O(n^(3+ε))個處理器的PARBS來解決，其中ε是一 個極小的正實數[3]。在[17]，最小擴張樹問題需要O(1)的時間 ，和O(n^6)個處理器的PARBS來解決。在本篇論文中，我們提出 一個利用PARBS模型，而可以在常數時間內使用較少的處理器， 來解決最小擴張樹問題的演算法。我們的最小擴張樹演算法可以 在常數時間內，用O(n^4)個處理器的PARBS來解決這個問題。首 先，為了發展我們的最小擴張樹演算法，我們先發展一個常數時 間迴圈檢查演算法，這個演算法是我們最小擴張樹演算法的基礎 。同時我們也運用常數時間迴圈檢查演算法的概念，來解決最小 擴張樹驗證問題﹑擴張樹問題與擴張樹驗證問題。最小擴張樹驗 證問題可以在O(1)的時間內，用O(n^3)個處理器的PARBS來解決。擴張樹問題可以在O(1)的時間內，用O(n^3)個處理器的PARBS來解決。擴張樹驗證問題可以在O(1)的時間內，用O(n^2)個處理器的PARBS來解決。

A processor array with reconfigurable bus system (abbreviated to PARBS)is a parallel computation model that consists of a processor array and a reconfigurable bus system. It is a very powerful parallel computation model in that it possesses the ability to solve many problems efficiently or quickly. For example [1], [2], [3], [4], [5], [6], [17] and [18] used PARBS model to develop faster or constant-time parallel algorithms. However, most existing algorithms on PARBS model use O(log n)-time to solve the minimum spanning tree problem. For example, for solving the minimum spanning tree problem, O(log n)-time and O(n^4) processors are required[2]. In Lin's paper, the minimum spanning tree problem can be solved in O(log n)-time by using O(n^(3+ε)) processors, where ε is a small positive real number[3]. In [17], it needs O(1)-time and O(n^6) processors to solve the minimum spanning tree problem.In this paper, we will show a constant-time algorithm to solve the minimum spanning tree problem on PARBS model using fewer processors. We will show how the minimum spanning tree can be found in O(1)-time on PARBS model with O(n^4) processors. At first, we develop a constant-time loop-checking algorithm in our paper to achieve the goal. We also use this loop-checking algorithm to solve the minimum spanning tree verification problem, the spanning tree problem and the spanning tree verification problem. The minimum spanning tree verification problem can be solved in O(1)-time on PARBS model with O(n^3) processors. The spanning tree problem can be solved in O(1)-time on PARBS model with O(n^3) processors. The spanning tree verification problem can be solved in O(1)-time on PARBS model with O(n^2) processors.