Edge-ээр холбогдсон node-уудыг BFS (Queue) ба DFS (recursion) гэсэн хоёр өөр дарааллаар тойрч гардаг арга.

IntermediateХугацаа: O(n + m)Санах ой: O(n + m)
HackerRank дээр бодох

Эхлээд жижиг бодлого

4 node, 3 edge: 1-2, 1-3, 2-4. Node 1-ээс эхэлье.

BFS эхлээд 1-ийн хөршүүд 2, 3-ыг, дараа нь 2-ын хөрш 4-ийг үзнэ: 1 2 3 4. DFS 1-ээс 2 руу, тэндээсээ шууд 4 руу гүн орно. Дараа нь буцаж 3 руу явна: 1 2 4 3.

Энгийн аргаас санаа руу

Graph-ыг n × n хүснэгтээр хадгалбал хөршүүдийг олохын тулд мөр бүрийг бүтэн гүйнэ. n = 100 000 бол хүснэгт 10 тэрбум нүдтэй болж санах ойд багтахгүй.

Тиймээс node бүрийн хөршүүдийг жагсаалтаар (vector<int> g[]) хадгална. BFS Queue ашиглаж ойроос нь хол руу, DFS recursion ашиглаж гүн рүүгээ явна. Хоёулаа vis ашиглан node бүрт нэг л удаа орно.

Нэр томьёо ба тэмдэглэгээ

g[u]
u-гийн хөршүүдийн жагсаалт (adjacency list).
vis[v]
v-д аль хэдийн очсон эсэх.
BFS
Queue ашиглан ойрын node-уудыг түрүүлж үздэг хайлт.
DFS
Recursion ашиглан нэг зам руу аль болох гүн ордог хайлт.
n, m
Node-ын тоо ба edge-ийн тоо.
1234567
q (Queue)
хоосон
хэвлэсэн
хоосон

Эхлэх node нь 1. BFS эхлээд ойрын хөршүүдээ, дараа нь тэдний хөршүүдийг үзнэ. Хөршүүдийг жижиг дугаараас нь эхэлж шалгана.

Алхам 1 / 32
Хурд
  • Одоогийн node / шалгаж буй edge
  • Шинээр олдсон
  • Тэмдэгтэй, дуусаагүй
  • Дууссан node / ашигласан edge
  • Хүрэхгүй
Слайд 1 / 7

Graph гэж юу вэ?

Дугуйнууд нь node, тэднийг холбосон шугам нь edge. Хотууд ба замууд, найзууд ба тэдний найрамдал бүгд graph болно.

graph-bfs-dfs.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> g[105];
bool vis[105];
queue<int> q;
void bfs(int s) {
vis[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << ' ';
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
void dfs(int u) {
vis[u] = true;
cout << u << ' ';
for (int v : g[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
bfs(1);
cout << '\n';
memset(vis, 0, sizeof vis);
dfs(1);
cout << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Graph-ын бүх node-д очиж, хүрч болох эсэхийг шалгана. Хамгийн богино зам, connected component, tree зэрэг олон graph бодлого үүнээс эхэлдэг.

Яаж ажилладаг вэ?

1. Edge бүрийг хоёр тал руу нь g жагсаалтад нэмээд, хөршүүдийг өсөх дарааллаар эрэмбэлнэ. 2. BFS: эхлэх node-ыг тэмдэглээд Queue-д хийнэ. Queue-гийн эхнээс node гаргаж хэвлээд, очоогүй хөршүүдийг нь тэмдэглэж Queue-гийн ард нэмнэ. 3. DFS: dfs(u) нь u-г тэмдэглээд хэвлэнэ. Дараа нь очоогүй хөрш бүр дээр dfs-ийг дуудна. 4. Хоёулаа node бүрт нэг л удаа очно. BFS ойроос нь хол руу, DFS гүн рүүгээ явна. Оролт: эхний мөрөнд n ба m, дараа нь m мөрөнд edge «u v». Гаралт: эхний мөрөнд BFS, дараагийн мөрөнд DFS дараалал. Хоёулаа node 1-ээс эхэлнэ.

Яагаад зөв, хэр хурдан бэ?

Хоёр хайлт хоёулаа node-ыг зөвхөн vis нь false үед нээдэг тул node бүрийг нэг л удаа хэвлэнэ. Node 1-ээс зам бүхий node бүрт хүрнэ: зам дээрх node нээгдсэн бол түүний бүх хөршийг шалгадаг тул дараагийнх нь ч нээгдэнэ.

Node бүр нэг удаа, edge бүр хоёр тал руугаа хоёр удаа шалгагдана: хугацаа O(n + m). n = 100 000, m = 200 000 бол 500 000 орчим үйлдэл. Хөршүүдийг эрэмбэлэхэд нэмж O(m log m) зарцуулна.

Түгээмэл алдаа

  • BFS-д node-ыг Queue-гээс гаргах үед тэмдэглэх. Нэг node Queue-д хэд хэдэн удаа орно. Queue-д хийх үед нь тэмдэглэ.
  • Чиглэлгүй graph-д edge-ийг зөвхөн нэг тал руу нь нэмэх. g[u].push_back(v) ба g[v].push_back(u) хоёулаа хэрэгтэй.
  • BFS-ийн дараа DFS хийхийн өмнө vis-ийг цэвэрлэхээ мартах. Кодонд memset(vis, 0, sizeof vis) гэж бичсэн.
  • Хөршүүдийг эрэмбэлэхгүй орхих. Хайлт зөв хэвээр ч гаралтын дараалал өөр гарна.

Хязгаарын тохиолдол

  • Edge огт байхгүй: хоёр мөрөнд хоёуланд нь зөвхөн 1 хэвлэгдэнэ.
  • Graph хэд хэдэн хэсэгтэй: node 1-ийн хэсэгт ороогүй node-ууд хэвлэгдэхгүй.
  • Graph-д cycle байвал vis-ийн ачаар дахин орохгүй, хайлт дуусна.

Өөрийгөө шалга

  1. 1-2, 2-3, 3-4, 4-1 гэсэн cycle дээр BFS, DFS ямар дараалал гаргах вэ?

    Хариу харах

    BFS: 1 2 4 3. DFS: 1 2 3 4.

  2. 1-2, 1-3, 2-4, 3-5 tree дээр DFS ямар дараалал гаргах вэ?

    Хариу харах

    1 2 4 3 5. 2-оос 4 рүү гүн ороод, буцаж 3 руу явна.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Animation-ы жишээ graph дээр BFS-ийн Queue алхам бүрт ямар байхыг бич.

    Hint харах

    Node 1-ийн хөршүүд 2, 3. Node 2-ын шинэ хөрш 6.

    Хариу ба тайлбар

    1 → 2 3 → 3 6 → 6 5 → 5 4 → 4 7 → 7 → хоосон. Хэвлэгдэх нь 1 2 3 6 5 4 7.

  2. 2.BFS ашиглан node 1-ээс node бүр хүртэлх хамгийн цөөн edge-ийн тоог ол.

    Hint харах

    vis-ийн оронд dist[v] = -1 ашигла.

    Хариу ба тайлбар

    dist[1] = 0. Шинэ хөрш олдох бүрт dist[v] = dist[u] + 1. Жишээ graph дээр 2, 3 нь 1; 5, 6 нь 2; 4, 7 нь 3.

  3. 3.Graph-д хэдэн connected component байгааг тоол.

    Hint харах

    Node бүрийг гүйж, очоогүй node олдох бүрт шинэ хайлт эхлүүл.

    Хариу ба тайлбар

    for (int i = 1; i <= n; i++) if (!vis[i]) { comps++; dfs(i); }. Хугацаа O(n + m).

Жишээ

Оролт

7 8
1 2
1 3
2 3
2 6
3 5
3 6
4 6
5 7

Гаралт

1 2 3 6 5 4 7
1 2 3 5 7 6 4

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.