Before applying Fleury’s algorithm to the graph, we need to check the degrees of the nodes to find out whether there is an Euler circuit in the graph or not. If there is an Euler circuit then we can start the search from any node, if there is an Euler path then we have to start from the first node. How to understand which is the first node? Any node in an undirected graph whose degree is odd can be taken as the start node. A node whose outdegree is greater than 1 in the directed graph is the starting node of the Euler path.
Now assume that the initial node is u
. Now we take any node v adjacent to u such that deleting the edge u−v does not make the graph disconnected, i.e. u−v is not a bridge. Then we delete the u−v edge and do the same from the next node v node. But it may happen that there is no edge u−v that is not a bridge, in which case we proceed along the bridge. Continue in this way until all edges are removed. Once all the edges are removed we will find the Euler circuit or path.
See the above graph as an example. This graph does not have an Euler circuit but does have a path. Here 1 is the starting node (indegree 1, outdegree 2). At the beginning we see 1−>4 is a bridge, we skip it and proceed through 1−>2 and delete the edge.
Now only one edge can be traversed from node 2, 2−>3 and 2−>3 is a bridge. Since there are no other options, we proceed with 2−>3. By simulating like this we can see that our path is 1−>2−>3−>1−>4
. This is the Euler path of the graph.
I won’t go into the proof of the algorithm but the basic idea is not to break the bridge before all the edges on one side have been visited. Once you break the bridge, the graph is disconnected, you cannot return to the node on the other side of the bridge. So we’ll be wise to visit all non-bridges first, only break the bridge when we see no such edge.
Although Fleury’s algorithm is easy to understand, it is a bit of a hassle to implement because it has to find a bridge every time an edge is deleted. If you run the algorithm to find Tarzan’s Bridge every time you E
Running the Tarzan algorithm many times and the complexity becomes O(E2). So we will implement another simple algorithm without going into so much trouble. So why did we learn Fleury’s algorithm? Because one will get you thinking about bicycles, bridges, connected components, etc. and maybe help you solve another problem someday.
Now we will learn Heirholzer’s algorithm. This algorithm is mainly for finding the Euler circuit, but with a bit of intelligence, the Euler path can also be found, I will come to that point later. If a graph has an Euler circuit, the indegree and outdegree of each node are equal. Now we have to use our powers of observation.
If the graph has an Euler circuit, each node must belong to a cycle. When you leave each node, there must be a cycle path back to that node. And the most important observation is that if you delete all the edges of a cycle from the Euler circuit graph, the connected graph that remains will be a new Euler circuit, because when you delete the edges of the cycle, the indegree and outdegree of all the nodes in the cycle decrease by 1.
Our task will be to detect one cycle at a time and delete cycle edges. We will do this recursively so that a node can delete as many cycle edges as possible.
Try to understand what is happening in the above sudocode. Here we delete one edge from each node and recursively delete all edges of that component. Finally adding the node to the stack. After all the work is done, we get the Euler circuit by removing the nodes from the stack.
If you have trouble understanding an algorithm, the best way to understand is to simulate it on a graph. Once simulated in notebook and pen, the thing will become clear. I could show the simulation here, but then you wouldn’t get into the habit of thinking. Hope you can do it yourself.
I said earlier that this algorithm is for finding the Euler circuit, so how to find the Euler path? Very simply, tracing the circuit by adding a dummy edge from the first node to the last node will also get the path. The complexity of this algorithm is O(E).
, the algorithm will also work on undirected graphs.
Think of a postman every morning leaving the post office with his bicycle and returning to the post office with letters on different streets. Which way will he have the least trouble? If the roads are thought of as a graph and the graph contains an Euler circuit, then the same road is never visited twice.
But in reality it is not possible in most cases. In that case, even if one road is used more than once, the total distance is minimized. This problem has a name, it is called the Chinese postman problem. This is a slightly advanced level problem that requires knowledge of weighted bipartite matching or min-cost-max-flow to solve. If you are interested, you can discuss this.
This time the SimpleSum class implements all the methods. Using the @Override annotation is optional here, it means that these methods implement the interface class, I will not discuss the annotation in detail here.
Now I want another kind of implementation which only sums the unique numbers instead of adding all the numbers. In that case our algorithm will be slightly different, we’ll store the numbers in a set so that every time we get a new number we can check to see if we got the number before. We create a class called UniqueSum:
We’ve got two classes that implement the interface. Now we see how to use the interface:
Here’s how I created two SummationServices. Once I used SimpleSum’s constructor, another time UniqueSum’s. But both times I assigned same type to variable. That means the SummationService interface has two different implementations.
That’s it for today, happy coding!
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
You must Join our Facebook Group and Subscribe YouTube Channel