WOLFRAM

Wolfram 语言与系统参考资料中心

FindCycle[g]

找出图 g 的一个圈.

FindCycle[g,k]

找出图 g 中长度最多为 k 的圈.

FindCycle[g,{k}]

找出长度恰好为 k 的圈.

FindCycle[g,{kmin,kmax}]

找出长度介于 kmin 和 kmax 之间的圈.

FindCycle[g,kspec,s]

找出最多 s 个圈.

FindCycle[{g,v},…]

找出包含顶点 v 的圈.

FindCycle[{vw,…},…]

用规则 vw 指定图 g.

更多信息
Details and Options Details and Options
背景
范例  
基本范例  
范围  
Specification  
Enumeration  
应用  
属性和关系  
可能存在的问题  
参见
相关指南
历史
按以下格式引用：

FindCycle

FindCycle[g]

找出图 g 的一个圈.

FindCycle[g,k]

找出图 g 中长度最多为 k 的圈.

FindCycle[g,{k}]

找出长度恰好为 k 的圈.

FindCycle[g,{kmin,kmax}]

找出长度介于 kmin 和 kmax 之间的圈.

FindCycle[g,kspec,s]

找出最多 s 个圈.

FindCycle[{g,v},…]

找出包含顶点 v 的圈.

FindCycle[{vw,…},…]

用规则 vw 指定图 g.

更多信息

  • 圈也被称为环路或循环.
  • 圈是由除了起止顶点之外无重复的顶点或边组成的路径.
  • FindCycle 会给出圈的列表. 每个圈都以边的列表的形式给出.
  • 若没有圈则 FindCycle 会返回一个空列表.
  • FindCycle[g,kspec,All] 会找出所有的圈.
  • 对于加权图，FindCycle[g,k] 会给出所有总权重小于 k 的圈.
  • FindCycle 适用于无向图、有向图和多重图.

背景

  • FindCycle 试图找出图中的一个或多个不同的圈. 圈以一系列边列表的形式返回，若不存在任何圈则返回 {}. 图的圈（若该圈被显式路径标明且路径由特定端点组成，则更适合被称为环路）是由不同边组成的一个连续序列，头尾两条边的端点是重合的. 圈的枚举可用于规划许多情况下的环路（地铁、公路旅行等等），计算电子电路中的电压或电流，或者发现计算机程序中的无限循环.
  • 一般来说，FindCycle[g,kspec,s] 试图找出 s 个长度为 kspec 的圈. 计数要求 s 可以被省略（在这种情况下它取值为 1），可以是一个正整数，或者是 All. 长度要求 kspec 可以是一个正整数 k（在这种情况下它表示圈长度小于或等于 k），可以是 Infinity，可以是有一个正整数的列表 {k}（在这种情况下它表示圈长度正好等于 k），或者是有两个正整数的列表 {kmin,kmax}（在这种情况下它表示圈长度从 kmin 到 kmax）.
  • 对于 FindCycle[g,{3}] 返回 {} 的图被称为无三角形图；对 FindCycle[g,{4}] 返回 {} 的图被称为无正方形图. 长度为 n 的环被称为哈密顿环，其中 n 是图的顶点数，拥有这种环的图被称为哈密顿图.
  • 不包含任何圈的图被称为无圈图并可用 AcyclicGraphQ 检测.
  • FindCycle 返回的是简单的圈，而 FindHamiltonianCycle、FindEulerianCycle 和 FindFundamentalCycles 返回的是特殊类型的圈. FindPath 可被用于寻找两个指定顶点之间的路径（两端端点不重合的边的集合），返回值是沿着路径的连续顶点组成的集合.

范例

打开所有单元 关闭所有单元

基本范例  (2)

找出图的一个圈：

Wolfram Language code: g = [image];
Wolfram Language code: FindCycle[g]

突出显示该圈：

Wolfram Language code: HighlightGraph[g, %]

找出图中所有的圈：

Wolfram Language code: g = WheelGraph[4];
Wolfram Language code: FindCycle[g, Infinity, All]

范围  (12)

Specification  (6)

FindCycle 适用于无向图：

Wolfram Language code: FindCycle[[image]]

有向图：

Wolfram Language code: FindCycle[[image]]

加权图：

Wolfram Language code: FindCycle[[image]]

多重图：

Wolfram Language code: FindCycle[[image]]

用规则指定图：

Wolfram Language code: FindCycle[{2 -> 1, 1 -> 4, 3 -> 2, 2 -> 5, 6 -> 3, 5 -> 4, 4 -> 7, 6 -> 5, 8 -> 5, 6 -> 9, 7 -> 8, 7 -> 10, 9 -> 8, 11 -> 8, 12 -> 9, 10 -> 11, 12 -> 11}]

FindCycle 适用于大型图：

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: FindCycle[g]//Short//Timing

Enumeration  (6)

长度恰好为8的圈：

Wolfram Language code: FindCycle[[image], {8}]

长度最多为6的圈：

Wolfram Language code: FindCycle[[image], 6]

长度介于3和5之间的圈：

Wolfram Language code: FindCycle[[image], {3, 5}]

包含给定顶点的圈：

Wolfram Language code: FindCycle[{[image], 8}]

找出所有的圈：

Wolfram Language code: FindCycle[[image], Infinity, All]//Short

若没有圈 FindCycle 会给出空列表：

Wolfram Language code: FindCycle[[image]]

应用  (4)

找出经过每个顶点恰好一次的哈密尔顿圈：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"]
Wolfram Language code: FindCycle[g, {VertexCount[g]}]

显示这个圈：

Wolfram Language code: HighlightGraph[g, First[%]]

找出带有给定性质的圈：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"]

包含一个顶点：

Wolfram Language code: FindCycle[{g, 1}]

包含一条边：

Wolfram Language code: cycles = FindCycle[g, Infinity, All];
Wolfram Language code: Select[cycles, MemberQ[#, 52 | 25]&]//Short

找出韩国釜山地铁的最长环线：

Wolfram Language code: busan = [image];

最长环线的长度：

Wolfram Language code: allloops = FindCycle[busan, Infinity, All];
Wolfram Language code: Max[Length /@ allloops]

找出该环线：

Wolfram Language code: Short[loop = Select[allloops, (Length[#] == %)&]]
Wolfram Language code: HighlightGraph[busan, loop]

计划遛狗的路线：

Wolfram Language code: g = [image];

对给定的起始结点，找出5条长度至少是20的避开有坏狗的街道的路线：

Wolfram Language code: walks = FindCycle[{EdgeDelete[g, {1216, 23, 1318, 2127}], "Home"}, {20, Infinity}, 5]
Wolfram Language code: HighlightGraph[g, walks[[1]]]

属性和关系  (3)

用 FindHamiltonianCycle 找出访问每个顶点恰好一次的圈：

Wolfram Language code: g = [image];
Wolfram Language code: FindHamiltonianCycle[g]

等价于：

Wolfram Language code: FindCycle[g, {VertexCount[g]}]

EdgeCycleMatrix 给出了所有的圈的基：

Wolfram Language code: g = WheelGraph[4]
Wolfram Language code: basis = Pick[EdgeList[g], #, 1] & /@ EdgeCycleMatrix[g]

构造全部的圈：

Wolfram Language code: addedges[edges_] := Cases[Tally[Flatten[edges]], {e_, _ ? OddQ} :> e]
Wolfram Language code: cycles = addedges[Pick[basis, #, 1]]& /@ Most[Tuples[{1, 0}, 3]]

从 FindCycle 找出全部的圈：

Wolfram Language code: FindCycle[g, Infinity, All]

FindCycle 对无向图给出空列表：

Wolfram Language code: g = GraphData[{"CayleyTree", {3, 4}}]
Wolfram Language code: AcyclicGraphQ[g]
Wolfram Language code: FindCycle[g]

可能存在的问题  (1)

FindCycle 忽略了自圈：

Wolfram Language code: g = [image];
Wolfram Language code: FindCycle[g]
Wolfram Research (2014)，FindCycle，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindCycle.html （更新于 2015 年）.

文本

Wolfram Research (2014)，FindCycle，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindCycle.html （更新于 2015 年）.

CMS

Wolfram 语言. 2014. "FindCycle." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/FindCycle.html.

APA

Wolfram 语言. (2014). FindCycle. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindCycle.html 年

BibTeX

@misc{reference.wolfram_2026_findcycle, author="Wolfram Research", title="{FindCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindCycle.html}", note=[Accessed: 31-October-2026]}

BibLaTeX

@online{reference.wolfram_2026_findcycle, organization={Wolfram Research}, title={FindCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindCycle.html}, note=[Accessed: 31-October-2026]}