首页

▼ 算法合集

▼ 加密算法

▼ 凯撒密码

凯撒密码

▼ Hill密码算法

Hill密码算法

▼ 多项式哈希算法

多项式哈希算法

▼ Rail Fence Cipher

Rail Fence Cipher

▼ Graph算法

▼ 关节点

关节点

▼ Bellman-Ford算法

Bellman-Ford算法

▼ 广度优先搜索

广度优先搜索

▼ GraphBridges

桥接模式

▼ 深度优先搜索

深度优先搜索

▼ 检测循环

检测循环

▼ Dijkstra算法

Dijkstra算法

▼ Eulerian Path

欧拉路径

▼ Floyd-Warshall算法

Floyd-Warshall算法

▼ HamiltonianCycle

Hamiltonian Cycle

▼ Kruskal算法

Kruskal算法

▼ Prim算法

Prim算法

▼ 强连通分量

强连通分量

▼ 拓扑排序

拓扑排序

▼ Travelling Salesman Problem

Travelling Salesman

▼ 图像处理算法

▼ Seam Carving算法

内容感知缩放算法

▼ 链表

▼ 反向遍历

反向遍历

▼ GraphTraversal

GraphTraversal

▼ 数学算法

▼ 二进制浮点数

BinaryFloatingPoint

▼ 位操作

位操作算法

▼ 复数

复数

▼ 欧几里得算法

Euclidean Algorithm

▼ Euclidean Distance

欧几里得距离

▼ 阶乘算法

阶乘算法

▼ 快速幂算法

快速幂算法

▼ Fibonacci数列

斐波那契数列

▼ 傅里叶变换

Fourier变换

▼ Horner法

霍纳法则

▼ 整数划分

整数划分

▼ 判断是否为2的幂

判断是否为2的幂

▼ 最小公倍数

最小公倍数

▼ Liu Hui

Liu Hui

▼ 矩阵

Matrix

▼ Pascal三角形

Pascal三角形

▼ Primality Test

素数测试

▼ 质因数

质因数

▼ 弧度计算

弧度计算

▼ 埃拉托色尼筛法

埃拉托色尼筛法

▼ SquareRoot

SquareRoot

▼ MachineLearning

▼ K均值算法

K均值算法

▼ K近邻算法

K近邻算法

▼ 搜索算法

▼ 二分查找算法

二分查找

▼ 插值搜索算法

插值搜索算法

▼ 跳跃搜索算法

跳跃搜索算法

▼ 线性搜索

线性搜索算法

▼ 集合

▼ 笛卡尔积

笛卡尔积

▼ 组合总和

组合总和

▼ 组合算法

组合算法

▼ Fisher-Yates洗牌算法

Fisher-Yates洗牌算法

▼ 背包问题

背包问题

▼ 最长公共子序列

最长公共子序列

▼ 最长递增子序列

最长递增子序列

▼ 最大子数组

最大子数组

▼ 排列组合

排列组合

▼ 幂集

幂集算法

▼ 最短公共超序列

最短公共超序列

▼ Sorting Algorithms

▼ 冒泡排序

冒泡排序

▼ 桶排序算法

桶排序算法

▼ 计数排序算法

计数排序

▼ 堆排序算法

堆排序

▼ 插入排序

插入排序

▼ 归并排序

归并排序

▼ 快速排序算法

快速排序算法

▼ 基数排序

基数排序

▼ 选择排序算法

选择排序算法

▼ 希尔排序

希尔排序

▼ 统计学

▼ 加权随机

加权随机算法

▼ 字符串算法

▼ Hamming距离

Hamming距离

▼ KnuthMorrisPratt算法

Knuth-Morris-Pratt算法

▼ LevenshteinDistance

Levenshtein距离

▼ 最长公共子串

最长公共子串

▼ 回文检测算法

回文检测算法

▼ Rabin-Karp算法

Rabin-Karp算法

▼ 正则表达式匹配

正则表达式匹配

▼ Z算法

Z算法

▼ Tree Data Structure

▼ 广度优先搜索

广度优先搜索

▼ 深度优先搜索

深度优先搜索

▼ 未分类

▼ 最佳买卖股票时机

最佳买卖股票时机

▼ 汉诺塔算法

HanoiTower

▼ 跳跃游戏算法

跳跃游戏

▼ KnightTour

骑士巡逻

▼ N皇后问题

N皇后问题

▼ 雨水收集

雨水收集

▼ 递归楼梯问题

递归楼梯问题

▼ 方阵旋转

方阵旋转

▼ 独特路径

UniquePaths

▼ 数据结构

▼ BloomFilter算法

布隆过滤器

▼ 不相交集数据结构

Disjoint Set

▼ 双向链表

双向链表

▼ Graph

Graph算法

▼ 哈希表

哈希表

▼ Heap数据结构

Heap数据结构

▼ 链表

链表

▼ LRU缓存

LRU缓存

▼ 优先队列

优先队列

▼ 队列

队列

▼ 栈结构

栈结构

▼ Tree Data Structure

树结构

▼ AVL树

AVL树

▼ 二叉搜索树

二叉搜索树

▼ Fenwick树

Fenwick树

▼ 红黑树

红黑树

▼ 线段树

SegmentTree

▼ Trie数据结构

Trie数据结构

图中的循环检测

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

定义

封闭游走由一系列顶点和顶点组成,起点和终点相同,在序列中相邻的顶点之间。在有向图中,每条边必须被游走一致地沿着其方向:边必须从两个连续顶点中较早的一个指向两个顶点中较晚的一个。开始顶点的选择并不重要:从不同的起始顶点遍历相同的循环边序列会产生相同的封闭游走。

简单循环可以定义为不允许重复顶点和边的封闭游走,除了起始和结束顶点的重复,或者作为此类游走中的边集合。这两种定义在有向图中是等价的,在有向图中简单循环也被称为有向循环:游走中顶点和边的循环序列完全由它使用的边集合决定。在无向图中,循环的边集合可以通过游走以两种方向之一遍历,为每个无向循环产生两个可能的定向循环。电路可以是允许顶点重复但边不重复的封闭游走;然而,它也可以是一个简单循环,因此当使用它时建议明确定义。

示例

循环

一个带有颜色标记的图,说明路径H-A-B(绿色),封闭路径或带重复顶点的游走B-D-E-F-D-C-B(蓝色)和一个**没有重复边的循环或顶点H-D-G-H(红色)

无向图中的循环

无向循环

有向图中的循环

有向循环

参考资料

一般信息:

无向图中的循环:

有向图中的循环: