Graphs have numerous applications out of which Social Networks is quite popular.
In this Article I have tried to present a simple use case to demonstrate how to represent it using Adjacency Lists. Idea is to help you get started with Graphs.
Since we are discussing friendships the Graph used is an undirected one.
Consider a simple case, we have a really small town with only 6 people. The figure below shows how they are connected to each other. So for example Ankur is friend with Dikshit and Reena.
So how can we capture this data?
A Graph is a set of Vertices and Edges. In our case the people are the vertices and the relationship between them are the Edges.
There are two popular ways to represent a Graph. One is the Adjacency Matrix approach and another one is the Adjacency List approach. The second one is more popular because of it’s efficiency. If you need more details on these two representations kindly visit the following links Adjacency Matrix & Adjacency List
Please drop a comment if you want me to explain these approaches as well. For now I want to keep things short and simple.
In the List approach we maintain an Array of Vertices and each Vertex in the Array has a Linked List which points to it’s Edges. See the figure below. I have shown one of the Linked List that shows Ankur’s connections.
Now let’s see how to implement this using C. If you are not quite familiar with Arrays and Linked List I will recommend you to visit Wiki for the same. I have written sample programs for Array and Linked List here and I am planning to explain them soon.
Continue reading “Basic Graph Data Structure to demonstrate Friendships”
Why Android 