DFS și componentele conexe
O companie de telefonie vrea să știe câte rețele separate de antene are: grupuri de antene care comunică între ele, dar nu și cu celelalte grupuri. În limbajul grafurilor, câte componente conexe are graful? Le găsești cu parcurgerea în adâncime (DFS), pornind câte un DFS din fiecare nod încă nevizitat.
DFS recursiv
DFS merge cât mai adânc pe o ramură, apoi se întoarce și încearcă următorul vecin, exact ca parcurgerea în preordine a unui arbore. Diferența: graful poate avea cicluri, deci marchezi nodurile vizitate.
graf = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1], 4: [5], 5: [4]}
vizitat = set()
def dfs(nod, adancime=0):
vizitat.add(nod) Scrie funcția componente(n, muchii) pentru un graf neorientat cu nodurile 0 .. n-1. Returnează un tuplu (număr de componente, lista componentelor), fiecare componentă fiind sortată, iar componentele în ordinea celui mai mic nod.
- Construiește graful cu {nod: [] for nod in range(n)} și adaugă fiecare muchie în ambele sensuri.
- Parcurge nodurile 0 .. n-1; din fiecare nod nevizitat pornește un DFS care colectează componenta.
- Trebuie să apară: (2, [[0, 1, 2], [3, 4]]), (4, [[0], [1], [2], [3]]), (3, [[0, 3, 5], [1, 4], [2]]), (1, [[0, 1, 2]]).
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan