題目出處
難度
medium
個人範例程式碼
from typing import (
List,
)
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
# write your code here
if len(edges) != n-1:
return False # not completed graph
graph = self.build_graph(edges)
return self.bfs(graph, n)
def bfs(self, graph, n):
visited = {0}
queue = [0]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
return len(visited) == n
def build_graph(self, edges):
graph = collections.defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
return graph
算法說明
這題的存在，直接地告訴了我們 graph 與 tree 的差別，
簡單來說，tree 就等於「沒有環的 graph」，
我們使用 bfs 來幫助我們搜尋，看是否全部搜尋完全即可。
注意：這題題目中有提示我們，我們可以從 0 做為起點開始搜尋。
input handling
因為 n 的點至少需要有 n-1 條邊，且我們「tree 又必定沒有環」，
因此我們可以先判斷 len(edges) 是否等於 n-1，沒有可以直接 return False
Boundary conditions
用 while queue 搭配做出 bfs，把全部可找到的點都加入 visited 後，
比較 len(visited) 是否等於 n，作為我們最後的答案。