<aside> <img src="/icons/help-alternate_gray.svg" alt="/icons/help-alternate_gray.svg" width="40px" /> Most, if not all, of the topics covered in this lecture are pretty much recap of what we covered in COE428. For reference: COE428 - Algorithms and Data Structures — most of which will be copy-pasted in here.
</aside>
A graph $G$ is a pair $(V,E)$ where the element of $V$ are called vertices and the element of $E$ are called edges. The number of vertices is denoted by $n = |V|$ and edges by $m = |E|$.
Figure 2.1 Example of a graph.
Consider the graph in Figure 2.1. The graph has the following vertices and edges:
A graph can be categorized into one of two types depending on the edge type:
Figure 2.2a Undirected graph.
Directed graph: Edges with direction — directed edges are ordered pair of vertices, such that $\langle u,v \rangle$ and $\langle v,u \rangle$ are two different edges.
Figure 2.2b Directed graph.
We can choose between two standard ways to represent a graph $G = (V,E)$.
The adjacency list is a node indexed array of list It has a space proportional to $m+n$.
Figure 2.3a Example of an adjacency list.
<aside> <img src="/icons/help-alternate_gray.svg" alt="/icons/help-alternate_gray.svg" width="40px" /> Note that in an adjacency list, the order doesn't matter, meaning we could have listed the vertex in any order.
</aside>
For reference, if we look at the vertex $2$:
Figure 2.3b The vertices adjacent to 2
The adjacency matrix is $n$-by-$n$ matrix with $A_{uv} = 1$ if $(u, v)$ is an edge. It has a space proportional to $n^2$.
Figure 2.4a Example of an adjacency matrix.
For reference, if we look at vertex $2$:
Figure 2.4b The vertices adjacent to 2.
We will go over a few graph terminologies, some of which you should be familiar with.
A path is a sequence of vertices, such that consecutive vertices are adjacent.
Figure 2.5a A path.