கிராப் என்பது உச்சங்களால் இணைக்கப்பட்ட விளிம்புகளின் ஒரு தொகுப்பு. இரண்டு நிலையான பிரதிநிதித்துவங்கள் அடுத்தடுத்த பட்டியல் (ஒவ்வொரு உச்சமும் அதன் அண்டை மக்களை சேமிக்கிறது) மற்றும் அடுத்தடுத்த மேட்ரிக்ஸ் (பூலியன் மதிப்புகளின் 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(degree) | O(1) |
| அண்டை மக்களை சுற்றுவர | O(degree) | O(V) |
| சிறந்த முறை | அரிய கிராப்ஸ் | அடர்த்தியான கிராப்ஸ் |
অধিকাংশ நிজ-உலக கிராப்ஸ் (சামाजिक நெட்வொர்க்குகள், சாலைகளின் வரைபடங்கள், சார்பு கிராப்ஸ்) அரிதாக உள்ளன, எனவே அடுத்தடுத்த பட்டியல்கள் பாரிய இடத்தை சேமிக்கிறது மற்றும் BFS/DFS போன்ற பயணங்களை வேகம் அதிகரிக்கிறது.
இந்த சமநிலை அறிந்து, உனது கிராப்ப் அ்যালগরிதம்களை திறமையாக வைத்திருக்கும் பிரதிநிதித்துவத்தைத் தேர்வு செய்ய உனக்கு அனுமதிக்கிறது, O(V²) நினைவகத்தை தற்செயலாக பயன்படுத்துவதற்கு பதிலாக.