Graphs/Euler Circuit: Difference between revisions
From charlesreid1
| Line 20: | Line 20: | ||
=Algorithm= | =Algorithm= | ||
==Fleury's Algorithm== | ==Undirected Graphs: Fleury's Algorithm== | ||
To print the Euler Circuit of | To print the Euler Circuit of an undirected graph (if it has one), you can use Fleury's Algorithm [https://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/]. | ||
This algorithm is <math>O(E^2)</math> (where E is number of edges). | |||
Step 1: | Step 1: | ||
| Line 39: | Line 41: | ||
Step 4: | Step 4: | ||
* Stop when you run out of edges. | * Stop when you run out of edges. | ||
==Directed Graphs: Hierholzer's Algorithm== | |||
To print the Euler circuit on a directed graph, use the Hierholzer algorithm. | |||
This algorithm is <math>O(E)</math> (where E is number of edges). | |||
=Related= | =Related= | ||
Revision as of 05:32, 28 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
Undirected Graphs: Fleury's Algorithm
To print the Euler Circuit of an undirected graph (if it has one), you can use Fleury's Algorithm [1].
This algorithm is $ O(E^2) $ (where E is number of edges).
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.
Directed Graphs: Hierholzer's Algorithm
To print the Euler circuit on a directed graph, use the Hierholzer algorithm.
This algorithm is $ O(E) $ (where E is number 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
