Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Printing Eulerian Path using Fleury's Algorithm
2.1.
Example 🧪
2.2.
Algorithm 🕵️
2.3.
Code implementation 🧑‍💻
2.4.
Output 📤
2.5.
Time complexity ⏳
3.
Frequently Asked Questions
3.1.
How would you track down the Eulerian way?
3.2.
What is the essential rule in Fleury's calculation?
3.3.
How would you decide whether a chart has an Euler way?
3.4.
What do you mean by Euler's way?
3.5.
What is the contrast between the Euler path and the Euler circuit?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Printing Eulerian Path using Fleury's Algorithm

Author Adya Tiwari
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Hey, Ninjas🥷 Eulerian Path is a way in a diagram that visits each edge precisely once. Eulerian Circuit is an Eulerian Path that beginnings and closures on a similar vertex. We recommend you go through the Eulers Path once before reading about this topic.

Fleury's Algorithm is utilized to show the Euler way or Euler circuit from a given diagram. In this calculation, beginning from one edge, it attempts to move other nearby vertices by eliminating the past vertices. Utilizing this stunt, the chart becomes more straightforward in each move toward tracking down the Euler way or circuit.

In this article, we will see the Eulerian path and Fleury's algorithm and how one is used for the other.

Eulers path CN

Printing Eulerian Path using Fleury's Algorithm

We need to take a look at specific standards to get the way or circuit −

✔️Ensure the chart has either 0 or 2 odd vertices.

✔️Assuming there are 0 odd vertices, begin anyplace. Considering there are two odd vertices, start at one of them.

✔️Follow edges each in turn. If you decide between a scaffold and a non-span, consistently pick the non-span.

✔️Stop when you run out of edges.

You can practice questions on Euler's path from here. 😉

The thought is, "don't break bridges," so we can return to a vertex and cross the excess edges. For instance, let us think about the accompanying diagram.

Example 🧪

Example CN Euler's

Two vertices have odd degrees, '2' and '3', and we can begin from any of them. Let us start the visit from vertex '2'.

Example CN Euler's

Three edges are going out from vertex '2'. Which one to pick? We don't like the edge '2-3' since that is a scaffold (we will not have the option to return to '3'). We can pick any of the leftover two edges. Allow us to say we choose '2-0'. We eliminate this edge and move to vertex '0'. 🤔

Example CN Euler's

There is just a single edge from vertex '0', so we pick it, eliminate it and move to vertex '1'. Euler visit becomes '2-0 0-1'.

Example CN Euler's

There is just a single edge from vertex '1', so we pick it, eliminate it and move to vertex '2'. Euler's visit becomes '2-0 0-1 1-2.'

Example CN Euler's

Again there is just a single edge from vertex 2, so we pick it, eliminate it and move to vertex 3. Euler visit becomes '2-0 0-1 1-2 2-3'

Example CN Euler's

No more edges are left now, so we stop here. Last visit is '2-0 0-1 1-2 2-3'.

Algorithm 🕵️

🔸We first find the beginning stage, which should be an odd vertex (on the off chance that there are odd vertices), and store it in factor 'u.' Assuming zero odd vertices, we start from vertex '0'. 

🔸We call printEulerUtil() to print Euler visits beginning with u. We promptly think about it when we cross all adjacent vertices of u, assuming there is just a single contiguous vertex. 

🔸If there are more than one nearby vertices, we consider a contiguous v provided that edge u-v isn't a scaffold.

🔸We count a few vertices reachable from u. We eliminate edge u-v and measure the number of reachable vertices from u. 

🔸On the off chance that the amount of reachable vertices is decreased, edge u-v is a scaffold. To count reachable vertices, we can utilize BFS or DFS Algorithm; we have involved DFS in the above code. The capability DFSCount(u) returns a few vertices reachable from u.

When an edge is handled (remembered for the Euler visit), we eliminate it from the diagram. We supplant the vertex section with - 1 in the contiguousness list to eliminate the edge. Just erasing the hub may not function as the code is recursive, and a parent call might be in the nearness list.

findStartVert(graph)
Input: The given graph.
Output: Find the starting vertex to this algorithm.
Begin
   for all vertex i, in the graph, do
      deg := 0
      for all vertex j, which are adjacent with i, do
         deg := deg + 1
      done
      if deg is odd, then
         return i
   done
   when all degree is even return 0
End

dfs(prev, start, visited)
Input: The pervious and start vertex to perform DFS, and visited list.
Output: Count the number of nodes after DFS.
Begin
   count := 1
   visited[start] := true
   for all vertex b, in the graph, do
      if prev is not u, then
         if u is not visited, then
            if start and u are connected, then
               count := count + dfs(start, u, visited)
            end if
         end if
      end if
   done
   return count
End

isBridge(u, v)
Input: The start and end node.
Output: True when u and v are forming a bridge.
Begin
   deg := 0
   for all vertex i which are adjacent with v, do
      deg := deg + 1
   done
   if deg > 1, then
      return false
   return true
End

fleuryAlgorithm(start)
Input: The starting vertex.
Output: Display the Euler path or circuit.
Begin
   edge := get the number of edges in the graph
   //it will not initialize in next
   recursion call
   v_count = number of nodes
   //this will not initialize in next recursion call
   for all vertex v, which are adjacent with start, do
      make visited array and will with false value
      if isBridge(start, v), then decrease v_count by 1
      cnt = dfs(start, v, visited)
      if difference between cnt and v_count <= 2, then
         print the edge (start →‡ v)
         if isBridge(v, start), then decrease v_count by 1
         remove edge from start and v
         decrease edge by 1
         fleuryAlgorithm(v)
      end if
   done
End

Code implementation 🧑‍💻

In the accompanying code, it is accepted that the given chart has an Eulerian trail or Circuit. The fundamental center is to print an Eulerian trail or circuit. We can use isEulerian() to initially check whether there is an Eulerian Trail or Circuit in the diagram.

coding gif
# Python program print Eulerian Trail in a given Eulerian or Semi-Eulerian Graph

from collections import defaultdict

class Graph:

    def __init__(self,vertices):
        self.V= vertices
        self.graph = defaultdict(list)
        self.Time = 0
    def addEdge(self,s,v):
        self.graph[s].append(v)
        self.graph[v].append(s)

    def rmvEdge(self, s, v):
        for index, key in enumerate(self.graph[s]):
            if key == v:
                self.graph[s].pop(index)
        for index, key in enumerate(self.graph[v]):
            if key == s:
                self.graph[v].pop(index)

    def DFSCount(self, v, visited):
        count = 1
        visited[v] = True
        for i in self.graph[v]:
            if visited[i] == False:
                count = count + self.DFSCount(i, visited)      
        return count

    def isValidNextEdge(self, s, v):
        if len(self.graph[s]) == 1:
            return True
        else:

            visited =[False]*(self.V)
            count1 = self.DFSCount(s, visited)

            self.rmvEdge(s, v)
            visited =[False]*(self.V)
            count2 = self.DFSCount(s, visited)

            self.addEdge(s,v)

            return False if count1 > count2 else True

    def printEulerUtil(self, s):
        for v in self.graph[s]:
            if self.isValidNextEdge(s, v):
                print("%d-%d " %(s,v)),
                self.rmvEdge(s, v)
                self.printEulerUtil(v)

    def printEulerTour(self):
        s = 0
        for i in range(self.V):
            if len(self.graph[i]) %2 != 0 :
                s = i
                break
        print ("\n")
        self.printEulerUtil(s)

# Create a graph given in the above diagram
g2 = Graph(3)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 0)
g2.printEulerTour()

g1 = Graph(4)
g1.addEdge(1, 2)
g1.addEdge(0, 3)
g1.addEdge(1, 1)
g1.addEdge(3, 1)
g1.printEulerTour()

g3 = Graph (5)
g3.addEdge(1, 0)
g3.addEdge(0, 3)
g3.addEdge(2, 0)
g3.addEdge(4, 2)
g3.addEdge(2, 4)
g3.addEdge(3, 4)
g3.addEdge(3, 0)
g3.addEdge(2, 4)
g3.printEulerTour()

Output 📤

0-1
1-2
2-0


0-3
3-1
1-1
1-2


1-0
0-3
3-4
4-2

Time complexity ⏳

The time complexity of the above execution is O ((V+E)^2). The capability printEulerUtil() is like DFS and it calls isValidNextEdge() which additionally does DFS twice. The time complexity of DFS for nearness list portrayal is O(V+E). Consequently, in general, the time complexity is O((V+E)*(V+E)) which can be composed as O(E2) for an associated chart.

⚠️The variables V and E here refer to Vertices and Edges.

time complexity
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How would you track down the Eulerian way?

To track down the Euler way (not a cycle), let's get down to business: if there are two vertices of odd degrees, then simply add an edge ( V 1, V 2 ). In the subsequent chart, we find the Euler cycle (it will exist) and afterward eliminate the "imaginary" edge ( V 1, V 2 ) from the response.

What is the essential rule in Fleury's calculation?

The essential rule of Fleury's calculation is exceptionally straightforward. To find the Euler Path or Euler Circuit, the extension edge ought to be the last edge we need to cross.

How would you decide whether a chart has an Euler way?

If chart G has an Euler way, it should have precisely two odd vertices. Or on the other hand, If the quantity of odd vertices in G is something besides 2, then, at that point, G can't have an Euler way.

What do you mean by Euler's way?

In chart hypothesis, an Eulerian trail (or Eulerian way) is a path in a limited diagram that visits each edge precisely once (considering returning to vertices). An Eulerian circuit or cycle is an Eulerian trail that beginnings and closures on a similar vertex.

What is the contrast between the Euler path and the Euler circuit?

An Euler Path is a way that goes through each edge of a chart precisely once. An Euler Circuit is an Euler Path that starts and finishes at a similar vertex.

Conclusion

In this article, we learned that the Eulerian Path is a way in a diagram that visits each edge precisely once. Eulerian Circuit is an Eulerian Path that beginnings and closures on a similar vertex. With that we shall conclude this article.

Check out this problem - Root To Leaf Path

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in pygameCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Eulerian Path and Circuit
Next article
Print all Paths from a Given Source to a Destination
Live masterclass