Python graph + dfs search


  • 0
    S
    from collections import defaultdict
    
    class Solution(object):
    
        def calcEquation(self, equations, values, queries):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type queries: List[List[str]]
            :rtype: List[float]
            """
            # adjacency list graph G, G[v1] --> [(v2, w12), (v3, w13)...]
            # where w12 is the weight for a directed edge v1->v2, where v1 / v2 = w12
            G = defaultdict(list)
            for (v1, v2), val in zip(equations, values):
                # v1 / v2 = val
                G[v1].append((v2, val))
                G[v2].append((v1, 1 / val))
    
            # for each query v1 / v2, check whether there is a path from v1 to v2
            # if so, the result of v1 / v2 is given by the accumulated product of 
            # all weights on the path
            results = []
            for v1, v2 in queries:
                if v1 in G and v2 in G:
                    results.append(self.check_path(G, v1, v2))
                else:   # if either of v1 and v2 doesn't exist in the graph
                    results.append(-1.0)
            return results
    
        def check_path(self, G, v1, v2):
            visited = set()
            weight_path = []
    
            def backtrack(v):   # dfs with backtracking to find a path v --> v2
                if v == v2:
                    return True
                for x, w in G[v]:
                    if x not in visited:
                        visited.add(x)
                        weight_path.append(w)
                        if backtrack(x):
                            return True
                        del weight_path[-1]  # elimination to restore the original path
                return False
    
            if backtrack(v1):
                r = 1.0
                for w in weight_path:
                    r *= w
                return r
            return -1.0

Log in to reply
 

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