Eulerian Path — A brief
--
Eulerian path : A Eulerian path is a path in a graph that passes through all of its edges exactly once. A Eulerian cycle is a Eulerian path that is a cycle.
Eulerian path is used to solve problems in an undirected multigraph with loops.
Applications of Eulerian path :-
There are many applications of Eularian path in real life such as garbage collectors, airplane pilots and world navigators etc.
The above image represents Eulerian path, airline companies use this kinds of route map the map is made of destinations (vertices) and lines connecting destinations (edges).
Similarly Eulerian path is also used by garbage collectors as they don’t have to go through same house or neighborhood again, it saves time and increases efficiency.
Algorithm :
There are two methods to determine the Eulerian path, one is the Recursive Approach and the second one is Non-Recursive Approach
Recursive approach :-
Procedure FindEulerPath(V)
1. Iterate through all the edges outgoing from vertex V;
remove this edge from graph,
and call FindEulerPath from the second edge of this edge;
2. Add vertex V to the answer.
NON-Recursive approach :-
stack St;
put start vertex in St;
until St is empty
let V be the value at the top of St;
if degree (V)=0, then
add V to the answer;
otherwise
find any edge coming out of V;
remove it from the graph;
put the second end of this edge in St;
This article was written by my colleagues —
