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.

Definitions

• Vertex: each element of the graph.

• Edge: each connection between vertices, represented as (s, e), meaning the start and the end vertex.

• In-degree: how many edges enter the vertex.

• Out-degree: how many edges leave the vertex.

• Directed graph: when the edges are one-way arrows, otherwise it is an undirected graph.

• Cyclic graph: when the edges allow you to move in circles, otherwise it is an acyclic graph.

• DAG: directed acyclic graph, a very widely used type of graph.

• Topological sorting: a list of the vertices of a DAG following the hierarchy in which one connects to the next.

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.