## Sunday, November 26, 2006

### [TECH] Algorithm to find euler circuit in a graph in O(|E|)

Important observation I found is that, if we delete a cycle (delete all the edges which form a cycle) from the graph which has a Euler circuit, the property of the graph still remains, i.e the necessary and sufficient condition for the graph to have a Euler cycle is that every vertex should have even degree. And also there has to be a cycle at every vertex.

INPUT: G =(E,V)
v = v
euler_cycle = NULL;
while(|E| > 0){
/*Find a cycle in G, start
the search at v, returns c0 around
which cycle is formed*/
c0 = FIND_CYCLE(G,v);
v = GET_NON_ZERO_DEGREE_VERTEX(c0);
/*Above can be done in constant time,
using some space while finding the cycle
*/
MERGE(c0,euler_cyle);
/*constant time operation,
put c0 after an edge e1 in
euler cycle which ends at
vertex 'v', we can just remember
the position of v n euler_cycle
every time we merge*/

}