بتل کد Battle Codeدارد باز می‌شود…

مثال تابع در پایتون: 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: درهم‌سازی و گراف‌ها · مثال بعدی → · چالش‌های این جلسه