C#,图论与图算法,无向图(Graph)回环(Cycle)的不相交集(disjoint)或并集查找(union find)判别算法与源代码

1 回环(Cycle)的不相交集(disjoint)或并集

不相交集数据结构是一种数据结构,它跟踪划分为多个不相交(非重叠)子集的一组元素。联合查找算法是对此类数据结构执行两个有用操作的算法:

查找:确定特定元素所在的子集。这可用于确定两个元素是否在同一子集中。

并集:将两个子集合并为一个子集。这里我们首先要检查这两个子集是否属于同一个集合。如果没有,那么我们就不能执行联合。

在这篇文章中,我们将讨论不相交集数据结构的应用。应用程序用于检查给定的图形是否包含循环。

联合查找算法可用于检查无向图是否包含圈。注意,我们已经讨论了一种检测循环的算法。这是另一种基于联合查找的方法。此方法假定图形不包含任何自循环。

我们可以跟踪一维数组中的子集,我们称之为父数组[]。

让我们考虑以下图表:

2 图表中的循环

对于每条边,使用边的两个顶点创建子集。如果两个顶点位于同一子集中,则会找到一个循环。

3 核心代码

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorit

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-22 13:00:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-22 13:00:01       101 阅读
  3. 在Django里面运行非项目文件

    2024-03-22 13:00:01       82 阅读
  4. Python语言-面向对象

    2024-03-22 13:00:01       91 阅读

热门阅读

  1. Android Zygote的面试问题

    2024-03-22 13:00:01       46 阅读
  2. RCE漏洞

    RCE漏洞

    2024-03-22 13:00:01      43 阅读
  3. 面试算法-71-加一

    2024-03-22 13:00:01       45 阅读
  4. Node.js 常用命令

    2024-03-22 13:00:01       42 阅读
  5. 查询ECS服务启动命令包含特定的字符串

    2024-03-22 13:00:01       47 阅读
  6. 【蓝桥杯常考题型汇总】

    2024-03-22 13:00:01       45 阅读