CodeWithYash

Intermediate · Module 17 · Lesson 1

Graph representation

Adjacency lists, matrices, edge lists, and direction.

15–25 min readLesson 95 of 123

Lesson 95 of 123

1d streak

Theory lesson · Step-by-step

Understand Graph representation

Adjacency lists, matrices, edge lists, and direction.

Worked approach

Trace the reasoning step by step

  1. 1Choose a graph representation and define directedness and weights for Graph representation.
  2. 2Initialize visited, distance, parent, color, indegree, or component state.
  3. 3Remove one frontier item and inspect each outgoing edge.
  4. 4Update only when an edge proves new or better information.
  5. 5Repeat from every unvisited vertex when the graph may be disconnected.

Concrete example

Represent undirected edges (0,1) and (1,2).

  1. 1Adjacency list 0:[1], 1:[0,2], 2:[1].
  2. 2Matrix marks symmetric cells.

The list uses O(V+E) space; the matrix uses O(V²).

What must remain true (Loop Invariant)

Every vertex finalized by Graph representation has the promised reachability, component, order, or distance property; frontier state represents discovered but unfinished work.

Cost Model

Complexity & Trade-offs

Build adjacency list / matrix
O(V + E) / O(V²)
O(V + E) / O(V²)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Networks, dependencies, connectivity, shortest paths, and grid movement.
  • Ordering prerequisite-constrained work.
  • Grouping reachable or mutually reachable states.

Common mistakes

  • Marking visited too late and enqueuing the same vertex repeatedly.
  • Ignoring disconnected components.
  • Using an algorithm whose weight assumptions do not match the graph.

Practice prompts

  • Reproduce the worked Graph representation example without looking at the trace.
  • Change one input condition and explain whether the Graph representation invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.