Hierholzer’s algorithm for undirected graph – Euler path and longest path

An Euler path  is a trail in a graph that visits every edge exactly once. Here we use graph data structure to simulate the set of linked porker cards and find the Euler path between them. In a porker game, if two poker cards have matched suites and figures, they can be link together. Given set of porker cards, we are going to link matched card as an Euler path and find the longest possible one. Each card can be seen as a node in a graph. The matched two cards have a bi-directional edge between them. So the graph is undirected. This post is to find Euler path with Hierholzer’s algorithm for undirected graph.

How Hierholzer’s algorithm works in undirected graph?

First build graph (as adjacency list) from the input data. To apply Hierholzer’s algorithm , (1) start from any vertex v and follow a trail of edges until returning to v. The tour formed a closed tour. (2) If there is a vertex u that belongs to the current tour, but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u. (3) keep following unused edges and removing them when we get stuck. When stuck, backtrack to the nearest vertex in the current path that has unused edges. Repeat the process until all the edges have been used. 

hierholzer algorithm

The set of cards will be the input to build an undirected graph as adjacency list. After building the graph, we start from the first key in adjacency list. The node’s degree is used to keep track the unvisited edges. A stack is to track the cards that have been visited. When the edge is visited, its degree will be decreased by 1. When the degree is 0, it is time to backtrack the card that is last visited and has unused edges. So that we bridge other links of the matched cards. Meanwhile the visited card popped from the stack will be saved in a doubly linked list, which link all possible matched cards. This double linked list is the result of one pass of Hierholzer run. It’s time complexity is O(E). E is the number of edges.

After we have solution to find Euler path with Hierholzer’s algorithm for undirected graph, we are asked to find the longest path from the first card. This is the extension of the problem. The answer is to add another layer of loop to have multiple Hierholzer runs. We iterate through all keys (all cards) in the adjacency list as the start node to run Hierholzer’s . The result is saved in a map. The key is the length of the matched cards in each Hierholzer run. The value is a linked list which maintains the linked matched cards with the same length. The map is sorted by key in descending order. The first key is the max number of the matched cards.


longest path of matched cards

Amazon Interview Question:
As we all know that poker cards have four suites: Spades, Hearts, Clubs and Diamonds with figures from 1 to 13.Now you are given a set of poker cards, you can pick any one card as the first card. And except for the first card, you can only pick the card that has the same suit or figure with the previous one.Return the max number of cards you can. For example: [(H, 3), (H, 4), (S, 4), (D, 5), (D, 1)], it returns 3 as follows: (H,3)–>(H,4)–>(S,4)

Java

JavaScript

Python

Output:
(H, 3), (H, 4), (S, 4), (D, 1), (D, 5)
Max number of cards: 3
Links: (H, 3), (H, 4), (S, 4), (D, 1), (D, 5), (H, 1)
Max number of cards: 6

Please note the test case2. Sometimes when a new card is added, it makes two linked lists merge as one. For example, we have the first linked list of (H,3), (H,4), (S,4), and the second linked list (D,1), (D5). When adding new card (H,1), it connect two linked lists to be one (D,5), (D,1), (H,1), (H,3), (H,4), (S,4).

O Notation:
Time complexity: O(E*V)
Space complexity: O(E+V)
V is total number of cards, E is number of matched cards


Download LongestPathOfMatchedCards.java
Download LongestPathOfMatchedCards.js
Download LongestPathOfMatchedCards.py

Comments are closed