# My python easy understood BFS solution

• 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:
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

• @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:
visited = set()
queue = collections.deque([dic.keys()[0]])
while queue:
node = queue.popleft()
if node in visited:
return False