I’ve been a speaker to a London Algorithms Meetup and the subject was Graph Theory.
In the repo there are two branches: master and solution.
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
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
I hope you enjoyed this article and happy coding!