Leetcode 1971. Find if Path Exists in Graph [Python]

本文主要是介绍Leetcode 1971. Find if Path Exists in Graph [Python]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

BFS 从start遍历到end，每一次que弹出节点是end，返回true，否则，把此节点加入到seen set中，并入队。遍历完成后，未找到end节点，代表和start直接或间接相连的节点中没有end节点。返回false。注意特殊情况，只有一个节点时。

class Solution:
    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:
        if n == 1:return True
        dic = collections.defaultdict(set)
        for n,m in edges:
            dic[n].add(m)
            dic[m].add(n)
        que = collections.deque()
        que.append(start)
        seen = set()
        while que:
            size = len(que)
            for _ in range(size):
                curnode = que.popleft()
                for nextnode in dic[curnode]:
                    if nextnode == end:
                        return True
                    else:
                        if nextnode not in seen:
                            seen.add(nextnode)
                            que.append(nextnode)
        return False

这篇关于Leetcode 1971. Find if Path Exists in Graph [Python]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！