My python easy understood BFS solution


  • 3
    F

    My solution is based on a simple idea that from any vertices, use BFS to visit the graph, if encountered the vertice that just been visited, or when finished visiting, there are still nodes that has not been visited, then this graph is not a valid tree.
    There are two things that we need to pay attention:

    1. The input edges are meant for directed graph, so first we need to cover it to the input for undirected graph.
      2.User python's default dictionary to record vertices that has been visited, its a pretty convenient data structure for this problem.

      class Solution(object):
      def validTree(self, n, edges):
      """
      :type n: int
      :type edges: List[List[int]]
      :rtype: bool
      """
      dict={i:set() for i in range(n)} #cover directed graph input to undirected
      for i, j in edges:
      dict[i].add(j)
      dict[j].add(i)
      start=[dict.keys()[0]] #start from any vertices
      visited=collections.defaultdict(int) #record every visited vertices
      while start: # BFS
      node = start.pop(0)
      if visited[node]==1:
      return False
      visited[node]=1
      for i in dict[node]:
      start.append(i)
      dict[i].remove(node) #prevent going back to the previous vertices
      del dict[node]
      return not dict


  • 2
    C

    @fangkunjnsy , thanks for your very clear Python BFS solution! I rewrite your code a little bit:

    def validTree(self, n, edges):
        dic = {i: set() for i in xrange(n)}
        for i, j in edges:
            dic[i].add(j)
            dic[j].add(i)
        visited = set()
        queue = collections.deque([dic.keys()[0]])
        while queue:
            node = queue.popleft()
            if node in visited:
                return False
            visited.add(node)
            for neighbour in dic[node]:
                queue.append(neighbour)
                dic[neighbour].remove(node)
            dic.pop(node)
        return not dic

  • 0

    @caikehe Thanks for your rewriting!


Log in to reply
 

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