I’ve been a speaker to a London Algorithms Meetup and the subject was *Graph Theory*.

Here there is the link to the repository: https://github.com/LondonAlgorithms/graph_theory with the javascript code.

I have created a pairing exercise with specs to guide through the creation of an undirect Graph by using an adjacency list. After all the vertices and edges have been added to the Graph, the exercise requires to visit a Graph with a Breadth First Search Algorithm. In the repo I have written some Javascript tests to follow during the code development. You can run tests by opening *SpecRunner.html*.

In the repo there are two branches: master and solution.

As you might expect, solution branch contains the complete javascript code.

After a brief introduction to what is a **Graph** and which are the use cases, I’ve explained how to build a graph with an **Adjacency List** and then I’ve shown which are the *Graph Traversal Algorithms*: *Depth First Search* and *Breadth First Search*.

## What is a Graph

Graph is a non linear data structure, it contains a set of points known as nodes (or vertices) and set of linkes known as edges (or Arcs) which connects the vertices.

Graphs are used to represent networks of communication, transportation system, website, maps, social networks, chemistry, games etc.

## How to build a Graph

To build a Graph we might use an Adjacency List.

An Adjacency List associates each vertex in the graph with the collection of its neighboring vertices. It uses an hash table to associate each vertex in a graph with an array of adjacent vertices.

## How to visit a Graph

There are two search algorithms we can perform on a graph:

- depth first search (Use a stack – LIFO)
- breadth first search (Use a queue – FIFO)

Depth-first search involves following a path from the beginning vertex until it reaches the last vertex, then backtracking and following the next path until it reaches the last vertex, and so on until there are no paths left.

There are two ways to visit a Graph with DFS:

- iterative solution with a stack
- recursive solution

Keep in mind, any recursive algorithm can be translated to an iterative one by using a stack

### Recursive Solution

Unlike trees, graphs may contain cycles, so we may come to the same node again.

To avoid processing a node more than once, we use a boolean **wasVisited** stored on the Vertex.

DFS-recursive(G, s): mark s as visited for all neighbours w of s in Graph G: if w is not visited: DFS-recursive(G, w)

### Iterative Solution with a Stack

DFS-iterative (G, s): //Where G is graph and s is source vertex let S be stack S.push( s ) //Inserting s in stack while ( S is not empty): //Pop a vertex from stack to visit next v = S.top( ) S.pop( ) mark s as visited. //Push all the neighbours of v in stack that are not visited for all neighbours w of v in Graph G: if w is not visited : S.push( w )

## Breath First Search

A breadth-first search moves through a graph layer by layer, first examining layers closer to the first vertex and then moving down to the layers farthest away from the starting vertex.

For breadth first search **we don’t use recursion**, Breadth-first traversal traditionally **uses a queue** as helper data structure

Define a queue Add to queue the starting vertex Visit the starting vertex While there is a vertex in the queue Get the next vertex to visit from the queue Get vertex neighbours For each vertex neighbour if the neighbour has not been visited → visit neighbour add to the queue

## Online BFS algorithm

Link: https://www.cs.usfca.edu/~galles/visualization/BFS.html

I hope you enjoyed this article and happy coding!