0_1 BFS
می دانیم دو نوع گراف وزن دار و بدون وزن داریم که برای پیدا کردن کوتاه ترین مسیر از راس مشخص $s$ به بقیه رئوس باید در هرکدام به صورت متفاوتی عمل کرد . به عنوان مثال در گراف های وزن دار بدون دور منفی می توانیم این مسیر را با استفاده از دایکسترا در $Order(n^2 + m)$ یا در $Order(mlog(m))$ پیدا کنیم ، یا در گراف های بدون وزن می توانیم از BFS استفاده کنیم .
در این مقاله می خواهیم یادبگیریم چگونه از $BFS$ برای پیدا کردن کوتاه ترین مسیر از راس مشخص $s$ به بقیه رئوس در گرافی که وزن تمام یال های آن یا صفر است یا یک استفاده کنیم .
الگوریتم
بیایید با دایکسترا شروع کنیم و ببینیم که اگر گراف مخصوص (گراف با یال ۰ یا ۱) به آن بدهیم چه اتفاقی می افتد . این قسمتی از کد دایکسترا با استفاده از $Set$ است :
d.assign(n, INF);
d[s] = 0;
set<pair<int, int>> st;
st.insert({0, s});
while (!st.empty())
{
int v = st.begin()->second;
st.erase(st.begin());
for (auto edge : adj[v])
{
int u = edge.first;
int w = edge.second;
if (d[v] + w < d[u])
{
st.erase({d[u], u});
d[u] = d[v] + w;
st.insert({d[u], u});
}
}
}
با کمی دقت متوجه می شویم که اختلاف فاصله بین راس $s$ با راسی که تازه به $Set$ اضافه می شود ، در هر مرحله حداکثر یک واحد تغییر می کند ، به خصوص که می دانیم : $d[v] <= d[u] <= d[v] + 1$ زیرا در هر مرحله ما راسی را به $Set$ اضافه می کنیم که فاصله اش یا مساوی است یا یدونه زیادتر می شود . حال بیایید یک پیاده سازی بهتر برای گراف مخصوص خود داشته باشیم . برای این پیاده سازی از $deque$ استفاده می کنیم . این $Data Structure$ هم مانند $queue$ است با این تفاوت که دوسر آن باز است و می توان از دو طرف آن عضوی را برداشت یا به آن اضافه کرد . اگر یال $v$ به $u$ مساوی صفر بود آنگاه آن را از سمت چپ $queue$ که همان $Front$ است ، $push$ می کنیم . چون صفرها باید تقدم بیشتری داشته باشند و زودتر برداشته شوند . و اگر این یال مساوی ۱ باشد و داشته باشیم : $d[u] = d[v] + 1$ آنگاه باید این راس را از سمت راست که همان $back$ است ، $push$ کنیم .
پیاده سازی
vector<int> d(n, INF);
d[s] = 0;
deque<int> dq;
dq.push_front(s);
while (!dq.empty())
{
int v = dq.front();
dq.pop_front();
for (auto edge : adj[v])
{
int u = edge.first;
int w = edge.second;
if (d[v] + w < d[u])
{
d[u] = d[v] + w;
if (w == 1)
dq.push_back(u);
else
dq.push_front(u);
}
}
}