Python de la zero

2. Ce este un graf?

Putem folosi grafuri pentru rețele de drumuri, prietenii între persoane, conexiuni între calculatoare, hărți, relații între obiecte și multe alte situații.

Graf neorientat

Dacă există muchia dintre A și B, putem merge din A în B și din B în A.

Graf orientat

O muchie are direcție: A → B nu înseamnă automat și B → A.

Graf ponderat

Fiecărei muchii îi putem asocia o valoare, de exemplu distanța, timpul sau costul.

3. Cum reprezentăm un graf în Python?

Vom folosi două reprezentări importante. Alegerea reprezentării depinde de problemă.

Numerotarea vârfurilor

În Python este comod să numerotăm vârfurile de la 0 la n-1.

n = 5
# vârfurile sunt: 0, 1, 2, 3, 4

4. Lista de adiacență

Pentru graful cu muchiile 0—1, 0—2, 1—3, putem scrie:

graf = [
    [1, 2],
    [0, 3],
    [0],
    [1]
]

graf[0] este lista vecinilor lui 0. graf[1] este lista vecinilor lui 1.

Construirea unui graf neorientat

n = 4
graf = [[] for i in range(n)]

a = 0
b = 1
graf[a].append(b)
graf[b].append(a)

Muchia trebuie introdusă în ambele liste deoarece graful este neorientat.

Construirea unui graf orientat

n = 4
graf = [[] for i in range(n)]

a = 0
b = 1
graf[a].append(b)

Aici introducem doar direcția 0 → 1.

5. Matricea de adiacență

Pentru n vârfuri folosim o matrice n × n. Dacă există muchia dintre i și j, punem 1; altfel 0.

n = 4
mat = [[0] * n for i in range(n)]

mat[0][1] = 1
mat[1][0] = 1

Pentru un graf neorientat, matricea este simetrică față de diagonala principală.

Lista sau matrice?

6. BFS — parcurgerea pe niveluri

Pentru BFS avem nevoie de o coadă. Vom implementa coada folosind o listă și un indice.

def bfs(graf, start):
    n = len(graf)
    vizitat = [False] * n
    coada = [start]
    vizitat[start] = True
    poz = 0

    while poz < len(coada):
        nod = coada[poz]
        poz = poz + 1
        print(nod)

        for vecin in graf[nod]:
            if not vizitat[vecin]:
                vizitat[vecin] = True
                coada.append(vecin)

BFS pentru distanțe

Într-un graf neponderat, BFS poate calcula numărul minim de muchii de la sursă la fiecare vârf.

def distante(graf, start):
    n = len(graf)
    dist = [-1] * n
    coada = [start]
    dist[start] = 0
    poz = 0

    while poz < len(coada):
        nod = coada[poz]
        poz = poz + 1

        for vecin in graf[nod]:
            if dist[vecin] == -1:
                dist[vecin] = dist[nod] + 1
                coada.append(vecin)

    return dist

7. DFS — parcurgerea în adâncime

DFS recursiv

def dfs(graf, nod, vizitat):
    vizitat[nod] = True
    print(nod)

    for vecin in graf[nod]:
        if not vizitat[vecin]:
            dfs(graf, vecin, vizitat)

Observăm legătura directă cu recursivitatea studiată în Partea 5.

BFS și DFS

8. Existența unui drum

O întrebare frecventă este: „Se poate ajunge de la s la t?”. Putem porni un DFS și verificăm dacă ajungem la destinație.

def exista_drum(graf, start, destinatie):
    vizitat = [False] * len(graf)

    def dfs(nod):
        vizitat[nod] = True

        if nod == destinatie:
            return True

        for vecin in graf[nod]:
            if not vizitat[vecin]:
                if dfs(vecin):
                    return True

        return False

    return dfs(start)

9. Componente conexe

Într-un graf neorientat, două vârfuri aparțin aceleiași componente conexe dacă există un drum între ele.

Algoritmul: parcurgem toate vârfurile. Dacă găsim unul nevizitat, pornim un DFS nou și am găsit o componentă nouă.

def componente(graf):
    n = len(graf)
    vizitat = [False] * n
    nr = 0

    for i in range(n):
        if not vizitat[i]:
            nr = nr + 1
            dfs(graf, i, vizitat)

    return nr

Numărul de porniri DFS este numărul componentelor conexe.

10. Drum minim într-un graf ponderat — ideea lui Dijkstra

Vom înțelege mai întâi ideea, apoi implementarea. Pentru fiecare vârf păstrăm cea mai bună distanță cunoscută.

1. Inițial, distanța sursei este 0, iar celelalte sunt foarte mari.
2. Alegem vârful nevizitat cu distanța cea mai mică.
3. Încercăm să îmbunătățim distanțele vecinilor.
4. Marcăm vârful ca procesat.
5. Repetăm.

def dijkstra(graf, start):
    n = len(graf)
    INF = 10**18
    dist = [INF] * n
    vizitat = [False] * n
    dist[start] = 0

    for pas in range(n):
        nod = -1

        for i in range(n):
            if not vizitat[i] and (nod == -1 or dist[i] < dist[nod]):
                nod = i

        if nod == -1 or dist[nod] == INF:
            break

        vizitat[nod] = True

        for muchie in graf[nod]:
            vecin = muchie[0]
            cost = muchie[1]

            if dist[nod] + cost < dist[vecin]:
                dist[vecin] = dist[nod] + cost

    return dist

11. Exerciții rezolvate

graf = [[] for i in range(4)]

muchii = [[0, 1], [0, 2], [1, 3]]

for muchie in muchii:
    a = muchie[0]
    b = muchie[1]
    graf[a].append(b)
    graf[b].append(a)

print(graf)

print(len(graf[v]))

vizitat = [False] * len(graf)
coada = [0]
vizitat[0] = True
poz = 0

while poz < len(coada):
    nod = coada[poz]
    poz = poz + 1
    print(nod)

    for vecin in graf[nod]:
        if not vizitat[vecin]:
            vizitat[vecin] = True
            coada.append(vecin)

d = distante(graf, 0)
print(d)

graf = [
    [[1, 4], [2, 2]],
    [[0, 4], [3, 5]],
    [[0, 2], [3, 1]],
    [[1, 5], [2, 1]]
]

print(dijkstra(graf, 0))

12. Exerciții propuse

13. Greșeli frecvente

• Confundarea vârfului cu indicele din Python.
• Adăugarea unei muchii o singură dată într-un graf neorientat.
• Uitarea vectorului vizitat.
• Adăugarea repetată a aceluiași vârf în coada BFS.
• Folosirea Dijkstra când există muchii cu ponderi negative.
• Confundarea BFS cu DFS.
• Încercarea de a memora algoritmul fără să înțelegi ce reprezintă fiecare variabilă.

14. Recapitulare