Grade 11 · Undirected graphsCitește în română

Depth-first search (DFS)

Original: Parcurgerea în adâncime (DFS)

O(n²)C++1761 lines1 example

The idea

Depth-first search goes as far as it can: from the current node it moves to the first unvisited neighbour, from there to that node's first unvisited neighbour, and so on; when a node has no unvisited neighbours left, it returns to the node it came from. Going back happens naturally through recursion (the call stack). Neighbours are taken in increasing order. Input: n m, the m edges, then the start node.

Original description (Romanian)

Parcurgerea în adâncime merge cât de departe se poate: din nodul curent trece în primul vecin nevizitat, de acolo în primul vecin nevizitat al acestuia și așa mai departe; când un nod nu mai are vecini nevizitați, se întoarce la nodul din care a venit. Revenirea se face natural prin recursivitate (stiva de apeluri). Vecinii se iau în ordine crescătoare. Datele: n m, cele m muchii, apoi nodul de start.

Complexity
O(n²) with the adjacency matrix (O(n + m) with adjacency lists)
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

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

Expected output

5 2 1 3 4 6 7

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

parcurgerea-in-adancime-dfs.cpp
/*
 * Titlu: Parcurgerea în adâncime (DFS)
 * Clasa: 11
 * Capitol: Grafuri neorientate
 * Descriere: Parcurgerea în adâncime merge cât de departe se poate: din nodul curent trece
 *            în primul vecin nevizitat, de acolo în primul vecin nevizitat al acestuia și
 *            așa mai departe; când un nod nu mai are vecini nevizitați, se întoarce la nodul
 *            din care a venit. Revenirea se face natural prin recursivitate (stiva de
 *            apeluri). Vecinii se iau în ordine crescătoare. Datele: n m, cele m muchii,
 *            apoi nodul de start.
 * Complexitate: O(n²) cu matricea de adiacență (O(n + m) cu liste de adiacență)
 *
 * Exemplu
 * Intrare:
 * 7 8
 * 1 2
 * 1 3
 * 2 4
 * 2 5
 * 3 5
 * 4 6
 * 5 6
 * 6 7
 * 5
 * Ieșire: 5 2 1 3 4 6 7
 */
#include <iostream>
using namespace std;

int n, m, a[105][105];
bool vizitat[105];

void dfs(int x)
{
    vizitat[x] = true;
    cout << x << ' ';
    for (int y = 1; y <= n; y++)
    {
        if (a[x][y] == 1 && !vizitat[y])
        {
            dfs(y);
        }
    }
}

int main()
{
    int start;
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    cin >> start;
    dfs(start);
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.