ਇੱਕ graph vertices ਦਾ ਇੱਕ ਸੈਟ ਹੈ ਜੋ edges ਦੁਆਰਾ ਜੁੜੇ ਹੁੰਦੇ ਹਨ। ਦੋ ਮਾਨਕ ਪ੍ਰਸਤੁਤੀਆਂ ਹਨ adjacency list (ਹਰੇਕ vertex ਆਪਣੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ) ਅਤੇ adjacency matrix (ਬੂਲੀਨਾਂ ਦੀ ਇੱਕ V×V ਗ੍ਰਿਡ)। ਚੋਣ ਗ੍ਰਾਫ density 'ਤੇ ਨਿਰਭਰ ਕਰਦੀ ਹੈ।
ਇੱਕ graph vertices ਦਾ ਇੱਕ ਸੈਟ ਹੈ ਜੋ edges ਦੁਆਰਾ ਜੁੜੇ ਹੁੰਦੇ ਹਨ। ਦੋ ਮਾਨਕ ਪ੍ਰਸਤੁਤੀਆਂ ਹਨ adjacency list (ਹਰੇਕ vertex ਆਪਣੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ) ਅਤੇ adjacency matrix (ਬੂਲੀਨਾਂ ਦੀ ਇੱਕ V×V ਗ੍ਰਿਡ)। ਚੋਣ ਗ੍ਰਾਫ density 'ਤੇ ਨਿਰਭਰ ਕਰਦੀ ਹੈ।
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]
# 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
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Edge exists? | O(degree) | O(1) |
| Iterate neighbors | O(degree) | O(V) |
| Best for | sparse graphs | dense graphs |
ਬਹੁਤੇ ਵਾਸਤਵਿਕ-ਸੰਸਾਰ ਦੇ graphs (ਸਮਾਜਿਕ ਨੈੱਟਵਰਕ, ਰੋਡ ਮੈਪ, ਨਿਰਭਰਤਾ graphs) sparse ਹੁੰਦੇ ਹਨ, ਇਸਲਈ adjacency lists ਬਹੁਤ ਸਾਰੀ ਮੈਮੋਰੀ ਬਚਾਉਂਦੇ ਹਨ ਅਤੇ BFS/DFS ਵਰਗੀਆਂ ਟ੍ਰੈਵਰਸਲਾਂ ਨੂੰ ਤੇਜ਼ ਕਰਦੇ ਹਨ। ਇਸ ਟ੍ਰੇਡ-ਆਫ ਨੂੰ ਜਾਣਨਾ ਤੁਹਾਨੂੰ ਉਹ ਪ੍ਰਸਤੁਤੀ ਚੁਣਨ ਦਿੰਦਾ ਹੈ ਜੋ ਤੁਹਾਡੇ ਗ੍ਰਾਫ ਅਲਗੋਰਿਦਮ ਨੂੰ ਕੁਸ਼ਲ ਰੱਖਦੀ ਹੈ ਬਜਾਏ ਗਲਤੀ ਨਾਲ O(V²) ਮੈਮੋਰੀ ਦੀ ਵਰਤੋਂ ਕਰਨ ਦੇ।