Python topological sort w/o BFS/GFS


  • 6
    Z

    We do not need a DFS or BFS to detect if there is a cycle, because if the graph stop shrinking before all nodes are removed, it indicates that solution doesn't exist (a cycle in the graph)

    class Node(object):
    def __init__(self):
        self.IN = set()
        self.OUT = set()
    
    class Solution(object):
    def alienOrder(self, words):
       # find out nodes
       graph = {}
        for word in words:
            for letter in word:
                if letter not in graph:
                    graph[letter] = Node()
    
        # find out directed edges (from StefanPochmann)
        for pair in zip(words, words[1:]):
            for a, b in zip(*pair):
                if a != b:
                    graph[a].OUT.add(b)
                    graph[b].IN.add(a)
                    break
    
        # topo-sort
        res = ""
        while graph:
            oldlen = len(graph)
    
            for key in graph:
                if not graph[key].IN:   # to remove this
                    for key2 in graph[key].OUT:
                        graph[key2].IN.remove(key)
                    del graph[key]
                    res += key
                    break
    
            if oldlen == len(graph): # if shrinking stops, solution doesn't exist
                return ""
            oldlen = len(graph)
        return res

  • 1
    Z

    Just revisited and had cleaner code

    class Node(object):
    def __init__(self):
        self.IN = set()
        self.OUT = set()
    
    class Solution(object):
    def alienOrder(self, words):
        # initialization
        allnodes, graph, res = set("".join(words)), {}, ""
        for i in allnodes:
            graph[i] = Node()
        
        # build the graph
        for i in range(len(words)-1):
            for j in zip(words[i], words[i+1]):
                if j[0] != j[1]:
                    graph[j[0]].OUT.add(j[1])
                    graph[j[1]].IN.add(j[0])
                    break
    
        # topo-sort
        while allnodes:
            buff = set([i for i in allnodes if graph[i].OUT and not graph[i].IN])
            if not buff:
                return res + "".join(allnodes) if not [i for i in allnodes if graph[i].IN] else "" # have solution if no connected node
            res += "".join(buff)
            allnodes -= buff
            for i in allnodes:
                graph[i].IN -= buff
        return res

Log in to reply
 

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