• Graph is a non-linear data structure.
• It is a collection of nodes (vertices) connected by edges.
• No rules for connections.
• The graph might consist of multiple isolated subgraphs. If there is a path between every pair of vertices, it is called a connected graph.
• The graph can have cycles (or not). An acyclic graph is one without cycles.

## Edges

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

 Operation Running-time Finding adjacent nodes O(|E|) Check if given nodes are connected O(|E|)

 Operation Running-time Finding adjacent nodes O(V) Check if given nodes are connected O(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 so small enough to not consider.

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

 Operation Running-time Finding adjacent nodes O(V) Check if given nodes are connected O(V) or O(logv) if we keep sorted

Space = O(e)

## Algorithms

### 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.

https://en.wikipedia.org/wiki/Topological_sorting