Graphs/Euler Circuit: Difference between revisions
From charlesreid1
| Line 17: | Line 17: | ||
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. | 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 [https://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/]. | |||
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 o the odd vertices. | |||
Step 3: Follow edges one at a time. If you have a choice between a "bridge" edge and a "non-bridge" edge, always choose the "non-bridge" edge. | |||
Step 4: Stop when you run out of edges. | |||
=Related= | =Related= | ||
Revision as of 22:57, 27 April 2019
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 circuit/Euler cycle - an Euler tour that starts and ends at the same vertex.
- The following pages all redirect to Graphs/Euler Circuit:
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 o the odd vertices.
Step 3: Follow edges one at a time. If you have a choice between a "bridge" edge and a "non-bridge" edge, always choose the "non-bridge" edge.
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:
Breadth-first search and traversal on trees:
Depth-first search and traversal on trees:
OOP design patterns:
Flags
