BFS روی گراف
Graph Breadth-First SearchBFS گراف را level-by-level با Queue پیمایش می‌کند و در گراف بدون وزن shortest path از نظر تعداد edge را پیدا می‌کند.
اول این مفهوم را در ذهن نگه دار
BFS گراف را level-by-level با Queue پیمایش می‌کند و در گراف بدون وزن shortest path از نظر تعداد edge را پیدا می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
Node شروع را enqueue و visited می‌کنیم.
هر بار یک Node dequeue می‌شود و neighborهای دیده‌نشده enqueue می‌شوند.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای BFS روی گراف هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function bfs(graph, start) {
const seen = new Set([start]);
const queue = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head++];
for (const next of graph[node] ?? []) {
if (!seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
return seen;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(V+E)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
Queue فقط جزئیات پیاده‌سازی نیست؛ همین Queue ترتیب levelها را می‌سازد و دلیل درست بودن shortest path بدون وزن است.
BFS روی گراف چه مسئله‌ای را حل می‌کند؟
BFS گراف را level-by-level با Queue پیمایش می‌کند و در گراف بدون وزن shortest path از نظر تعداد edge را پیدا می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(V+E) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.