Рекурсивный обход графа
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
G[a].append(b)
G[b].append(a)
used = [0] * n
R = []
def dfs(h):
used[h] = 1
R.append(h + 1)
for a in G[h]:
if used[a] == 0:
dfs(a)
if n > 0:
dfs(0)
print(*R)#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> G;
vector<int> used;
vector<int> R;
void dfs(int h) {
used[h] = 1;
R.push_back(h + 1);
for (auto a : G[h]) {
if (!used[a]) {
dfs(a);
}
}
}
int main() {
cin >> n >> m;
G.resize(n);
used.assign(n, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--; b--;
G[a].push_back(b);
G[b].push_back(a);
}
if (n > 0) {
dfs(0);
}
for (int i = 0; i < R.size(); i++) {
cout << R[i] << " ";
}
return 0;
}DFS (Depth-First Search / поиск в глубину) — алгоритм обхода графа, который идёт "вглубь" от стартовой вершины, пока не упрётся в тупик, затем возвращается назад и продолжает с непосещёнными соседями.
Алгоритм использует стек (явный или рекурсию):
Рекурсивная реализация естественно выражает этот процесс: сначала рекурсивно обрабатываем первого соседа, затем следующего и т.д.
Важные особенности:
Временная сложность: O(n + m), где n — количество вершин, m — количество рёбер.
Ввод:
n m — количество вершин и количество рёберa b — ребро между вершинами a и b (повторяется m раз)Вывод:
4 4
1 2
2 3
3 4
1 4Здесь:
n=4 (вершины 1,2,3,4)
m=4 (4 ребра)
Ребра: 1-2, 2-3, 3-4, 1-4
Вывод (порядок обхода из 1):
1 → 2 → 3 → 4 (или 1 → 4 → ... в зависимости от порядка соседей)
Введите граф в формате, описанном выше: