గ్రాఫ్ అనేది అంచులతో అనుసంధానించిన శీర్షాల సమితి. రెండు ప్రామాణిక ప్రాతినిధ్యాలు ప్రక్కనే ఉన్న జాబితా (ప్రతి శీర్షం దాని పొరుగువారిని నిల్వ చేస్తుంది) మరియు ప్రక్కనే ఉన్న మాత్ర (బూలియన్ విలువల 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(degree) | O(1) |
| పొరుగువారిని పునరావృత్తి చేయండి | O(degree) | O(V) |
| ఉత్తమం కోసం | విరళ గ్రాఫ్లు | దట్టమైన గ్రాఫ్లు |
ంజరీ నిజ-ప్రపంచ గ్రాఫ్లు (సోషల్ నెట్వర్క్లు, రోడ్డు మ్యాప్లు, డిపెండెన్సీ గ్రాఫ్లు) విరళగా ఉన్నాయి, కాబట్టి ప్రక్కనే ఉన్న జాబితాలు భారీ స్థలాన్ని ఆదా చేస్తాయి మరియు BFS/DFS వంటి ట్రావర్సల్లను వేగవంతం చేస్తాయి.
ఈ ట్రేడ్-ఆఫ్ను తెలుసుకోవడం వల్ల మీరు మీ గ్రాఫ్ అల్గారిథమ్లను సమర్థవంతంగా ఉంచే ప్రాతినిధ్యాన్ని ఎంచుకోగలరు, O(V²) మెమరీని ఆకస్మికంగా ఉపయోగించే బదులుగా.
జూనియర్ నుండి సీనియర్ వరకు వివరణాత్మక సమాధానాలతో IT ఇంటర్వ్యూ ప్రశ్నల లైబ్రరీ.
విరాళం