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

### 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 so small enough to not consider.

### 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)
- Bidirectional search
- two simultaneous breadth-first searches
- used to find the shortest path between a source and destination node.
- finished when their searches collide.

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

E.g. 207. Course Schedule

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