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

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

### Adjacency Matrix

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 too less to matter.

### Adjacency List

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

- Depth first search (DFS)
- Breadth first search (BFS)
- Topological sorting (ordering dependencies)

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