Graphs cheatsheet

Here is a list with some of the most basic forms of graphs and how to implement them. Graphs are useful when implementing search algorithms.

Edge list

1. Create an array with sub arrays.

2. Each sub array will contain 2 numbers which represent the vertices that form the edge.

3. It may contain a 3^rd number to represent the weight.

4. It doesn't use much memory but the search time is long.

Adjacency matrix

1. Create a matrix with all the vertices x vertices. The indices of the rows and columns of the matrix will be the vertices.

2. Add the number 1 when 2 vertices form an edge.

3. Add the number 0 otherwise.

4. It uses a lot of memory but the search time is super fast.

Adjacency list

1. Create an array with sub arrays.

2. Each sub array's index will represent a vertex.

3. Fill each sub array with the vertices it forms edges with.

4. This one doesn't use much memory and the search time is short.

Notes

1. Adjacency matrix is the fastest, but uses the most memory, Adjacency list uses the least memory and Edge list is the worst in both memory and speed.