Eulerian Path

I haven't been able to update my blog for a long time because I have been very busy in the last few days, so now here's an update.

I'm going to jump to Eulerian Path in this post. My Program uses a recursive function to get the Eulerian Path for a given graph. For those who don't know what Eulerian Path is

"Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex"

If there is to be an Eulerian path for a given graph the graph must have lesser than three nodes with odd number of edges. If there are two nodes with odd number of edges the Euler walk must begin in an odd node and end with the other odd node.

This graph can't have an Eulerian Path.



But this graph can have an Eulerian Path.



You can download the eulerwalk.cpp file by clicking on the link.

#include <iostream>
#include <list>

using namespace std;

int graph[100][100];
int n, x, y, steps;
list<int> path;

void walk(int pos){
for(int i = 0; i < n; i++){
    if(graph[pos][i] > 0){
             graph[pos][i] --;
             graph[i][pos] --;
             walk(i);
             break;
    }
}
path.push_back(pos+1);

}

int main(){

cin >> n;
for(int i = 0; i < n; i++){
  cin >> x >> y;
  graph[x-1][y-1] ++; //we are using zero index 
}
walk(0);
while(!path.empty()){
    cout << path.back() << ' ';
    path.pop_back();
}
}

Read More...

Summary only...