एक ग्राफ शिखर का एक सेट है जो किनारों से जुड़ा हुआ है। दो मानक प्रतिनिधित्व सन्निहितता सूची (प्रत्येक शिखर अपने पड़ोसियों को संग्रहीत करता है) और सन्निहितता मैट्रिक्स (बूलियन का एक V×V ग्रिड) हैं। पसंद ग्राफ की घनता पर निर्भर करती है।
एक ग्राफ शिखर का एक सेट है जो किनारों से जुड़ा हुआ है। दो मानक प्रतिनिधित्व सन्निहितता सूची (प्रत्येक शिखर अपने पड़ोसियों को संग्रहीत करता है) और सन्निहितता मैट्रिक्स (बूलियन का एक V×V ग्रिड) हैं। पसंद ग्राफ की घनता पर निर्भर करती है।
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
| सन्निहितता सूची | सन्निहितता मैट्रिक्स | |
|---|---|---|
| स्थान | O(V + E) | O(V²) |
| किनारा मौजूद है? | O(डिग्री) | O(1) |
| पड़ोसियों पर पुनरावृत्ति | O(डिग्री) | O(V) |
| के लिए सर्वश्रेष्ठ | विरल ग्राफ़ | घने ग्राफ़ |
अधिकांश वास्तविक-दुनिया ग्राफ़ (सोशल नेटवर्क, सड़क मानचित्र, निर्भरता ग्राफ़) विरल हैं, इसलिए सन्निहितता सूचियां भारी मात्रा में स्थान बचाती हैं और BFS/DFS जैसी ट्रैवर्सल को तेज करती हैं।
ट्रेड-ऑफ को जानना आपको उस प्रतिनिधित्व को चुनने देता है जो आपके ग्राफ एल्गोरिदम को कुशल रखता है, न कि गलती से O(V²) मेमोरी का उपयोग करने के बजाय।