Graph is . acollection of nodes where the nodes are connected using edges.

It can have directed edges (directed graphs) and it can have both way edges (undirected graphs).epth

If you want to know if there is a path between two nodes:

two ways to do that:

1. Depth First Search (DFS)
2. Breadth First Search (BFS)

Breadth First Search:

https://www.youtube.com/watch?v=QRq6p9s8NVg

You go level by level and mark the nodes as visited and add all the children of every node in a queue.

Then take one node out at a time from the queue and mark those as visited annd again add their children to the queue and so on.

Time Complexity : O(V+E)

Depth First Search (DFS):

https://www.youtube.com/watch?v=iaBEKo5sM7w

You start with one node and mark it as visited and add it to the stack.

If it has children, you pick any one of the child and mark that as visited and add it to the stack.

You keep going deeper via child to child and adding them to the stack.

Start popping when the node doesnt have any unvisited children left.

Time Complexity : O(V+E)

It visits every vertex in the graph and checks every edge for the node hence its V+E.