Graph is a non-linear data structure.  It is a collection of nodes (vertices) connected by edges.  No rules for connections.


Directed edge – connection is one way
Undirected edge – two way connection

Mathematical Representation

A graph G is an ordered pair of a set V of vertices and a set E of edges.
G = (V,E)

A graph is either a:

  • Directed graph (i.e. links on world wide web) – problems web crawling
  • Undirected graph (i.e. friendship graph) – problems friend recommendations
  • Weighted (i.e. Map of roads)

Graph Representation

Vertex List / Edge List

Finding adjacent nodesO(|E|)
Check if given nodes are connectedO(|E|)

Adjacency Matrix 

Finding adjacent nodesO(V)
Check if given nodes are connectedO(1)

There is a big space-time trade off here.
O(v^2) space.
You wouldn’t want to store a social network on an adjacency matrix.  There would be a lot of wasted space.
Good if graph is dense or V^2 is too less to matter.

Adjacency List

Adjacency matrix wastes a lot of space by also storing non-connected edges.

Finding adjacent nodesO(V)
Check if given nodes are connectedO(V) or O(logv) if we keep sorted

Space = O(e)


Topological sorting

The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs.