Sunday, August 16, 2020

Graph Representations & Graph Traversals

Graphs have two primary components known as i) vertex and ii) a pair of Vertex bonding to form an edge.

Graphs can be represented in two different ways.
  1. Adjacency Matrix : The Distance between two vertices are represented in a row X column format.
  2. Adjacency List: An Array of linked Lists are maintained representing each node and its respective edges with other nodes.

The method to traverse a Graph is as follows: 
  1. Breadth First Traversal/Search
  2. Depth First Traversal/Search

Breadth First Traversal(BFS):


Breadth First Traversal is used to traverse all the nodes in a graph, and the order of it is determined using a Queue structure.


Depth First Traversal(DFS):


Depth First Traversal uses a a stack/recursive method approach to traverse all the nodes in a graph.

DFS can be implemented using a recursive method.
This post was originally drafted on 13th Feb 2018.