Graph Representations (Adjacency Matrix, Adjacency List)
Graph Representations (Adjacency Matrix, Adjacency List)
Pick a representation based on graph density, operations, and memory.
Adjacency Matrix
N×Nboolean/weight grid- Edge check
O(1), iterate neighborsO(N)per vertex - Space
O(N^2)even if few edges - Great for dense graphs,
Floyd–Warshall, or bitset tricks
// Matrix (weights or Infinity for no edge)
const N = 4
const INF = 1e15
const mat = Array.from({ length: N }, () => Array(N).fill(INF))
for (let i=0;i<N;i++) mat[i][i]=0
function addDirected(u,v,w=1){ mat[u][v]=w }
Adjacency List
- Array/map of neighbor lists:
adj[u] = [v1, v2, ...]or weightedadjW[u] = [[v,w], ...] - Edge check
O(deg(u)), iterate neighborsO(deg(u)) - Space
O(N + M)forNvertices andMedges - Excellent for sparse graphs and most traversals
// Unweighted undirected
const N = 5
const adj = Array.from({ length: N }, () => [])
function addUndirected(u, v) { adj[u].push(v); adj[v].push(u) }
Edge List
- Just a list of edges
[[u,v,w], ...] - Minimal overhead; sort/filter-friendly (e.g., Kruskal)
- Convert to matrix/list as needed for traversal
const edges = []
function addEdge(u,v,w=1){ edges.push([u,v,w]) }
Conversions and Tips
- Matrix → List: scan rows to collect neighbors in
O(N^2) - List → Matrix: fill grid in
O(N + M) - For directed graphs, only add one direction; for undirected, add both
- Weighted graphs: store pairs
[v,w]or an object{ v, w } - Self-loops and multi-edges: represent explicitly if needed
Sparse graphs favor adjacency lists; dense graphs may favor matrices. For algorithms dominated by neighbor iteration (BFS, DFS), lists usually win.
التالي · الدرس 62 من 92
Breadth-First Search (BFS)
قراءة 2 دقيقة
أنهيت 61 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

