Module 5 Graph Search 18

Graph Representation — Adjacency Matrix vs Adjacency List

Build one graph, then see how it looks as a 2D array (matrix) and an array of linked lists (adjacency list). Click a node to highlight its row/column and neighbors. Open the Insights tab for “what the matrix tells you”.

V 6  ·  E 7 Density — Selected —
Tip: Click a node in the graph to highlight its row (outgoing), column (incoming), and its adjacency list.
🔎 Query Playground (see O(1) vs O(deg))
Try the same query in both representations. Matrix checks A[u][v] in O(1), while List scans neighbors of u in O(deg(u)).
Matrix space 36
List space 13
Edge lookup O(1) vs O(deg)
Neighbors O(V) vs O(deg)
Avg deg —
Diagonal self-loops (A[i][i])
Row outgoing
Col incoming
Undirected: matrix is symmetric (A[i][j] = A[j][i]).
Degrees: count the non-zero entries in a row (out-degree), and in a column (in-degree for directed graphs).
Adjacency list = array of linked lists. Each row is a head pointer for neighbors of that node.
Edge list is the simplest representation: store edges as pairs (u,v) (and w if weighted). Great for algorithms like Kruskal and for iterating over all edges in O(E).
Iterate edges O(E) Edge lookup usually O(E) (unless hashed)

Graph type (from matrix)

—

Diagonal (self-loops)

—

Isolated vertices

—

Connectivity hint

—

Selected node summary

Click a node to see row/column sums and neighbors.
Block pattern idea: if the matrix can be rearranged into block-diagonal form, the graph has multiple components. (We verify this using BFS in the “Check connectivity” button.)

🌍 Real-world idea: Graph from locations

Turn places into a graph using latitude/longitude. This matches what students see in Google Maps.
  • Node = location (lat, lon)
  • Edge = road between two locations
  • Weight = distance (km) or travel time (min)
Why we care: Weighted graph → Dijkstra finds the shortest path from a source to all nodes.
In this demo: if Weighted is ON and you click Plot using lon/lat, weights can auto-fill using Haversine distance (approx km).
Weighted matrix uses edge distances
If “Weighted” is ON and you apply geo layout, edge weights will auto-fill as Haversine distance (km) for the edges you created. (No Google Maps API needed to understand the concept.)

Next pages: 19 — BFS (queue + levels + shortest path unweighted) and 20 — DFS (recursion/stack + traversal tree).