Grafuri — Reprezentări și Parcurgeri
Grafuri — Reprezentări și Parcurgeri¶
Ce este un Graf?¶
Un graf $G = (V, E)$ este o structură matematică formată din:
- $V$ — mulțimea vârfurilor (nodurilor)
- $E \subseteq V \times V$ — mulțimea muchiilor (legăturilor)
Grafurile modelează relații: rețele sociale (prieteni), hărți (drumuri), dependențe (task-uri), rețele de calculatoare, structuri moleculare.
Tipuri de grafuri¶
Neorientat: muchiile nu au direcție — dacă A e conectat cu B, și B e conectat cu A. Exemplu: prietenii pe Facebook.
Orientat (digraf): muchiile au direcție — $(u, v) \neq (v, u)$. Exemplu: follow pe Twitter, dependențe între task-uri.
Ponderat: fiecare muchie are un cost/greutate $w(u, v)$. Exemplu: distanțe pe hartă, latențe în rețea.
Aciclic: nu conține cicluri. Un DAG (Directed Acyclic Graph) este un graf orientat aciclic — esențial pentru sortare topologică.
Terminologie esențială¶
- Grad (degree): numărul de muchii incidente unui nod. La grafuri orientate: in-degree (câte intră) și out-degree (câte ies).
- Cale (path): secvență de noduri conectate prin muchii
- Ciclu: cale care începe și se termină în același nod
- Componentă conexă: submulțime maximală de noduri interconectate
- Graf complet: toate perechile de noduri sunt conectate — $|E| = \frac{n(n-1)}{2}$
Reprezentări¶
Lista de Adiacență¶
Fiecare nod stochează o listă cu vecinii săi. Cea mai folosită reprezentare.
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.adj = defaultdict(list)
self.directed = directed
def add_edge(self, u, v, weight=None):
if weight is not None:
self.adj[u].append((v, weight))
if not self.directed:
self.adj[v].append((u, weight))
else:
self.adj[u].append(v)
if not self.directed:
self.adj[v].append(u)
def neighbors(self, u):
return self.adj[u]
def nodes(self):
return self.adj.keys()
Spațiu: $O(V + E)$ — eficient pentru grafuri rare (sparse), care sunt majoritatea în practică.
Matricea de Adiacență¶
Un tablou 2D unde matrix[i][j] = 1 (sau greutatea) dacă există muchie de la $i$ la $j$.
class GraphMatrix:
def __init__(self, n):
self.n = n
self.matrix = [[0] * n for _ in range(n)]
def add_edge(self, u, v, weight=1):
self.matrix[u][v] = weight
self.matrix[v][u] = weight # pentru neorientat
def has_edge(self, u, v):
return self.matrix[u][v] != 0
Spațiu: $O(V^2)$ — eficient pentru grafuri dense (aproape complete).
Când folosim ce?¶
| Criteriu | Listă de adiacență | Matrice |
|---|---|---|
| Spațiu | $O(V + E)$ | $O(V^2)$ |
| Verificare muchie | $O(\text{degree})$ | $O(1)$ |
| Iterare vecini | $O(\text{degree})$ | $O(V)$ |
| Adăugare muchie | $O(1)$ | $O(1)$ |
| Grafuri rare | ✅ Ideal | Risipitor |
| Grafuri dense | OK | ✅ Ideal |
Majoritatea grafurilor din lumea reală sunt rare — un utilizator Facebook are ~300 de prieteni, nu 3 miliarde.
BFS — Breadth-First Search¶
BFS explorează graful nivel cu nivel, vizitând toți vecinii unui nod înainte de a merge mai departe. Folosește o coadă (FIFO).
from collections import deque
def bfs(graph, start):
"""
Parcurgere BFS — O(V + E).
Returnează ordinea de vizitare și distanțele de la start.
"""
visited = {start}
queue = deque([start])
order = []
distance = {start: 0}
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.adj[node]:
if neighbor not in visited:
visited.add(neighbor)
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return order, distance
Proprietăți BFS¶
- Complexitate: $O(V + E)$ — vizităm fiecare nod și fiecare muchie o singură dată
- Cel mai scurt drum: BFS găsește automat cel mai scurt drum (în număr de muchii) de la sursă la orice nod
- Niveluri: nodurile aflate la distanța $d$ de sursă sunt descoperite toate înainte de cele la distanța $d+1$
Aplicație: Reconstrucția drumului¶
def bfs_shortest_path(graph, start, end):
"""Găsește cel mai scurt drum de la start la end"""
if start == end:
return [start]
visited = {start}
queue = deque([start])
parent = {start: None}
while queue:
node = queue.popleft()
for neighbor in graph.adj[node]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
queue.append(neighbor)
if neighbor == end:
# Reconstruim drumul
path = []
current = end
while current is not None:
path.append(current)
current = parent[current]
return path[::-1]
return None # nu există drum
# Exemplu
g = Graph()
for u, v in [(0,1), (0,2), (1,3), (2,3), (3,4), (2,5), (5,4)]:
g.add_edge(u, v)
print(bfs_shortest_path(g, 0, 4)) # [0, 1, 3, 4] sau [0, 2, 3, 4]
Aplicație: Componente conexe¶
def connected_components(graph, n):
"""Găsește toate componentele conexe ale unui graf neorientat"""
visited = set()
components = []
for node in range(n):
if node not in visited:
# BFS de la acest nod
component = []
queue = deque([node])
visited.add(node)
while queue:
u = queue.popleft()
component.append(u)
for v in graph.adj[u]:
if v not in visited:
visited.add(v)
queue.append(v)
components.append(component)
return components
DFS — Depth-First Search¶
DFS explorează cât mai adânc posibil pe o ramură înainte de a reveni și a încerca altă ramură. Folosește o stivă (explicit sau implicit prin recursivitate).
Varianta recursivă¶
def dfs_recursive(graph, start, visited=None):
"""DFS recursiv — O(V + E)"""
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph.adj[start]:
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
Varianta iterativă¶
def dfs_iterative(graph, start):
"""DFS iterativ cu stivă explicită — evită stack overflow"""
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
result.append(node)
# Adăugăm vecinii în ordine inversă pentru a menține ordinea naturală
for neighbor in reversed(graph.adj[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
Timpii de descoperire și finalizare¶
DFS oferă informații structurale profunde prin timpii de descoperire (când intrăm într-un nod) și finalizare (când ieșim):
class DFSInfo:
def __init__(self):
self.time = 0
self.discovery = {}
self.finish = {}
self.parent = {}
def dfs_full(self, graph, nodes):
"""DFS complet cu timpi — folosit pentru sortare topologică, SCC, etc."""
visited = set()
for node in nodes:
if node not in visited:
self._dfs_visit(graph, node, visited)
def _dfs_visit(self, graph, u, visited):
visited.add(u)
self.time += 1
self.discovery[u] = self.time
for v in graph.adj[u]:
if v not in visited:
self.parent[v] = u
self._dfs_visit(graph, v, visited)
self.time += 1
self.finish[u] = self.time
Clasificarea muchiilor (în grafuri orientate)¶
DFS clasifică fiecare muchie $(u, v)$:
- Tree edge: $v$ nu a fost descoperit — face parte din arborele DFS
- Back edge: $v$ e un strămoș al lui $u$ — indică un ciclu!
- Forward edge: $v$ e un descendent al lui $u$ (dar nu pe tree edge)
- Cross edge: $v$ e într-un subarbore diferit
Aplicație: Detectarea ciclurilor¶
def has_cycle_directed(graph, n):
"""
Un graf orientat are ciclu ⟺ DFS găsește un back edge.
Folosim 3 stări: WHITE (nevizitat), GRAY (în procesare), BLACK (finalizat).
Back edge = muchie către un nod GRAY.
"""
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(u):
color[u] = GRAY
for v in graph.adj[u]:
if color[v] == GRAY:
return True # back edge → ciclu!
if color[v] == WHITE and dfs(v):
return True
color[u] = BLACK
return False
return any(dfs(u) for u in range(n) if color[u] == WHITE)
def has_cycle_undirected(graph, n):
"""La grafuri neorientate: ciclu ⟺ vedem un nod deja vizitat (care nu e părintele)"""
visited = set()
def dfs(u, parent):
visited.add(u)
for v in graph.adj[u]:
if v not in visited:
if dfs(v, u):
return True
elif v != parent:
return True # ciclu!
return False
return any(dfs(u, -1) for u in range(n) if u not in visited)
Sortare Topologică¶
Ordonează nodurile unui DAG astfel încât pentru orice muchie $(u, v)$, $u$ apare înaintea lui $v$. Util pentru: dependențe (build systems, cursuri universitare), planificarea task-urilor.
Varianta DFS (Kahn cu finish times)¶
def topological_sort_dfs(graph, n):
"""
Sortare topologică cu DFS.
Ideea: nodul care se finalizează ULTIMUL trebuie să fie PRIMUL.
"""
visited = set()
stack = [] # va conține nodurile în ordine topologică inversă
def dfs(u):
visited.add(u)
for v in graph.adj[u]:
if v not in visited:
dfs(v)
stack.append(u) # adăugăm DUPĂ ce finalizăm
for u in range(n):
if u not in visited:
dfs(u)
return stack[::-1] # inversăm
Varianta BFS (Algoritmul lui Kahn)¶
def topological_sort_bfs(graph, n):
"""
Algoritmul lui Kahn — BFS cu in-degree.
Procesăm nodurile cu in-degree 0, scăzând in-degree-ul vecinilor.
"""
in_degree = [0] * n
for u in range(n):
for v in graph.adj[u]:
in_degree[v] += 1
queue = deque([u for u in range(n) if in_degree[u] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph.adj[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != n:
raise ValueError("Graful conține un ciclu — nu se poate sorta topologic!")
return result
Avantajul Kahn: detectează automat ciclurile — dacă
len(result) < n, există un ciclu.
Dijkstra — Drumuri Minime¶
Algoritmul Dijkstra găsește cel mai scurt drum de la un nod sursă la toate celelalte, într-un graf ponderat cu costuri pozitive.
Ideea: menține o mulțime de noduri „finalizate" cu distanța minimă cunoscută. La fiecare pas, extrage nodul nefinalizat cu distanța cea mai mică (greedy) și actualizează distanțele vecinilor.
import heapq
def dijkstra(graph, start):
"""
Dijkstra cu min-heap — O((V + E) log V).
graph.adj[u] conține tuple (vecin, cost).
"""
dist = defaultdict(lambda: float('inf'))
dist[start] = 0
parent = {start: None}
pq = [(0, start)] # (distanță, nod)
while pq:
d, u = heapq.heappop(pq)
# Dacă am găsit deja un drum mai scurt, skip
if d > dist[u]:
continue
for v, weight in graph.adj[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
parent[v] = u
heapq.heappush(pq, (new_dist, v))
return dict(dist), parent
def reconstruct_path(parent, target):
"""Reconstruiește drumul de la sursă la target"""
path = []
current = target
while current is not None:
path.append(current)
current = parent.get(current)
return path[::-1]
De ce nu funcționează cu ponderi negative? Dijkstra se bazează pe faptul că odată ce un nod e „finalizat", distanța sa nu se mai poate îmbunătăți. Cu ponderi negative, un drum indirect ar putea fi mai scurt — principiul greedy se rupe. Pentru ponderi negative, folosim Bellman-Ford ($O(V \cdot E)$).
Exemplu complet¶
# Graf ponderat: oraș cu drumuri
g = Graph(directed=False)
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 8)
g.add_edge('C', 'E', 10)
g.add_edge('D', 'E', 2)
dist, parent = dijkstra(g, 'A')
print(f"Distanțe de la A: {dist}")
# {'A': 0, 'C': 2, 'B': 3, 'D': 8, 'E': 10}
print(f"Drum A → E: {reconstruct_path(parent, 'E')}")
# ['A', 'C', 'B', 'D', 'E'] (cost: 2+1+5+2 = 10)
BFS vs DFS — Când folosim ce?¶
| Problemă | BFS | DFS |
|---|---|---|
| Cel mai scurt drum (neponderat) | ✅ | ❌ |
| Componente conexe | ✅ | ✅ |
| Detectare cicluri | ✅ (indirect) | ✅ (direct) |
| Sortare topologică | ✅ (Kahn) | ✅ |
| Verificare graf bipartit | ✅ (colorare) | ✅ |
| Labirint (orice cale) | OK | ✅ (mai simplu) |
| Spațiu pe grafuri largi | $O(V)$ per nivel | $O(V)$ per adâncime |
Exerciții¶
-
Implementați un algoritm care verifică dacă un graf neorientat este bipartit (colorabil cu 2 culori). Hint: BFS cu colorare.
-
Implementați Bellman-Ford pentru drumuri minime cu ponderi negative și detectarea ciclurilor negative
-
Dat un grid 2D cu
0(teren liber) și1(obstacol), găsiți cel mai scurt drum de la colțul stânga-sus la dreapta-jos. Modelați grid-ul ca un graf implicit. -
Implementați componente tare conexe (SCC) folosind algoritmul lui Kosaraju (două DFS-uri)