带你读《图解算法小抄》二十五、图(12)

简介: 带你读《图解算法小抄》二十五、图(12)

带你读《图解算法小抄》二十五、图(11)https://developer.aliyun.com/article/1347761?groupCode=tech_library


15.检测图中的循环


在图论中,循环是指一条由边和顶点组成的路径,其中一个顶点可以从自身到达。循环有几种不同的类型,主要有闭合路径和简单循环。

1定义

闭合路径由一系列从同一顶点开始和结束的顶点组成,序列中的任意两个连续顶点在图中相邻。

 

在有向图中,每条边在路径中的遍历必须与其方向一致:边必须从序列中较早的顶点指向序列中较后的顶点。起始顶点的选择并不重要:从不同的起始顶点遍历相同的循环边序列会产生相同的闭合路径。

 

简单循环可以定义为一条闭合路径,不允许重复顶点和边,除了起始和结束顶点的重复,或者可以定义为该路径中的边的集合。在有向图中,这两种定义是等价的,简单循环也被称为有向循环:在循环中的顶点和边的循环序列完全由其使用的边的集合确定。

 

在无向图中,循环的边集可以按照两个方向之一遍历,为每个无向循环提供两种可能的有向循环。电路可以是允许重复顶点但不允许重复边的闭合路径;然而,它也可以是简单循环,因此在使用时建议明确定义。

 

2示例

image.png

循环

带有颜色边的图,用于说明路径 H-A-B(绿色),带有重复顶点的闭合路径或循环路径 B-D-E-F-D-C-B(蓝色)以及没有重复边或顶点的循环 H-D-G-H(红色)

无向图中的循环

image.png

 

 

带你读《图解算法小抄》二十五、图(13)https://developer.aliyun.com/article/1347759?groupCode=tech_library

相关文章
|
1月前
|
算法 搜索推荐 图计算
图计算中的社区发现算法是什么?请解释其作用和常用算法。
图计算中的社区发现算法是什么?请解释其作用和常用算法。
53 0
|
1月前
|
存储 人工智能 算法
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
131 0
|
11天前
|
算法 计算机视觉
图像处理之基于图的广度优先搜索组件标记算法
图像处理之基于图的广度优先搜索组件标记算法
8 0
|
12天前
|
存储 算法
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
9 0
|
25天前
|
存储 算法 C++
c++算法学习笔记 (8) 树与图部分
c++算法学习笔记 (8) 树与图部分
|
1月前
|
算法 数据可视化
圆填充( CIRCLE PACKING)算法圆堆图圆形空间填充算法可视化
圆填充( CIRCLE PACKING)算法圆堆图圆形空间填充算法可视化
|
1月前
|
存储 算法
图的深度优先算法
图的深度优先算法
20 0
|
1月前
|
算法 数据可视化 大数据
圆堆图circle packing算法可视化分析电商平台网红零食销量采集数据
圆堆图circle packing算法可视化分析电商平台网红零食销量采集数据
|
1月前
|
存储 编解码 自然语言处理
【软件设计师备考 专题 】深入理解数据压缩、递归和图的相关算法
【软件设计师备考 专题 】深入理解数据压缩、递归和图的相关算法
72 0
|
1月前
|
算法 搜索推荐 数据挖掘
图计算中的图算法有哪些常见的类型?请举例说明每种类型的算法。
图计算中的图算法有哪些常见的类型?请举例说明每种类型的算法。
55 0

热门文章

最新文章