Matrice sau liste de adiacență pentru un graf?
Compară memoria, verificarea unei muchii și enumerarea vecinilor. Alege reprezentarea după numărul de noduri, de muchii și operațiile algoritmului.
În acest material
Un graf are noduri și legături între ele, numite muchii. Reprezentarea în memorie trebuie să permită operațiile de care are nevoie algoritmul. Matricea și listele de adiacență descriu același graf, dar au costuri diferite pentru unele operații.
Matricea rezervă toate perechile
Pentru n noduri, matricea de adiacență are n ori n poziții. O poziție indică dacă există muchia dintre două noduri sau, într-un model ponderat, poate păstra un cost împreună cu o convenție clară pentru absență.
Verificarea unei perechi date se face prin acces direct la o celulă. În schimb, pentru a enumera vecinii unui nod, parcurgi de obicei întreaga lui linie, inclusiv pozițiile fără muchii. Spațiul matricei este pătratic în n.
Listele păstrează vecinii existenți
În listele de adiacență, fiecare nod are o colecție a vecinilor săi. Pentru un graf neorientat simplu, fiecare muchie apare de obicei în două liste, câte o dată pentru fiecare sens. Spațiul este proporțional cu n plus numărul de muchii.
Enumerarea vecinilor vizitează numai intrările existente. Verificarea unei muchii arbitrare nu mai este automat un acces direct constant: într-o listă obișnuită, poate cere căutarea vecinului. Alte structuri pot schimba acest cost, cu alte compromisuri.
Un lanț neorientat de 1000 de noduri are 999 de muchii. Matricea are 1000000 de poziții; listele păstrează 1998 de intrări de vecinătate plus structura listelor.Mărește schema ↗
Graf rar și graf dens
Un graf rar are relativ puține muchii față de numărul perechilor posibile. Pentru el, listele pot economisi mult spațiu. Un graf dens are multe muchii, iar avantajul de spațiu poate fi mai mic.
Pentru 1000 de noduri legate într-un lanț, matricea rezervă un milion de poziții, deși există numai 999 de muchii. Listele unui model neorientat păstrează 1998 de intrări de vecinătate, plus structura celor 1000 de liste.
Complexitatea parcurgerii depinde de reprezentare
O parcurgere care verifică fiecare linie a matricei poate costa O(n²). Cu liste, aceeași idee de vizitare poate costa O(n+m), unde m este numărul muchiilor. Nu copia analiza unei implementări cu liste sub un cod care scanează matricea.
Alege după limite și operații: acces direct la perechi, enumerarea vecinilor, modificări sau memorarea costurilor. Pentru grafuri mici, claritatea matricei poate fi potrivită; pentru grafuri rare mari, listele sunt adesea necesare.
Revezi reprezentarea grafurilor, parcurgerile și complexitatea.
Întrebări frecvente
Câtă memorie ocupă matricea de adiacență?
O(n²) poziții pentru n vârfuri, indiferent de numărul muchiilor. Este convenabilă pentru verificarea directă a existenței unei muchii, dar poate consuma mult pentru grafuri rare.
Când sunt utile listele de adiacență?
Când vrei să parcurgi eficient vecinii existenți, mai ales într-un graf rar. Reprezentarea obișnuită ocupă O(n+m) spațiu pentru n vârfuri și m muchii.
Reprezentarea grafului schimbă complexitatea BFS?
Da. Cu liste de adiacență, parcurgerea în lățime are O(n+m) timp. Cu o matrice, examinarea unei linii pentru fiecare vârf poate duce la O(n²).