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.

BFS(source) 1. Creating nodes(elements in visited array) equal to the no. of vertices(V) visited= [False] * V 2. Marks the source node as visited. visited[source]= True 3. Enqueue source in the Queue 4. While Queue is not empty() i. print(Queue.front()) and Pop Queue's front element ii. Iterate through the list for visited nodes (i) iii. If Node is not visited a. mark the node i as visited b. Update the node i on the Queue

Depth First Traversal(DFS):

Depth First Traversal uses a a stack/recursive method approach to traverse all the nodes in a graph.
DFS(source) 1. Creating nodes(elements in visited array) equal to the no. of vertices(V) visited= [False] * V 2. Marks the source node as visited. visited[source]= True 3. Push the source node in the stack 4. While Stack is not empty() i. print(Stack.front()) and Pop Stack's front element ii. Iterate through the list for visited nodes (i) iii. If Node is not visited a. mark the node i as visited b. Update the node i on the Queue
DFS can be implemented using a recursive method.

This post was originally drafted on 13th Feb 2018.