How does Netflix recommend you movies?
Ever wondered how does netflix recommend movies? How does Facebook/LinkedIn shows people you know kind of recommendations? The simple answer is Graph data structure. Graphs are way of representing connection between certain objects with finite number of nodes. Basically, nodes and connections together make graph. And this graph is totally different from the graph we studied in mathematics. Graphs are use for social media recommendations, mapping and routing algorithms and other optimisations.
keywords used in graphs are given below.
Vertex: A node or pointer from which graph is formed.
Edge: connection between nodes is edge.
Un-weighted graphs: un-weighted graphs have no value associated with it.
Weighted graphs: It has got values associated with it.
Directed graphs: The graphs possessing one way direction between vertices and can’t traverse are called directed graphs.
Undirected graphs: The graphs possessing two way direction between vertices, more like two way routes are called undirected graphs.
Ways of representing graphs;
Adjacency Matrices: Adjacency matrices are N*N matrix where each true value indicates connection between two vertices.
Adjacency Lists: In Adjacency Lists, every node will be storing adjacent vertices into a list.
Graph Traversal
Traversing the graphs means checking or updating each node in graph. It helps in finding shortest path, gps navigation, closest matches and many more. Two common ways of traversing graph are given below;
Depth First Search (DFS): In Depth First Search, we start from one root node and traversing deep into one connection before visiting the other connections. Here we go deep first and then go wide. DFS uses Stack Data structure to keep track of the next location to visit. This algorithm suits when a target node is far from the source.
Even through above diagram is binary search tree, it gives overview about how DFS works. All trees are graph but not all graphs are trees. The given tree diagram gives a brief idea about how DFS works. It will focus on one root node i.e “A” then it will go to its sibling “B” and then its children “D” and “E”. After this it will go wide i.e “C” and its children “F” and “G”.
Breadth First Search(BFS): In Breadth First Search, we focus on root node and its sibling nodes before going to any of their children. Here we go wide first and then go deep.BFS uses Queue Data structure to keep track of the next location to visit. This algorithm suits when a target node is closer to the Source.
The given tree diagram gives a brief idea about how BFS works. It will focus on one root node i.e “A” then it will go to its sibling “B” and “E”. After this it will traverse through its child “C”, “D” and “F”, “G”, wide and then depth.