Python BFS Solution


  • 0

    Not only DFS, but also BFS does the job.

    class GraphNode:
        def __init__(self, value):
            self.val = value
            self.neighbors = []
            
    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]
            """
            h = {}
            for i in range(len(equations)):
                (x, y), k = equations[i], values[i]
                if x not in h:
                    h[x] = GraphNode(x)
                if y not in h:
                    h[y] = GraphNode(y)
                h[x].neighbors.append((y, k))
                h[y].neighbors.append((x, 1.0/k))
            ans = []
            for x, y in queries:
                visit = set()
                if not x in h or not y in h:
                    ans.append(-1.0)
                else:
                    queue = [(x,1.0)]
                    found = False
                    while queue:
                        print queue
                        for x,v in queue:
                            visit.add(x)
                            if x == y:
                                ans.append(v)
                                found = True
                                break
                        if found:
                            break
                        new_queue = []
                        for x,v in queue:
                            for a,b in h[x].neighbors:
                                if a not in visit:
                                    new_queue.append((a,b*v))
                        queue = new_queue
                    if not found:
                        ans.append(-1.0)
            return ans

Log in to reply
 

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