1. Szomszédsági mátrix (matrice de adiacență, adjacency matrix)

Egy n pontú gráf esetén ez egy n x n-es A mátrix, melyben

    A[i][j] = {
        1, ha i és j szomszédosak
        0, ha nem szomszédosak
    }

Példa:

A mellékelt gráf esetén a szomszédsági mátrix:

Tulajdonságok

Szimmetrikus a főátlóra nézve, és a főátlón minden elem 0.
Az x soron (vagy oszlopon) az összeg == x fokszámával.
Az egész mátrix elemeinek összege == 2 * élek száma.

2. Éllista (listă de muchii)

Adott lesz a csomópontok száma és az élek (számpárok) listája.

Példa:

Az fenti példában szerplő gráfnak 5 csomópontja van, az élei pedig:

    [1,2], [1,5], [2,5], [4,5].

3. Szomszédsági listák (liste de adiacență)

Minden csomópont esetén tároljuk a szomszédjainak a listáját.

Példa:

Az fenti példában szerplő gráf esetén a csomópontok szomszédsági listái:

Feladat:

Adott n és m, melyek egy gráf csomópontjainak és éleinek számai, majd ezeket követi m darab számpár, melyek egy-egy élet reprezentálnak.

a) Írjuk ki a gráf szomszédsági mátrixát!

b) Írjuk ki a gráfot ábrázoló szomszédsági listákat!

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <fstream>
using namespace std;

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

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

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

    int lista[101][101];
    int hossz[101] = {};

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

        // szomsz. mátrix:
        matrix[a][b] = 1;
        matrix[b][a] = 1;

        // szomsz. listák építése

        // a-nak a listájába bemegy b
        lista[a][hossz[a]] = b;
        hossz[a]++;

        // b-nek a listájába bemegy a
        lista[b][hossz[b]] = a;
        hossz[b]++;
    }

    cout << "szomsz. matrix: " << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;

    // ha a matrixból állítjuk elő:
    /*
    cout << "szomsz. listak: " << endl;
    for (int i = 1; i <= n; i++) {
        cout << i << ": ";
        for (int j = 1; j <= n; j++) {
            if (matrix[i][j] == 1)
                cout << j << " ";
        }
        cout << endl;
    }
    */

    // ha a közvetlenül felépített listákat használjuk:
    cout << "szomsz. listak: " << endl;
    for (int i = 1; i <= n; i++) {
        cout << i << ": ";
        for (int j = 0; j < hossz[i]; j++) {
            cout << lista[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Feladat:

Adott n, majd egy n x n-es mátrix, mely egy n pontú nemirányított gráf szomsz. mátrixa. Írjuk ki az élek listáját (egy él csak egyszer legyen benne).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <fstream>
using namespace std;

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

    int n;
    fin >> n;

    int t[101][101];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            fin >> t[i][j];

    // végigjárjuk a főátló feletti részt
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            if (t[i][j])
                cout << i << " " << j << endl;

    return 0;
}

Feladat:

https://www.pbinfo.ro/probleme/430/izolate

 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
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("izolate.in");
    ofstream fout("izolate.out");

    int n;
    fin >> n;

    int fok[101] = {};

    int a, b;
    while (fin >> a >> b) {
        fok[a]++;
        fok[b]++;
    }

    int db = 0;
    for (int i = 1; i <= n; i++)
        if (fok[i] == 0)
            db++;
    fout << db << " ";

    for (int i = 1; i <= n; i++)
        if (fok[i] == 0)
            fout << i << " ";
    fout << endl;
    return 0;
}