एक graph भनेको vertices को समूह हो जो edges द्वारा जोडिएको हुन्छ। दुई मानक प्रतिनिधित्व हुन् adjacency list (प्रत्येक vertex ले यसका neighbors लाई store गर्छ) र adjacency matrix (V×V grid of booleans)। छनोट ग्राफको density मा निर्भर गर्छ।
एक graph भनेको vertices को समूह हो जो edges द्वारा जोडिएको हुन्छ। दुई मानक प्रतिनिधित्व हुन् adjacency list (प्रत्येक vertex ले यसका neighbors लाई store गर्छ) र adjacency matrix (V×V grid of booleans)। छनोट ग्राफको 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 |
अधिकांश वास्तविक-संसार ग्राफहरु (social networks, road maps, dependency graphs) sparse हुन्छन्, त्यसैले adjacency lists असाधारण रूपमा स्पेस बचाउँछन् र BFS/DFS जस्तै traversals लाई गति दिन्छन्।
ट्रेड-अफ जान्दा तपाईले यो प्रतिनिधित्व छनोट गर्न सक्नुहुन्छ जसले तपाईको ग्राफ algorithms लाई दक्ष राख्छ अनायासै O(V²) memory प्रयोग गर्नुको सट्टा।
विस्तृत उत्तरसहित IT अन्तर्वार्ता प्रश्नहरूको पुस्तकालय — जुनियरदेखि सिनियरसम्म।
दान गर्नुहोस्