Lista sąsiedztwa vs macierz sąsiedztwa — kiedy którą wybrać?

Głębiej

Wybór zależy głównie od gęstości grafu i operacji, które dominują.

Lista sąsiedztwa:

• Pamięć: O(V + E)
• Iterowanie sąsiadów u: O(deg(u))
• Sprawdzenie krawędzi (u, v): O(deg(u)), chyba że trzymasz set per wierzchołek

Macierz sąsiedztwa:

• Pamięć: O(V^2)
• Iterowanie sąsiadów u: O(V) (skanujesz cały wiersz)
• Sprawdzenie krawędzi (u, v): O(1)

Kiedy co wybrać

• Graf rzadki (E dużo mniejsze niż V^2): lista.
• Graf gęsty albo mnóstwo zapytań o istnienie krawędzi: macierz.
• Algorytmy:
• BFS/DFS/Dijkstra: zwykle lista.
• Floyd–Warshall / domknięcie przechodnie: macierz (często z bitsetami).

Przykłady

// Lista sąsiedztwa
const adj: number[][] = Array.from({ length: n }, () => [])
adj[u].push(v)

// Macierz sąsiedztwa
const mat: boolean[][] = Array.from({ length: n }, () => Array(n).fill(false))
mat[u][v] = true