A grafika hija sett ta' vertiċi konnessi b'truf. It-tnejn rappreżentazzjonijiet standard huma l-lista ta' viċinanza (kull vertiċi jaħżen il-viċini tiegħu) u l-matriċi ta' viċinanza (griglia V×V ta' Booleans). Il-għażla tiddependi fuq id-densità tal-grafika.
It-tnejn forom
text
Graph: 0 - 1
| |
2 - 3
Adjacency list: Adjacency matrix:
0: [1, 2] 0 1 2 3
1: [0, 3] 0 [0 1 1 0]
2: [0, 3] 1 [1 0 0 1]
3: [1, 2] 2 [1 0 0 1]
3 [0 1 1 0]
Code
python
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1] # O(1) to get a vertex's neighbors
# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1 # O(1) edge lookup
Tqabbil (V vertiċi, E truf)
| Lista ta' viċinanza | Matriċi ta' viċinanza | |
|---|---|---|
| Ispazju | O(V + E) | O(V²) |
| Truf jeżisti? | O(grad) | O(1) |
| Irrepeti l-viċini | O(grad) | O(V) |
| Aħjar għal | grafiċi skarsi | grafiċi densi |
Għaliex hu importanti
Il-biċċa l-kbira tal-grafiċi tal-mond reali (netwerks soċjali, mapep tal-istrada, grafiċi ta' dipendenza) huma skarsi, għalhekk il-listi ta' viċinanza jissejvaw memorja enormi u jħaxxu traversals bħal BFS/DFS.
Li tkun taf it-trade-off jippermettilek li tagħżel ir-rappreżentazzjoni li żżomm l-algoritmi tal-grafika tiegħek efficienti, minflok tirrevertix user O(V²) ta' memorja.