Teaching Kids Programming – Reconstruct the Flight Itinerary using Topological Sorting Graph Algorithm (DAG)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of flights that were taken, represented as origin to destination airport pairs. Given that this list was shuffled, find all the airports that were visited in the correct order. Note: you can assume that no airport was visited twice.

Constraints
n ≤ 100,000 where n is the length of flights
Example 1
Input

1 2 3 4 5

flights = [     ["WRE", "RPM"],     ["AGN", "WRE"],     ["NTL", "AGN"] ]

flights = [
    ["WRE", "RPM"],
    ["AGN", "WRE"],
    ["NTL", "AGN"]
]

Output

1	["NTL", "AGN", "WRE", "RPM"]

["NTL", "AGN", "WRE", "RPM"]

Explanation
The only way to have taken the 3 flights was to have taken “NTL” -> “AGN” first. After that, “AGN” -> “WRE”, and “WRE” -> “RPM” could be taken.
Can you relate this with topological sort?

Try finding the airport with indegree 0. That will be the starting point of the route.

Reconstruct the Flight Itinerary using Topological Sorting Graph Algorithm (DAG)

The shuffled flight tickets are a Graph representing the DAG (Directed Acyclic Graph) – meaning there is no cycles. We have to find out the start node/place, which has zero indegree. Then we can just follow the path.

As it is a simple Graph with no cycles, and no nodes of out degrees more than one (one path), we can just perform a simple Topological Sorting to the Graph.

To store the Graph in a dictionary, we can simply do this:

1

G = dict(flights)

G = dict(flights)

which is the same as:

1

G = {a: b for a, b in flights}

G = {a: b for a, b in flights}

To get the start – a quick way can be done via sets:

1
2
3

st = set(G) - set(G.values()) 
# same as 
# st = set(G.keys()) - set(G.values()) 

st = set(G) - set(G.values()) 
# same as 
# st = set(G.keys()) - set(G.values()) 

And then get the single element out of the set:

1

st = next(iter(st))

st = next(iter(st))

Also, this works too:

1

st = "".join(st)

st = "".join(st)

The full Graph Topological Sorting Algorithm to find out the route is:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def solve(self, flights):
        G = dict(flights)
        st = set(G) - set(G.values())
        st = next(iter(st))
        ans = [st]
        while st in G:
            st = G[st]
            ans.append(st)
        return ans

class Solution:
    def solve(self, flights):
        G = dict(flights)
        st = set(G) - set(G.values())
        st = next(iter(st))
        ans = [st]
        while st in G:
            st = G[st]
            ans.append(st)
        return ans

The time/space complexity is O(N) where N is the number of the airports (vertices in the Graph).

–EOF (The Ultimate Computing & Technology Blog) —