Eulerian Path and Eulerian Circuit - Fleury's Algorithm

Definition

Definition

Fleury's Algorithm is a method for finding Eulerian paths and circuits in a graph. It's particularly useful when dealing with graphs that have a mix of even and odd degree vertices

Explanation

Select any vertex within the graph. Proceed by examining the number of edges connected to the current vertex. If only one edge exists, follow that edge. However, if multiple edges are present, prioritize selecting an edge that maintains graph connectivity; otherwise, any edge can be chosen. Once an edge is selected, mark it as visited and remove it from the graph. Transition to the vertex at the opposite end of the chosen edge. Continue this process of edge selection, traversal, and removal until no edges remain unexplored in the graph

Guidance

• Choose a starting vertex
• If the starting vertex has an odd degree, choose another starting vertex with an odd degree if one exists; otherwise, start with any vertex
• While there are unexplored edges
  • if the current vertex has only one unexplored edge, follow that edge
  • if the current vertex has multiple unexplored edges
    • choose an edge that doesn't disconnect the graph if possible
    • if all edges disconnect the graph, choose any edge
  • mark the chosen edge as visited and remove it from the graph
  • move to the other end of the chosen edge
• Stop when all edges are explored

Tips

• keep track of the degrees of vertices to efficiently choose the next edge
• use graph traversal techniques such as depth-first search (DFS) or breadth-first search (BFS) to implement Fleury's Algorithm

Practice

Practice

fleury(graph):
  initialize empty list path
  current_vertex = any_vertex_with_odd_degree(graph) or any_vertex(graph)
  while graph has edges:
    if current_vertex has unvisited edges:
      next_vertex = choose_edge(current_vertex, graph)
      remove_edge(current_vertex, next_vertex, graph)
      add current_vertex to path
      current_vertex = next_vertex
    else:
      add current_vertex to path
      break
  return path

choose_edge(vertex, graph):
  for each adjacent_vertex of vertex:
    if removing_edge(vertex, adjacent_vertex, graph) does not disconnect graph:
      return adjacent_vertex
  return any adjacent_vertex

removing_edge(vertex1, vertex2, graph):
  remove edge between vertex1 and vertex2 from graph temporarily
  check if graph is still connected
  restore edge between vertex1 and vertex2 in graph
  return true if graph is still connected, false otherwise

any_vertex_with_odd_degree(graph):
  for each vertex in graph:
    if degree of vertex is odd:
      return vertex
  return null

Solution

package main

type Graph map[int][]int

func fleurysAlgorithm(graph Graph) []int {
	var circuit []int
	oddVertices := findOddVertices(graph)

	startVertex := 0
	if len(oddVertices) > 0 {
		startVertex = oddVertices[0]
	}

	DFS(graph, startVertex, &circuit)

	return circuit
}

func DFS(graph Graph, vertex int, circuit *[]int) {
	for len(graph[vertex]) > 0 {
		nextVertex := graph[vertex][0]
		removeEdge(graph, vertex, nextVertex)
		DFS(graph, nextVertex, circuit)
	}
	*circuit = append(*circuit, vertex)
}

func removeEdge(graph Graph, u, v int) {
	for i, w := range graph[u] {
		if w == v {
			graph[u] = append(graph[u][:i], graph[u][i+1:]...)
			break
		}
	}
	for i, w := range graph[v] {
		if w == u {
			graph[v] = append(graph[v][:i], graph[v][i+1:]...)
			break
		}
	}
}

func findOddVertices(graph Graph) []int {
	oddVertices := make([]int, 0)
	for v, neighbors := range graph {
		if len(neighbors)%2 != 0 {
			oddVertices = append(oddVertices, v)
		}
	}
	return oddVertices
}

import java.util.*;

public class FleuryAlgorithm {

  public static List<Integer> fleurysAlgorithm(Map<Integer, List<Integer>> graph) {
    List<Integer> circuit = new ArrayList<>();
    List<Integer> oddVertices = findOddVertices(graph);

    int startVertex = 0;
    if (!oddVertices.isEmpty()) {
      startVertex = oddVertices.get(0);
    }

    DFS(graph, startVertex, circuit);

    return circuit;
  }

  public static void DFS(Map<Integer, List<Integer>> graph, int vertex, List<Integer> circuit) {
    while (!graph.get(vertex).isEmpty()) {
      int nextVertex = graph.get(vertex).get(0);
      removeEdge(graph, vertex, nextVertex);
      DFS(graph, nextVertex, circuit);
    }
    circuit.add(vertex);
  }

  public static void removeEdge(Map<Integer, List<Integer>> graph, int u, int v) {
    graph.get(u).remove(Integer.valueOf(v));
    graph.get(v).remove(Integer.valueOf(u));
  }

  public static List<Integer> findOddVertices(Map<Integer, List<Integer>> graph) {
    List<Integer> oddVertices = new ArrayList<>();
    for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
      if (entry.getValue().size() % 2 != 0) {
        oddVertices.add(entry.getKey());
      }
    }
    return oddVertices;
  }
}

function fleurysAlgorithm(graph) {
  let circuit = [];
  let oddVertices = findOddVertices(graph);

  let startVertex = 0;
  if (oddVertices.length > 0) {
    startVertex = oddVertices[0];
  }

  DFS(graph, startVertex, circuit);

  return circuit;
}

function DFS(graph, vertex, circuit) {
  while (graph[vertex].length > 0) {
    let nextVertex = graph[vertex][0];
    removeEdge(graph, vertex, nextVertex);
    DFS(graph, nextVertex, circuit);
  }
  circuit.push(vertex);
}

function removeEdge(graph, u, v) {
  graph[u] = graph[u].filter((item) => item !== v);
  graph[v] = graph[v].filter((item) => item !== u);
}

function findOddVertices(graph) {
  let oddVertices = [];
  for (let vertex in graph) {
    if (graph[vertex].length % 2 !== 0) {
      oddVertices.push(parseInt(vertex));
    }
  }
  return oddVertices;
}

fun fleurysAlgorithm(graph: MutableMap<Int, MutableList<Int>>): List<Int> {
    val circuit = mutableListOf<Int>()
    val oddVertices = findOddVertices(graph)

    var startVertex = 0
    if (oddVertices.isNotEmpty()) {
        startVertex = oddVertices[0]
    }

    DFS(graph, startVertex, circuit)

    return circuit
}

fun DFS(graph: MutableMap<Int, MutableList<Int>>, vertex: Int, circuit: MutableList<Int>) {
    while (graph[vertex]!!.isNotEmpty()) {
        val nextVertex = graph[vertex]!!.removeAt(0)
        removeEdge(graph, vertex, nextVertex)
        DFS(graph, nextVertex, circuit)
    }
    circuit.add(vertex)
}

fun removeEdge(graph: MutableMap<Int, MutableList<Int>>, u: Int, v: Int) {
    graph[u]!!.remove(v)
    graph[v]!!.remove(u)
}

fun findOddVertices(graph: Map<Int, List<Int>>): List<Int> {
    val oddVertices = mutableListOf<Int>()
    for ((vertex, neighbors) in graph) {
        if (neighbors.size % 2 != 0) {
            oddVertices.add(vertex)
        }
    }
    return oddVertices
}

def fleurys_algorithm(graph):
    circuit = []
    odd_vertices = find_odd_vertices(graph)

    start_vertex = 0
    if odd_vertices:
        start_vertex = odd_vertices[0]

    DFS(graph, start_vertex, circuit)

    return circuit

def DFS(graph, vertex, circuit):
    while graph[vertex]:
        next_vertex = graph[vertex].pop(0)
        remove_edge(graph, vertex, next_vertex)
        DFS(graph, next_vertex, circuit)
    circuit.append(vertex)

def remove_edge(graph, u, v):
    graph[u].remove(v)
    graph[v].remove(u)

def find_odd_vertices(graph):
    odd_vertices = []
    for vertex in graph:
        if len(graph[vertex]) % 2 != 0:
            odd_vertices.append(vertex)
    return odd_vertices

use std::collections::HashMap;

fn fleurys_algorithm(graph: &mut HashMap<i32, Vec<i32>>) -> Vec<i32> {
    let mut circuit = Vec::new();
    let odd_vertices = find_odd_vertices(graph);

    let mut start_vertex = 0;
    if !odd_vertices.is_empty() {
        start_vertex = odd_vertices[0];
    }

    DFS(graph, start_vertex, &mut circuit);

    circuit
}

fn dfs(graph: &mut HashMap<i32, Vec<i32>>, vertex: i32, circuit: &mut Vec<i32>) {
    while !graph[&vertex].is_empty() {
        let next_vertex = graph.get_mut(&vertex).unwrap().remove(0);
        remove_edge(graph, vertex, next_vertex);
        dfs(graph, next_vertex, circuit);
    }
    circuit.push(vertex);
}

fn remove_edge(graph: &mut HashMap<i32, Vec<i32>>, u: i32, v: i32) {
    graph.get_mut(&u).unwrap().retain(|&x| x != v);
    graph.get_mut(&v).unwrap().retain(|&x| x != u);
}

fn find_odd_vertices(graph: &HashMap<i32, Vec<i32>>) -> Vec<i32> {
    let mut odd_vertices = Vec::new();
    for (vertex, neighbors) in graph {
        if neighbors.len() % 2 != 0 {
            odd_vertices.push(*vertex);
        }
    }
    odd_vertices
}

function fleurysAlgorithm(graph: Map<number, number[]>): number[] {
  const circuit: number[] = [];
  const oddVertices = findOddVertices(graph);

  let startVertex = 0;
  if (oddVertices.length > 0) {
    startVertex = oddVertices[0];
  }

  DFS(graph, startVertex, circuit);

  return circuit;
}

function DFS(graph: Map<number, number[]>, vertex: number, circuit: number[]) {
  while (graph.get(vertex)?.length) {
    const nextVertex = graph.get(vertex)!.shift()!;
    removeEdge(graph, vertex, nextVertex);
    DFS(graph, nextVertex, circuit);
  }
  circuit.push(vertex);
}

function removeEdge(graph: Map<number, number[]>, u: number, v: number) {
  graph.set(u, graph.get(u)?.filter((item) => item !== v)!);
  graph.set(v, graph.get(v)?.filter((item) => item !== u)!);
}

function findOddVertices(graph: Map<number, number[]>): number[] {
  const oddVertices: number[] = [];
  for (let [vertex, neighbors] of graph) {
    if (neighbors.length % 2 !== 0) {
      oddVertices.push(vertex);
    }
  }
  return oddVertices;
}