##
__Reason to
write this__

__Reason to write this__
I was searched for C program to find
the euler path/circuit in Google, but I am not able to find any C
implementation for this. So I have decided to write a C program to find euler
path/circuit. I written, compiled and published here. I hope it will helpful
for some persons like me who are looking for C program to find the euler
path/circuit.

__EULER CIRCUIT PROBLEM__
Consider the three figures in Figure below. A popular puzzle is to
reconstruct these figures using a pen,
drawing each line exactly once. The pen may not be lifted from the paper while
the drawing is
being performed. As an extra challenge, make the pen finish at the same point
at which it started. This puzzle has a
surprisingly simple solution.

The first figure can be drawn only if the starting point is the lower
left- or right-hand corner, and it
is not possible to finish at the starting point. The second figure is easily
drawn with the
finishing point the same as the starting point, but the third figure cannot be
drawn at all within the parameters of
the puzzle.

We can convert this problem to a graph theory
problem by assigning a vertex to each intersection.Then the edges can be
assigned in the natural manner, as shown in below.

After this conversion is performed, we must find a path in the graph
that visits every edge exactly
once. If we are to solve the "extra challenge," then we must find a
cycle that visits every
edge exactly once. This graph problem was solved in 1736 by Euler and marked the beginning of
graph theory. The problem is thus commonly referred to as an Euler path (sometimes Euler tour) or Euler circuit problem, depending on the
specific problem statement. The Euler tour and Euler circuit
problems, though slightly different, have the same basic solution. Thus, we
will consider the Euler circuit problem

__EULER PATH__
In graph theory Euler path is a path that visits
each edge from the graph exactly once.

__EULER CYCLE/EULER CIRCUIT__
Euler cycle is a
Euler path that starts and ends with the same node.

__EULER GRAPH__
Euler graph is a
graph with graph which contains Euler cycle.

__EULERS THEOREM__

Connected undirected graph is Euler graph if and
only if every node in the graph is of even degree (has even number of edges starting from that node).

__HIERHOLZER’S ALGORITHM__
This is an algorithm to find an
Eulerian circuit in a connected graph in which every vertex has even degree.

1. Choose any vertex v and push it
onto a stack. Initially all edges are unmarked.

2. While the stack is nonempty, look
at the top vertex, u, on the stack. If u has an unmarked incident edge, say, to a
vertex w, then push w onto the stack and mark the edge uw. On the other hand, if u has
no unmarked incident edge, then pop u off the stack and print it.

When the stack is empty, you will have
printed a sequence of vertices that correspond to an Eulerian circuit

__HIERHOLZER’S ALGORITHM - Example__**We will use two stacks in this example:**

__tempPath__and__finalPath__in order to be able to combine the simple cycles we’ve found into one big cycle (the searched Euler’s cycle).**1.Lets start with edge 0 (arbitrary choice)**

**Adding 0 to the tempPath stack.**

**tempPath:0**

**finalPath:<empty>**

**2.Lets choose edge 0->1 (arbitrary choice).**

**Erasing the edge and adding 1 to tempPath stack**

**tempPath:0 1**

**finalPath:<empty>**

**3.Lets choose edge 1->2 (arbitrary choice).**

**Erasing the edge and adding 2 to tempPath stack**

**tempPath:0 1 2**

**finalPath:<empty>**

**4.Lets choose edge 2->3 (arbitrary choice).**

**Erasing the edge and adding 3 to tempPath stack**

**tempPath:0 1 2 3**

**finalPath:<empty>**

**5.Lets choose edge 3->0 (only possible choice).****Erasing the edge and adding 0 to tempPath stack**

**tempPath:0 1 2 3 0**

**finalPath:<empty>**

**We’ve created a simple cycle and there is nowhere to go, but there are still unvisited edges! Go back to vertex with unvisited edge, moving elements from tempPath to finalPath.**

**tempPath:0 1 2 3 0**

**finalPath:<empty>**

**6.Move back from o to 3.**

**Move o from tempPath to finalPath.**

**tempPath:0 1 2 3**

**finalPath:0**

**7.Move back from 3 to 2.**

**Move 3 from tempPath to finalPath.**

**tempPath:0 1 2**

**finalPath:0 3**

**8.Lets choose edge 2->4 (arbitrary choice).**

**Erasing the edge and adding 4 to tempPath stack**

**tempPath:0 1 2 4**

**finalPath:0 3**

**9.Lets choose edge 4->1 (only possible choice).**

**Erasing the edge and adding 1 to tempPath stack**

**tempPath:0 1 2 4 1**

**finalPath:0 3**

**10.Lets choose edge 1->5 (only possible choice).**

**Erasing the edge and adding 5 to tempPath stack**

**tempPath:0 1 2 4 1 5**

**finalPath:0 3**

**11.Lets choose edge 5->2 (only possible choice).****Erasing the edge and adding 2 to tempPath stack**

**tempPath:0 1 2 4 1 5 2**

**finalPath:0 3**

**So we have passed through all the edges! Now all we have to do is move elements from tempPath stack to finalPath stack!**

**tempPath:0 1 2 4 1 5 2**

**finalPath:0 3**

**The result sequence in finalPath stack is an Euler’s cycle!****tempPath:0 1 2 4 1 5 2**

**finalPath:0 3**

to

**tempPath:<empty>**

**finalPath:0 3 2 5 1 4 2 1 0**

##
__C Program to find
EULER Circuit/ EULER Path using Hierholzer’s Algorithm __

__C Program to find EULER Circuit/ EULER Path using Hierholzer’s Algorithm__

*//Written and Compiled by M.Karuppasamy Pandiyan*

*#include<stdio.h>*

*#include<conio.h>*

*char stack[20];*

*int top=-1, n;*

*char b[20],finalPath[20];*

*char ajMat[20][20];*

*int fp=0,count;*

*//Push into Stack Operation*

*void push(char val)*

*{*

*top=top+1;*

*stack[top]=val;*

*}*

*//Pop from Stack Operation*

*char pop()*

*{*

*return stack[top--];*

*}*

*//To check weather all adjecent vertices/nodes are visited*

*//or not*

*int allVisited(int i)*

*{*

*int j;*

*for(j=0;j<n;j++)*

*{*

*if(ajMat[i][j]=='y')*

*return 0;*

*}*

*return 1;*

*}*

*//To get the current index of node in the array b[] of nodes*

*int getNo(char c)*

*{*

*int l=0;*

*while(c!=b[l])*

*l++;*

*return l;*

*}*

*//Display the Euler circuit/path*

*void displayPath()*

*{*

*int i;*

*for(i=0;i<fp;i++)*

*{*

*printf("%c ->",finalPath[i]);*

*}*

*}*

*//To find the Euler circuit/path and store it in finalPath[] array*

*void eularFind(int root)*

*{*

*int l,j;*

*//push root into the stack*

*push(b[root]);*

*//Run upto stock becomes empty i.e top=-1*

*while(top!=-1)*

*{*

*//get the array index of top of the stack*

*l=getNo(stack[top]);*

*//If all adjacent nodes are already visited*

*//pop element from stack and store it in finalpath[] array*

*if(allVisited(l))*

*{*

*finalPath[fp++]=pop();*

*}*

*//If any unvisited node available push that node into stack*

*//mark that edge as already visited by marking 'n' in adjMat[][]*

*//break the iteration*

*else*

*{*

*for(j=0;j<n;j++)*

*{*

*if(ajMat[l][j]=='y')*

*{*

*ajMat[l][j]='n';*

*ajMat[j][l]='n';*

*push(b[j]);*

*break;*

*}*

*}*

*}*

*}*

*}*

*//To get the degree of node i.e no of edges currently connected to the node*

*int getDegree(int i)*

*{*

*int j,deg=0;*

*for(j=0;j<n;j++)*

*{*

*if(ajMat[i][j]=='y') deg++;*

*}*

*return deg;*

*}*

*//To assign the root of the graph*

*//Condition 1: If all Nodes have even degree, there should be a euler Circuit/Cycle*

*//We can start path from any node*

*//Condition 2: If exactly 2 nodes have odd degree, there should be euler path.*

*//We must start from node which has odd degree*

*//Condition 3: If more than 2 nodes or exactly one node have odd degree, euler path/circuit not possible.*

*//findRoot() will return 0 if euler path/circuit not possible*

*//otherwise it will return array index of any node as root*

*int findRoot()*

*{*

*int i,cur=1;//Assume root as 1*

*for(i=0;i<n;i++)*

*{*

*if(getDegree(i)%2!=0)*

*{*

*count++;*

*cur=i;//Store the node which has odd degree to cur variable*

*}*

*}*

*//If count is not exactly 2 then euler path/circuit not possible so return 0*

*if(count!=0 && count!=2)*

*{*

*return 0;*

*}*

*else return cur;// if exactly 2 nodes have odd degree, it will return one of those node as root otherwise return 1 as root as assumed*

*}*

*int main()*

*{*

*char v;*

*int i,j,l;*

*printf("Enter the number of nodes in a graph\n");*

*scanf("%d",&n);*

*printf("Enter the value of node of graph\n");*

*for( i=0; i<n; i++)*

*{*

*scanf("%s",&b[i]);//store the nodes in b[] array*

*}*

*//Get the Graph details by using adjacency matrix*

*printf("Enter the value in adjancency matrix in from of 'Y' or 'N'\n");*

*printf("\nIf there is an edge between the two vertices then enter 'Y' or 'N'\n");*

*for( i=0; i<n; i++)*

*printf(" %c ",b[i]);*

*for( i=0;i<n; i++)*

*{*

*printf("\n%c ",b[i]);*

*for( j=0; j<n; j++)*

*{*

*printf("%c ",v=getch());*

*ajMat[i][j]=v;*

*}*

*printf("\n\n");*

*}*

*//findRoot() will return 0 if euler path/circuit not possible*

*//otherwise it will return array index of any node as root*

*int root;*

*if(root=findRoot())*

*{*

*if(count) printf("Available Euler Path is\n");*

*else printf("Available Euler Circuit is\n");*

*eularFind(root);*

*displayPath();*

*}*

*else printf("Euler path or circuit not available\n");*

*getch();*

*}*

__Example1: Input Graph__

__Output__

__Example2: Input Graph__

*Output:*

*Exmple 3:Input Graph*

*Output:*

__Reference:__1. Data Structures and Algorithm Analysis in C by Mark Allen Weiss.

2. Euler Graphs Power point Presentation by Deyan Yosifov, Telerik Corporation.

### Goto Data Structure Concepts

nice

ReplyDeleteThank You Ajay...

Deletethank you so much brother

ReplyDeleteWith Pleasure Sister.... Mekala .....

DeleteThe only article on the web that has exactly what I wanted. Thank you!

ReplyDeleteThanks thodoris...

DeleteThank you so much for nice description

ReplyDeleteGreat work! Thanks for the excellent article, it really helped me understand Eulerian algorithms. I will take your advice and donate to someone in need!

ReplyDeleteThanks Brother for your donation.....

Delete"EULER PATH

ReplyDeleteIn graph theory Euler path is a path that visits each **node** from the graph exactly once."

Its a typo ... should be edge!

Thanks for pointing it out. I updated the same.

Delete