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 —

Amber Upadhyay, Kedar Trivedi and Ashwin Sapariya and Rohan Pandav (me) as a project given to us by our teaching faculty of Data Structures and Algorithms.

--

--

--

Hi. My name is Rohan Pandav and I am a 21-year young guy from Mumbai, India. I code and play video games. Content will be pretty diverse.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The Junior Developer Journey (09 May 2022)

Don’t ask what you can do for documentation — ask what documentation can do for you!

How to Connect S3 Data to Looker using Starburst Presto

My Favorite SQL Prompt Features

What are you trying to do?

Get Started with Spring Boot…

A simple HTML page

[Dynamic] Encode Club Announces the Launch of Encode Filecoin Accelerator

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohan Pandav

Rohan Pandav

Hi. My name is Rohan Pandav and I am a 21-year young guy from Mumbai, India. I code and play video games. Content will be pretty diverse.

More from Medium

Comparing Insertion Sorting and Merge Sorting Algorithms

Introduction to Linked Lists

Spiral Matrix — Problem solution

[Leetcode][17]Letter Combinations of a Phone Number