ગ્રાફ એ શિરોબિંદુઓનો સમૂહ છે જે કિનારીઓ દ્વારા જોડાયેલો છે. બે પ્રમાણભૂત રજૂઆતો સંલગ્નતા સૂચી (દરેક શિરોબિંદુ તેના પાડોશીઓને સંગ્રહ કરે છે) અને સંલગ્નતા મેટ્રિક્સ (બુલિયનનો 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²) મેમોરી વાપરે છે.