Basic Graph Data Structure to demonstrate Friendships

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.

Friend_Graph.png

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.

AL

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”

Data Structures using C

Lately I have been implementing the standard Data Structures in Computer Science using the C Programming Language. These have the minimal functions to demonstrate the basic usage.

Going forward I will be adding more and also try to explain these.

As of now the list includes:

In the Binary Search Tree program the delete node functionality hasn’t been implemented fully.

The basic algorithm has been presented though which is as follows:

Algorithm to delete a Node from Binary Search Tree (BST)

1. Find the Node in the BST.
2. If Node is a Leaf, then go ahead and delete it.
3. If not find the “in-order successor / predecessor”. Say we use the in-order successor Node_S.
4. Swap the node with Node_S. Now delete Node_S and if it has any children then update the pointers.

For Step 3 we can find wither the minimum node in the right sub tree or the maximum node in the left sub tree.