樹的應用：并查集

• 并查集的概念：
• 三種基本操作：
• 例：
• 代碼實現：

并查集的概念：

將所有的數據元素放在一個集合中，將集合分成若干個互不相交的子集，每一個子集對應一顆樹，所有的自己組成森林。

三種基本操作：

例：

初始化一個集合，將每一個元素初始化成一個獨立的子集，即令parent=-1

根節點的絕對值表示該顆樹的節點個數，負號表示該節點為根節點
parent里存放著該節點的雙親節點的數組下標

代碼實現：

//初始化 #define SIZE 100 int UFSets[SIZE]; //定義并查集，因為數組下標和數據元素值相同，所以只需要一個數組來存放parent的值即可void Initial(int s[]){for(int i = 0;i < sizeof(s) / sizeof(s[0]);i ++)s[i] = -1; } //查找 int Find(int s[],int x){while(s[x] >= 0)x = s[x];return x; } //合并 void Union(int s[],int Root1,int Root2){s[Root2] = Root1; }

總結

以上是生活随笔為你收集整理的数据结构之树的应用：并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。