Graphs Chapter 1 | Traverse through Graphs

When we learn data structures we come across with

• Linear data structures (arrays, structs, linked list)
• Non linear data structures (Trees, Graphs)

In trees we have Binary trees, Left Right Trees, Red & Black Trees, AVL Trees etc.

Trees Vs Graphs

• Tree has Hierarchical structure but Graphs does not
• Graphs can have many connections, any connection or Zero connections
• Trees always have directed edges but Graphs can have Directed edges or Undirected edges

In here A->B is Directed edge and A->C is undirected edge.

Lets see how to Process Through Graphs

There are few things we need to know when we are going to process through graphs

To move through Graphs there are mainly 2 methods

1. Breadth First Search : Start at one place and clear the ones next to it and go to next node
2. Depth First search : Start at one place and go by one path and reach to end the process that node and come by processing until you found another path

Breadth First Search

Step 1 : A is the source node. So A is Discovered and A is added to the Queue

Step 2 : Find all adjacency node to A and add those to queue and make them Grey.

Step 3 : Now the process of A is over so we set A to black and go to the next node giving the queue(B is next). A is removed from the Queue.

So step 2 and step 3 will repeat untill Queue ios empty.

Please have a look at how Breadth first search works for following Graph.

I am still learning new things sorry for not alligning the Gif

Complexity : O(V + αE) In here we need to vist nodes and one or all edges. For search node O(V+E) | Traverse Θ(V+E)

Use : Finding shortest path

Depth First Search

In here what we do is we start from source node and go by discovering and when we found the death end we process the node.

White path theorem : From start node(Grey) we can go to white nodes only we can not go to Grey nodes or Black nodes

We can only go to B if B is white only and like wise we can go to D. If B is grey we can not go to C or D.

Lets try to go through following graph through Depth first search

Step 1 : Start from source node A. Add A to stack and make it as Grey.

Step 2: Go to adjacency node C. make C as Grey and add C to Queue

Step 3: Go to adjacency node D. make D as Grey and add D to Queue

Step 4: Go to adjacency node F. make F as Grey and add F to Queue

Step 5: There is no wite nodes adjacency to F node. So F is dead end, F is processed and make it as black and remove from stack.

Step 6 : Get the next node in stack, D has adjacency node which is E. So go to E node and make it Grey and add to stack.

Step 7 : As you can see E also a dead end. So it will process and make it to Black like wise we repeat the process until Stack is empty.

Lets see how it works 😈

Complexity : O(V + αE) In here we need to vist nodes and one or all edges. For search node O(V+E) | Traverse Θ(V+E)

Use : Finding strongly connected components

I will end this chapter with this. Next chapter will be on how to find the shortes path from given Graph. In there we will discuss on Dijkstra’s algorithm | Bellman–Ford Algorithm | Floyd Warshall Algorithm

Graphs Chapter 2| Finding shortest path