Union-Find 检测无向图有无环路算法
算法 检测 Find union 无向 环路
2023-09-11 14:20:27 时间
不相交集合数据结构(Disjoint-set data structure)是一种用于跟踪集合被分割成多个不相交的子集合的数据结构,每个集合通过一个代表来标识,代表即集合中的某个成员。
Union-Find 算法为该数据结构提供了两种非常有用的操作:
- Find:判断子集中是否存在特定的元素。可以用于检测是否两个元素存在于相同的子集中。
- Union:将两个不子集合并成新的子集合。
Union-Find 算法的一个具体的应用就是在无向图(Undirected Graph)中检测是否存在环路(Cycle)。
例如,下面这张无向图 G:
0 | \ | \ 1-----2
G 中包含 3 个顶点和 3 条边 {{0, 1}, {1, 2}, {2, 1}}。
初始时,设 int[] parent = new int[VertexCount],默认每个顶点的子集中只有自己,设为 -1。
0 1 2 -1 -1 -1
处理边 {0, 1},Find 顶点 0 和 1 的子集,发现它们在不同的子集中,则 Union 它们,此时 1 代表了子集 {0, 1}。
0 1 2 1 -1 -1
处理边 {1, 2},Find 顶点 1 和 2 的子集,发现它们在不同的子集中,则 Union 它们,此时 2 代表了子集 {0, 1, 2}。
0 1 2 1 2 -1
处理边 {2, 1},Find 顶点 2 和 1 的子集,发现它们在相同的子集中,则图存在环。
Union-Find 算法简单实现如下,其时间复杂度为 O(n)。
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 5 namespace GraphAlgorithmTesting 6 { 7 class Program 8 { 9 static void Main(string[] args) 10 { 11 Graph g = new Graph(6); 12 g.AddEdge(0, 1, 16); 13 g.AddEdge(0, 2, 13); 14 g.AddEdge(1, 2, 10); 15 g.AddEdge(1, 3, 12); 16 //g.AddEdge(2, 1, 4); 17 g.AddEdge(2, 4, 14); 18 //g.AddEdge(3, 2, 9); 19 g.AddEdge(3, 5, 20); 20 //g.AddEdge(4, 3, 7); 21 //g.AddEdge(4, 5, 4); 22 23 Console.WriteLine(); 24 Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount); 25 Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount); 26 Console.WriteLine(); 27 28 Console.WriteLine("Is there cycle in graph: {0}", g.HasCycle()); 29 30 Console.ReadKey(); 31 } 32 33 class Edge 34 { 35 public Edge(int begin, int end, int weight) 36 { 37 this.Begin = begin; 38 this.End = end; 39 this.Weight = weight; 40 } 41 42 public int Begin { get; private set; } 43 public int End { get; private set; } 44 public int Weight { get; private set; } 45 46 public override string ToString() 47 { 48 return string.Format( 49 "Begin[{0}], End[{1}], Weight[{2}]", 50 Begin, End, Weight); 51 } 52 } 53 54 class Graph 55 { 56 private Dictionary<int, List<Edge>> _adjacentEdges 57 = new Dictionary<int, List<Edge>>(); 58 59 public Graph(int vertexCount) 60 { 61 this.VertexCount = vertexCount; 62 } 63 64 public int VertexCount { get; private set; } 65 66 public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } } 67 68 public IEnumerable<Edge> Edges 69 { 70 get { return _adjacentEdges.Values.SelectMany(e => e); } 71 } 72 73 public int EdgeCount { get { return this.Edges.Count(); } } 74 75 public void AddEdge(int begin, int end, int weight) 76 { 77 if (!_adjacentEdges.ContainsKey(begin)) 78 { 79 var edges = new List<Edge>(); 80 _adjacentEdges.Add(begin, edges); 81 } 82 83 _adjacentEdges[begin].Add(new Edge(begin, end, weight)); 84 } 85 86 private int Find(int[] parent, int i) 87 { 88 if (parent[i] == -1) 89 return i; 90 return Find(parent, parent[i]); 91 } 92 93 private void Union(int[] parent, int x, int y) 94 { 95 int xset = Find(parent, x); 96 int yset = Find(parent, y); 97 parent[xset] = yset; 98 } 99 100 public bool HasCycle() 101 { 102 int[] parent = new int[VertexCount]; 103 for (int i = 0; i < parent.Length; i++) 104 { 105 parent[i] = -1; 106 } 107 108 // Iterate through all edges of graph, find subset of both 109 // vertices of every edge, if both subsets are same, 110 // then there is cycle in graph. 111 foreach (var edge in this.Edges) 112 { 113 int x = Find(parent, edge.Begin); 114 int y = Find(parent, edge.End); 115 116 if (x == y) 117 { 118 return true; 119 } 120 121 Union(parent, x, y); 122 } 123 124 return false; 125 } 126 } 127 } 128 }
本篇文章《Union-Find 检测无向图有无环路算法》由 Dennis Gao 发表自博客园,未经作者本人同意禁止任何形式的转载,任何自动或人为的爬虫转载行为均为耍流氓。
相关文章
- 全排列生成算法 .
- 网络KPI异常检测之时序分解算法
- Java实现 基础算法 求100以内的质数
- 缓动小算法
- python 排序算法总结及实例详解
- 【OpenCV-Python】教程:4-6 FAST (Features from Accelerated Segment Test)算法角点检测
- [转]RSA,DSA等加解密算法介绍
- ML之回归预测之Lasso:利用Lasso算法对对红酒品质wine数据集解决回归(实数值评分预测)问题—优化模型【增加新(组合)属性】
- 零基础学Python(第八章 for循环·超重点,本章会有几个简单的单层循环练习,后续会有针对算法的单独章节)
- 轻量型目标检测算法总结
- 4种基于像素分割的文本检测算法
- 基于KDtree的电路故障检测算法的MATLAB仿真
- 【项目实战】Python基于局部离群因子LOF算法(LocalOutlierFactor)实现信用卡数据异常值检测项目实战
- 目标检测系列算法:YOLOv7代码复现
- 每日算法之旅(第一天):枚举算法的平凡与伟大
- DNS通道检测 国内学术界研究情况——研究方法:基于特征或者流量,使用机器学习决策树分类算法居多
- 【数据挖掘】2020奇安信秋招算法方向试卷1 笔试题解析
- 目标检测算法——安全帽识别数据集(附下载链接)
- 目标检测算法——垃圾分类数据集汇总(附下载链接)
- HBase选择Store file做compaction的算法
- 首次开源这一强大算法,我们向Meta致敬
- DL之yolov3:使用yolov3算法时需要对Ubuntu系统进行配置的简介、过程步骤之详细攻略
- 【目标检测论文解读复现NO.31】基于改进YOLO v5复杂场景下肉鹅姿态的检测算法研究
- 基于IMU原始数据的爬坡检测算法Python程序