Graphs is used to solve the most challenging and complex programming problems. If we are good with the concept of Graph data structure, many problems becomes easier to solve.
What is a graph data structure
A graph is a data structure which is represented as finite set of node and edges. These nodes are called vertices and these vertices are connected by edges. Let us say that we have 5 nodes A,B,C,D,E. And lets say all of these nodes are connected via several edges to form the resultant graph in the below image.
By Looking at the set of edges we can see how the vertices are connected together.
V= {A, B, C, D, E};
E = {{A,B}, {B.E}, {E, D}, {D, A} , {A,C}, {C,E}, {C, E}}
Real Life Applications of Graph
- Google Maps – Has a massive collection of nodes which are contained in Graph.
- Social Network: It assumes that every person on the network is a node. All the friendships on the Facebook forms the edges on the graph.
- In the social media if we look at the profile of some person and if we want to calculate the number of friends between us and the other person, the Facebook calculates the number of paths between us and person x. To find the friends suggestion, the Facebook uses the graph structure to find the next friend. Eg, in figure the Facebook will suggest Anoop, Sid and Nick in the Friends suggestion list of Ravi. As Ravi is friends with Vikram, And Vikram has these other Friends.
- Facebook also uses very popular algorithm known as Edge Rank algorithm. If you care fully notice the Facebook feeds you may notice that you have more feeds from some particular friends. These are the friends whose posts you have already liked or commented in the past. This happens because Facebook assigns weight to every edge in the Graph. This weight may depend on many parameters like likes or comments.
Basic Terminologies for Graphs:
Adjacent Vertices: Vertices that are directly connected with each other through edges are called adjacent vertices.
In the graph shown in Figure 3, we can say that (0, 1) (0, 3) (1,2) (3,4) are some set of adjacent vertices.
Degree: The number of edges connected to a node is known as degree of a node. The degree of node 0 is 2, degree of node 1 is 2, the degree of node 3 is 3. The degree of node 5 , 6 and 4 are 1.
In the Figure 4 as you can see the edges between 0 and 1 as well as 0 and 4 are unidirectional. A unidirectional edge means that we can move from one node to another and not in the reverse way.
These kind of graphs are good examples of social media like Twitter and Instagram. In these social media platforms one user can follow other user but reverse may not be true.
In case of unidirectional graphs or the graphs which have directions, each graph has In degree and out degree. The in degree denotes the number of edges terminating on a node. The out degree denotes the number of edges originating at the node.
Path: The set of edges that constitute the route from one vertex to another.
Connected Graphs: Connected graphs are the graphs where we start from one node we reach all the nodes of a graph as shown in figure 5
In case of Figure 3 we cannot reach the node 5 and 6 if we start from node 0.
Sub Graph
A part of the graph. Suppose 0 is the sub graph of the whole graph. Similarly, 0 and 4 as well as the edge between two nodes is a sub graph. The only part you cannot independently take from a Graph to form Sub graph is an edge.
Connected Components
The components in a graph where all the nodes are connected to each other are connected components. As seen in the figure 6, the sub graph made by nodes 0,1,2,3,4 and 5 and their edges is a connected component. On the other hand the sub graph made by 5 and 6 nodes and their edges is another connected component.
In the connected component it is possible to traverse all the nodes using the vertices of the graph.
Trees: Output of graph traversal as shown in figure 7.
Forests: Collection of trees.
There are two trees in the graph traversal in Figure 7.
Minimum Spanning Tree
Let us say that we have a weighted graph as shown in below figure. Believe that the weight of each edge represents the distance between two nodes in miles. Let us say that we want to find a way that traverses all the nodes of the graph in such a manner that the minimum distance is actually considered.
We have to somehow skip the edge between node A and B as it carries the maximum weight. We will start from node C, go to node D. Finally taking both nodes A and E. And Terminating on node E as shown in the figure on right hand side.
Conclusion:
In this article I have discussed graphs and some of its practical use cases in our day to day life. I have also discussed about the properties of the Graphs like path, vertices, connected and disconnected graphs. In the next article I will discuss how to represent Graphs in computer memory.
Leave a Reply