A „bejárás” azt jelenti, hogy felsoroljuk a pontokat valamilyen előre megadott szabály / sorrend szerint.

Szélességi bejárás

• angolul Breadth First Search, románul parcurgere în lățime
• Adott kiindulópontból kezdünk, melyet kezdetben egy várakozási sorba (queue) teszünk.
• Minden lépésben „meglátogatjuk” a sor elején levő elemet: kivesszük őt a sorból és betesszük a sor végére a szomszédait.
• Az algoritmus megáll, ha elfogytak az elemek a sorból.

Példa

Az alábbi gráfon az 1-es pontból indulva szélességi bejárást végzünk:

Az egyik lehetséges felfedezési sorrend (a sor tartalma):

    1 2 3 4 6 5 7 10

Mivel egy pont szomszédjainak sorrendje nem rögzített, ezért más bejárási sorrend is lehetséges, pl.

    1 3 2 6 4 7 10 5

Megjegyzések:

• Csak azok a csomópontok lesznek meglátogatva, akik ugyanazon összefüggő komponensben vannak a kiindulóponttal.
• A pontok megjelenésének sorrendje a kiinduló ponttól mért távolságuk szerinti sorrend (távolság == hány élen kell keresztül menni, hogy a kiinduló pontból eljussunk hozzá).

Implementáció

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("input.txt");

    int n, m;
    fin >> n >> m;

    int adj[101][101] = {};

    for (int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;

        adj[a][b] = 1;
        adj[b][a] = 1;
    }

    int sor[101];

    sor[0] = 1; // innen indulunk
    int bal=0, jobb=0;

    bool lattuk[101] = {};
    lattuk[1] = true;

    while (bal <= jobb) {
        int akt = sor[bal];
        bal++;
        cout << akt << " ";

        for (int sz = 1; sz <= n; sz++)
            if (adj[akt][sz] == 1
                && !lattuk[sz])
            {
                ++jobb;
                sor[jobb] = sz;
                lattuk[sz] = true;
            }
    }

    cout << endl;
    return 0;
}

Mélységi bejárás

• angolul Depth First Search, románul parcurgere în adâncime
• Elindulunk a kezdőpontból, addig megyünk előre, amíg tudunk (amíg vannak még nem látogatott pontok), közben egy verembe (stack) tesszük azokat a csomópontokat, amiken átmentünk.
• Amint nem lehet tovább menni, visszatérünk (a veremben előző elemre), és innen próbáljuk meg új ágon folytatni a bejárást.
• Ha nem lehet már folytatni, ismét visszatérünk és így tovább, míg a verem ki nem ürül.

Példa

Az alábbi gráfon mélységi bejárást végzünk a 3-as pontból indulva:

Az egyik lehetséges bejárási sorrend:

    3 1 2 4 5 6 7 10

Közben a verem tartalmának alakulása:

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

Implementáció

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <fstream>
using namespace std;

void dfs(
    int akt,
    int n,
    int adj[101][101],
    bool latott[101])
{
    cout << akt << " ";

    for (int i = 1; i <= n; i++)
        if (adj[akt][i] && !latott[i]) {
            latott[i] = true;
            dfs(i, n, adj, latott);
        }
}

int main()
{
    ifstream fin("input.txt");

    int n, m;
    fin >> n >> m;

    int adj[101][101] = {};

    for (int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;

        adj[a][b] = 1;
        adj[b][a] = 1;
    }

    bool latott[101] = {};
    latott[1] = true;

    dfs(1, n, adj, latott);

    cout << endl;
    return 0;
}