Graph Basics and Representation

DSA · Graphs

Theory

A graph is a set of vertices (nodes) connected by edges. Edges can be directed (one-way, like follows on social media) or undirected (two-way, like roads), and weighted (with a cost such as distance) or unweighted. Graphs are stored as an adjacency list (each vertex keeps a list of neighbours, O(V + E) space) or an adjacency matrix (a V × V grid, O(V²) space but O(1) edge checks).

Why we use it

Graphs model networks of relationships: maps, social networks, dependencies between tasks, and web links.

When to use it

Use an adjacency list for most sparse real-world graphs; use a matrix for small dense graphs or when you need constant-time edge lookups.

How it works

  1. Vertices V, edges E
  2. Dense graph? Yes: Adjacency matrix (V x V). No: Adjacency list (dict of lists).
  3. Edges have weights? Yes: Store (neighbour, weight). No: Store neighbour.
  4. Choose directed or undirected

Syntax

Adjacency list:   graph = {"A": ["B", "C"], "B": ["A"], ...}
Adjacency matrix: m[i][j] = 1 (or weight) if edge i->j

List:   space O(V+E), neighbours O(degree)
Matrix: space O(V²),  edge check O(1)

Example

edges = [("Delhi", "Jaipur"), ("Delhi", "Agra"), ("Agra", "Lucknow"), ("Jaipur", "Agra")]

graph = {}
for a, b in edges:                 # undirected
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for city in graph:
    print(city, "->", graph[city])

names = sorted(graph)
idx = {n: i for i, n in enumerate(names)}
matrix = [[0] * len(names) for _ in names]
for a, b in edges:
    matrix[idx[a]][idx[b]] = matrix[idx[b]][idx[a]] = 1
print(names)
for row in matrix:
    print(row)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic