Python DFS in directed graph


  • 1
    C

    Build a graph then traversal using DFS

    class Solution(object):    
        def calcEquation(self, equations, values, queries):
            # Build the directicted graph with adjacency list and weight matrix.
            Adj = defaultdict(list)
            weights = {}  # Sparse matrix representation
            for (t, s), v in zip(equations, values):
                Adj[s] += t,
                Adj[t] += s,
                weights[(s, t)] = v
                weights[(t, s)] = 1. / v
    
            def DFS_visit(u, t, product=1., visited=set()):
                if u == t and Adj[u]:  # u in Adj is insufficient, since Adj is a defualtdict.
                    return product
                    
                visited.add(u)
                p = None
                for v in Adj[u]:
                    if v not in visited:
                        p = DFS_visit(v, t, product * weights[(u, v)], visited)
                    
                    # If any search reaches t, then we are done. Otherwise, try others.
                    if p:
                        break
                visited.remove(u)
                return p
    
            result = []
            for t, s in queries:
                result += DFS_visit(s, t) or -1,
                    
            return result     
    

Log in to reply
 

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