Fleury’s algorithm

Let G be a connected graph, if G is Eulerian, Fleury’s algorithm can determine a Eulerian path in G. We know that in a connected graph, a bridge is a edge which, if it is removed, the graph becomes unconnected:

Step 1. Choose any vertex v of the graph G and fix the current node equal to v and the current path equal to the empty sequence of edges.

Step 2: Select an edge incident with the current peak, but choosing a bridge only if there is no other alternative.

Step 3: Add E to the current path and fix the current peak with the peak at the other end of the edge E.(If E is a loop, the current peak cannot be deleted)

Step 4: Delete E from the graph. Clear any isolated peak.

Fleury’s algorithm

#include<stdio.h>

#include<mem.h>

using namespace std;

bool A[200][200];

int n,m;

typedef unsigned char byte;

FILE *g = fopen(“eulerianpath.txt”,”w”);

byte ti[200], tf[200], father[200];

void READ_GRAPH()

{ File *f = fopen(“graph.txt”,”r”);

int i,j,k;

memset(A,false,sizeof(A));

fscanf(f,”%d%d”,&n,&m);

for(k=1;k≤m;k++)

{ fscanf(f,”%d%d”,&i,&j); A[i][j] = A[j][i] = true;

fclose(f);}

void DF()

{int time,i,j,node,top;

byte stack[200];bool marked[200];time=0;

for(i=1;i≤n;i++)

{ father[i]=0,marked[i]=false;}

for(i=1;i≤n;i++)

{ if(marked[i] == false)

{ node=i;marked[node] = true;ti[node] = ++time;top = 1,stack[top] = node;

while(top>0)

{for(j=1; ((j≤n)&&(A[node][j] == false || marked[j]));j++);

if(j≤n)

{father[j] = node;node = j;stack[++top]=node;marked[node] = true;ti[top]=++time;}

else{tf[node]=++time;node=stack[ — top];}

} } } }

void DF_EULER(int node)

{int i; fprintf(g,”%d ”,node);

for(i=1;i≤n;i++)

if(A[node][i] == true)

if((father[node] != i )&&(node!=father[i]))

{A[node][i] = A[i][node]=false;

DF_EULER(i); }

for(i=1;i≤n;i++)

if(A[node][i] == true)

{ A[node][i] = A[i][node] = false; DF_EULER(i);}

}

int main()

{READ_GRAPH();int i; DF_EULER(1);

fclose(g); return 0;}