Graphs/Euler Circuit

Euler tour/Euler path - a tour around a graph that visits every edge of the graph exactly once.

• The following pages all redirect to Graphs/Euler Tour:
  • Euler Tour
  • Graphs/Euler Tour
  • Euler Path
  • Graphs/Euler Path

Euler circuit/Euler cycle - an Euler tour that starts and ends at the same vertex.

• The following pages all redirect to Graphs/Euler Circuit:
  • Euler Circuit
  • Graphs/Euler Circuit
  • Euler Cycle
  • Graphs/Euler Cycle

Overview

An Euler Circuit is an Euler path or Euler tour (a path through the graph that visits every edge of the graph exactly once) that starts and ends at the same vertex.

Algorithm

Fleury's Algorithm

To print the Euler Circuit of a graph (if it has one), you can use Fleury's Algorithm [1].

Step 1:

• Check that the graph has 0 or 2 odd vertices
• If there are any other number of odd vertices, no Euler circuit exists

Step 2:

• If there are 0 odd vertices, start at any node on the graph
• If there are 2 odd vertices, start at one of the odd vertices

Step 3:

• Follow edges one at a time.
• Edges can be classified as bridges (edges that lead to "dead end" nodes with only one edge) or non-bridges
• If you have a choice among multiple edges, choose the non-bridges first, leave the bridge edge for last.

Step 4:

• Stop when you run out of edges.

Related

Graphs:

• Graphs#Graph Traversals
• Graphs/Depth First Traversal
• Graphs/Breadth First Traversal
• Graphs/Euler Tour
• Graphs/Euler Circuit

Traversals on trees:

• Trees/Preorder
• Trees/Postorder
• Trees/Inorder

Breadth-first search and traversal on trees:

• BFS - breadth first search
• BFT - breadth first traversal

Depth-first search and traversal on trees:

• DFS - depth first search
• DFT - depth first traversal

OOP design patterns:

• Tree Traversal/Traversal Method Template

Category:Traversal