# Algorithms Notes – Chapter 4

xkcd/835

Graph Algorithms

Over the next few chapters, we will learn and analyse the following two graph algorithms:

• Depth First Search (DFS)

Representation of Graphs

In computer science, it is common to represent graphs in one of two ways.

An adjacency list of a graph $G = (V, E)$ is written as $G.Adj$.It is an array that contains a list of vertices adjacent to the vertex in the index. In other words, let $u$ be a vertex of $G$. $G.Adj[u]$ will then consist of all the vertices that are adjacent to $u$ in $G$.
An adjacency matrix is a matrix defined in the following way. Let $1, 2, ... , |V|$ be any arbitrary ordering of the vertices in $G$. The $a_{ij}th$ element of the adjacency matrix that represents $G$ has a value of $1$ if there exists an edge between the vertices $i$ and $j$ (i.e $(i, j) \in E$) and has a value of $0$ otherwise.