Over the next few chapters, we will learn and analyse the following two graph algorithms:
- Breadth First Search (BFS)
- Depth First Search (DFS)
Representation of Graphs
In computer science, it is common to represent graphs in one of two ways.
- Adjacency List
- Adjacency Matrix
An adjacency list of a graph is written as .It is an array that contains a list of vertices adjacent to the vertex in the index. In other words, let be a vertex of . will then consist of all the vertices that are adjacent to in .
An adjacency matrix is a matrix defined in the following way. Let be any arbitrary ordering of the vertices in . The element of the adjacency matrix that represents has a value of if there exists an edge between the vertices and (i.e ) and has a value of otherwise.
The following figure shows both the adjacency list and adjacency matrix for a graph: