एक ग्राफ हा शिरोबिंदूंनी किनारोंद्वारे जोडलेल्या संच आहे. दोन मानक प्रतिनिधित्व म्हणजे समीपता यादी (प्रत्येक शिरोबिंदू त्याचे शेजारी संग्रहीत करतो) आणि समीपता मॅट्रिक्स (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²) मेमरी अनजाने वापरणे टाळताना.