WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

FindCycle
✖
FindCycle

✖

finds a cycle in the graph g.

✖
FindCycle[g,k]

finds a cycle of length at most k in the graph g.

✖
FindCycle[g,{k}]

finds a cycle of length exactly k.

✖
FindCycle[g,{kmin,kmax}]

finds a cycle of length between kmin and kmax.

✖
FindCycle[g,kspec,s]

finds at most s cycles.

✖
FindCycle[{g,v},…]

finds cycles that include the vertex v.

✖
FindCycle[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • A cycle is also known as a circuit or loop.
  • A cycle is a path with no repetitions of vertices or edges other than the starting and ending vertices.
  • FindCycle gives a list of cycles. Each cycle is given as a list of edges.
  • FindCycle will return an empty list if there is no cycle.
  • FindCycle[g,kspec,All] finds all the cycles.
  • For weighted graphs, FindCycle[g,k] gives all cycles with total weights less than k.
  • FindCycle works with undirected graphs, directed graphs, and multigraphs.

Background & Context

  • FindCycle attempts to find one or more distinct cycles in a graph. Cycles are returned as a list of edge lists or as {} if none exist. A cycle of a graph (more properly called a circuit when the cycle is identified using an explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edges coincide at their endpoints. Cycle enumeration can be used for planning a cyclic route in many situations (subway, road trip, etc.), computing voltage or current in electronic circuits, or discovering infinite loops in computer programs.
  • In general, FindCycle[g,kspec,s] attempts to find s cycles of length kspec. The count specification s may be omitted (in which case it is taken to be 1), may be a positive integer, or can be All. The length specification kspec may be a positive integer k (in which case it stands for cycles of length k or less), Infinity, a positive integer inside a list {k} (in which case it stands for cycles of length exactly k), or a list of two positive integers {kmin,kmax} (in which case it stands for cycles of lengths kmin through kmax).
  • A graph for which FindCycle[g,{3}] returns {} is known as a triangle-free graph, and one for which FindCycle[g,{4}] returns {} is known as square free. A cycle of length n, where n is the number of vertices in a graph, is known as a Hamiltonian cycle, and a graph possessing such a cycle is said to be Hamiltonian.
  • A graph that does not contain any cycle is called an acyclic graph and can be tested for using AcyclicGraphQ.
  • FindCycle returns simple cycles, while FindHamiltonianCycle, FindEulerianCycle, and FindFundamentalCycles return specific types of cycles. FindPath may be used to find a path (a set of edges for which the endpoints do not coincide) between two specific vertices, returned as a set of consecutive vertices along the path.

Examples

open allclose all

Basic Examples  (2)Summary of the most common use cases

Find a cycle in a graph:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-co2cc7
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-r3wdf
Out[2]=2

Highlight the cycle:

In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-vqpkgi
Out[3]=3

Find all cycles in a graph:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-d3vhle
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-miia26
Out[2]=2

Scope  (12)Survey of the scope of standard use cases

Specification  (6)

FindCycle works with undirected graphs:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-lfx0x8
Out[1]=1

Directed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-15kl6n
Out[1]=1

Weighted graphs:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-ighgre
Out[1]=1

Multigraphs:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-kbffo7
Out[1]=1

Use rules to specify the graph:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-bndh30
Out[1]=1

FindCycle works with large graphs:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-lkg873
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-b5ef0w
Out[2]=2

Enumeration  (6)

A cycle of length exactly 8:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-eygfi
Out[1]=1

A cycle of length at most length 6:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-1cmllb
Out[1]=1

A cycle of length between 3 and 5:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-v6o6ke
Out[1]=1

A cycle that includes a given vertex:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-lbl8wg
Out[1]=1

Find all cycles:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-muxwzs

FindCycle gives an empty list if there is no cycle:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-6c79w
Out[1]=1

Applications  (4)Sample problems that can be solved with this function

Find Hamiltonian cycles that visit each vertex exactly once:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-bu7km8
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-fvlylz
Out[2]=2

Show the cycle:

In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-rffun
Out[3]=3

Find cycles with a given property:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-b3mwr8
Out[1]=1

Include a vertex:

In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-ilq0ns
Out[2]=2

Include an edge:

In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-j9l0ig
In[4]:=4
✖
https://wolfram.com/xid/0rsxyjhsu-g4okdx

Find the longest loops in the Korean Busan Underground:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-6b42fb

The length of the longest loops:

In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-2jx5zd
In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-cuq9c8
Out[3]=3

Find the loops:

In[4]:=4
✖
https://wolfram.com/xid/0rsxyjhsu-7e9to4
In[5]:=5
✖
https://wolfram.com/xid/0rsxyjhsu-hy2i75
Out[5]=5

Plan a dog walk tour:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-03yo19

For a given starting node, find 5 tours of at least length 20 that avoid streets with bad dogs:

In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-eno3xt
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-mzrvk7
Out[3]=3

Properties & Relations  (3)Properties of the function, and connections to other functions

Use FindHamiltonianCycle to find cycles that visit each vertex exactly once:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-il8uue
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-jmb6at
Out[2]=2

Equivalent to:

In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-cnl73p
Out[3]=3

EdgeCycleMatrix gives a basis for all cycles:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-pydno
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-c2aec
Out[2]=2

Build all cycles:

In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-1hd4g
In[4]:=4
✖
https://wolfram.com/xid/0rsxyjhsu-bh8qbt
Out[4]=4

Find all cycles from FindCycle:

In[5]:=5
✖
https://wolfram.com/xid/0rsxyjhsu-c3rmgu
Out[5]=5

FindCycle gives an empty list for acyclic graphs:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-xshfy0
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-ffzjia
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0rsxyjhsu-66fmhb
Out[3]=3

Possible Issues  (1)Common pitfalls and unexpected behavior

FindCycle ignores self-loops:

In[1]:=1
✖
https://wolfram.com/xid/0rsxyjhsu-die81e
In[2]:=2
✖
https://wolfram.com/xid/0rsxyjhsu-xzhbfc
Out[2]=2
Wolfram Research (2014), FindCycle, Wolfram Language function, https://reference.wolfram.com/language/ref/FindCycle.html (updated 2015).
✖
Wolfram Research (2014), FindCycle, Wolfram Language function, https://reference.wolfram.com/language/ref/FindCycle.html (updated 2015).

Text

Wolfram Research (2014), FindCycle, Wolfram Language function, https://reference.wolfram.com/language/ref/FindCycle.html (updated 2015).

✖
Wolfram Research (2014), FindCycle, Wolfram Language function, https://reference.wolfram.com/language/ref/FindCycle.html (updated 2015).

CMS

Wolfram Language. 2014. "FindCycle." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindCycle.html.

✖
Wolfram Language. 2014. "FindCycle." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindCycle.html.

APA

Wolfram Language. (2014). FindCycle. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindCycle.html

✖
Wolfram Language. (2014). FindCycle. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindCycle.html

BibTeX

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

✖
@misc{reference.wolfram_2025_findcycle, author="Wolfram Research", title="{FindCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindCycle.html}", note=[Accessed: 10-July-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_findcycle, organization={Wolfram Research}, title={FindCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindCycle.html}, note=[Accessed: 10-July-2025 ]}

✖
@online{reference.wolfram_2025_findcycle, organization={Wolfram Research}, title={FindCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindCycle.html}, note=[Accessed: 10-July-2025 ]}