长沙医疗网站建设,厦门网页设计代做,自己做个网站多少钱,竞彩网站建设联合查找算法是一种对此类数据结构执行两个有用操作的算法#xff1a; 查找#xff1a;确定特定元素在哪个子集中。这可用于确定两个元素是否在同一子集中。联合#xff1a;将两个子集连接成一个子集。这里首先我们必须检查这两个子集是否属于同一个集合。如果否#xff0c…
联合查找算法是一种对此类数据结构执行两个有用操作的算法 查找确定特定元素在哪个子集中。这可用于确定两个元素是否在同一子集中。联合将两个子集连接成一个子集。这里首先我们必须检查这两个子集是否属于同一个集合。如果否则我们无法执行联合。
不相交集的 UNION 和 FIND 操作
一组元素 a1、a2、…an 上的关系可以分为等价类。元素 a 的等价类是 S 的子集它包含 S 中与 a 相关的所有元素。
通过这两个操作将一组元素划分为等价的类 1.联合
2. 寻找
一个集合被分成子集。每个子集都包含相关元素。如果我们知道 ai 和 aj 这两个元素是相关的那么我们可以执行以下操作 1.找到子集包含ai的Si
2.找到子集包含aj的Sj
3.如果S,和Si是两个独立的子集
然后我们通过合并 Si 和 Sj 创建一个新的子集
新子集 Si C ∪ PS j 。
该算法是动态的因为在算法过程中集合可以通过并集操作改变。 例子
让我们检查一个例子来理解数据结构是如何应用的。为此请考虑以下问题陈述
问题给定一个无向图任务是检查图中是否包含循环。
例子 输入下图 输出是解释存在顶点 {0, 1, 2} 的循环。 我们已经讨论了一种在有向图中检测循环的算法。这里可以使用 Union-Find 算法来检查无向图是否包含循环。这个想法是 最初创建仅包含一个节点的子集该节点是其自身的父节点。现在在遍历边时如果边的两个端节点属于同一个集合则它们形成一个循环。否则执行 union 将子集合并在一起。 注意此方法假定图形不包含任何自环。 插图 请按照下图更好地理解 让我们考虑下图 使用数组来跟踪子集以及哪些节点属于该子集。让数组成为parent[]。 最初父数组的所有槽都被初始化为保存与节点相同的值。 父母 [] {0, 1, 2}。同样当节点的值与其父节点的值相同时即为该节点子集的根。 现在一条一条地处理所有的边。Edge 0-1: 找到顶点0和1所在的子集。 0 和 1 属于子集 0 和 1。 因为它们在不同的子集中所以取它们的并集。 要合并请将节点 0 作为节点 1 的父节点反之亦然。 1 成为 0 的父级1 现在代表子集 {0, 1} parent[] {1, 1, 2} 边 1-2 1 在子集 1 中2 在子集 2 中。 因为它们在不同的子集中所以取并集。 将 2 作为 1 的父级。2 现在代表子集 {0, 1, 2} parent[] {1, 2, 2} 边 0-2 0 在子集 2 中2 也在子集 2 中。 因为 1 是 0 的父级而 2 是 1 的父级。所以 0 也属于子集 2 因此包括这条边形成一个循环。 因此上图包含一个循环。 按照以下步骤来实现这个想法
最初创建一个parent[]数组来跟踪子集。遍历所有边 通过查找 parent[] 数组检查每个节点属于哪个子集直到节点和父节点相同。如果两个节点属于同一个子集则它们属于一个循环。否则对这两个子集执行联合操作。如果没有找到循环则返回 false。
下面是上述方法的实现。
// A union-find algorithm to detect cycle in a graph
#include bits/stdc.h
using namespace std;// a structure to represent an edge in graph
class Edge {
public:int src, dest;
};// a structure to represent a graph
class Graph {
public:// V- Number of vertices, E- Number of edgesint V, E;// graph is represented as an array of edgesEdge* edge;
};// Creates a graph with V vertices and E edges
Graph* createGraph(int V, int E)
{Graph* graph new Graph();graph-V V;graph-E E;graph-edge new Edge[graph-E * sizeof(Edge)];return graph;
}// A utility function to find the subset of an element i
int find(int parent[], int i)
{if (parent[i] i)return i;return find(parent, parent[i]);
}// A utility function to do union of two subsets
void Union(int parent[], int x, int y) { parent[x] y; }// The main function to check whether a given graph contains
// cycle or not
int isCycle(Graph* graph)
{// Allocate memory for creating V subsetsint* parent new int[graph-V];// Initialize all subsets as single element setsfor(int i 0; i graph-V; i) {parent[i] i;}// Iterate through all edges of graph, find subset of// both vertices of every edge, if both subsets are// same, then there is cycle in graph.for (int i 0; i graph-E; i) {int x find(parent, graph-edge[i].src);int y find(parent, graph-edge[i].dest);if (x y)return 1;Union(parent, x, y);}return 0;
}// Driver code
int main()
{/* Let us create the following graph0| \| \1---2 */int V 3, E 3;Graph* graph createGraph(V, E);// add edge 0-1graph-edge[0].src 0;graph-edge[0].dest 1;// add edge 1-2graph-edge[1].src 1;graph-edge[1].dest 2;// add edge 0-2graph-edge[2].src 0;graph-edge[2].dest 2;if (isCycle(graph))cout Graph contains cycle;elsecout Graph doesnt contain cycle;return 0;
}// This code is contributed by rathbhupendra输出 Graph contains cycle 请注意 union()和find()的实现是天真的在最坏的情况下需要O(n) 时间。使用按等级或高度联合可以将这些方法改进为 O(logN)。
