Graph

Graph is used to represent the flow of computation or elements that share connections. Examples : Google maps, Social Network , Resource Allocation Graph in operating system

Graph-related questions are very common during Interview of product companies like Google, Facebook, Uber etc. One thing all these companies have in common is their heavy reliance on the graph data structure.

• Recognising a graph problem : The first key to solving a graph related problem is recognising that it is a graph problem. Nearly all graph problems will somehow use a grid or network or path in the problem, but sometimes problem has been expressed indirectly in a form of real life problem. In such situation, we need to extract all the relevant detail and transform the problem into graph problem.
• Its important to undestand the properties, implementation and applications of Depth First Search(DFS) and the Breadth First Search(BFS) traversal of graphs. We can solve several graph problems using these two traversals.

Understanding the idea of Graph Representation is also an important part in solving graph problems. There are two types of representation :

• Adjacency List
• Adjacency Matrix