Java Stack Solution (Hierholzer’s Algorithm)


  • 0

    Here's the details of finding Euler path using Hierholzer’s Algorithm. I implemented it in Java.

    The main steps are as follows.

    1. Start with an empty stack and an empty circuit (eulerian path).

      • If all vertices have same out-degrees as in-degrees - choose any of them.
      • If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - then choose the vertex that has its out-degree with one greater than its in-degree.
      • Otherwise no euler circuit or path exists.
    2. If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.

    3. Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.
      Note that obtained circuit will be in reverse order - from end vertex to start vertex.

    Code:

    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            Map<String, PriorityQueue<String>> map = new HashMap<>();
            LinkedList<String> route = new LinkedList<>();
            Stack<String> stack = new Stack<>();
            
            for (String[] t : tickets) {
                map.putIfAbsent(t[0], new PriorityQueue<>());
                map.putIfAbsent(t[1], new PriorityQueue<>()); //construct a queue for every node (even those without neighbors)
                map.get(t[0]).add(t[1]);
            }
            
            String cur = "JFK";
            while (map.get(cur).size() != 0 || !stack.isEmpty()){
                if (map.get(cur).size() == 0){
                    route.add(cur);
                    cur = stack.pop();
                } else {
                    stack.add(cur);
                    cur = map.get(cur).poll();
                }
            }
            route.add(cur);
            Collections.reverse(route);
            return route;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.