مثال تابع در پایتون: def bfs(graph, start):
مثال 4 از درس جلسهی 35 دورهی حرفهای پایتون (۱۵ سال به بالا): درهمسازی و گرافها
جستوجوی سطحاول (BFS) از مبدأ لایهبهلایه پیش میرود: اول همهی گرههای با فاصلهی ۱، بعد ۲ و... پس در گراف بدون وزن، اولین باری که به گرهای میرسیم کوتاهترین فاصله را داریم. صف (deque) + dist (که نقش visited را هم دارد)؛ زمان O(V + E).
from collections import deque
def bfs(graph, start):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
این کد را همینجا در ویرایشگر پایتون اجرا کن، عددها و متنهایش را عوض کن و دوباره اجرا کن تا ببینی چه تغییری میکند.
بیشتر بخوان: تابع در پایتون: آموزش def، پارامتر و return با مثال
← مثال قبلی · برگشت به درس جلسهی 35: درهمسازی و گرافها · مثال بعدی → · چالشهای این جلسه