Hello friends, in this this article I will write a program to create a graph data structure similar to one shown in figure 1. Though there are direct to use data structures provided by most of the programming languages like LinkedList, Dictionary or arrays.
But there is no direct data structure provided in C# to create a graph.
Lets try to create and represent the below figure in the computer memory by writing a C# program.
As you can see in the above figure all the edges are bidirectional in the Graph. The way you can represent the above graph in the computer memory is as below:
0 -> 1,3
1 -> 2,0
2 -> 1,3
3 ->2,4,0
4 -> 3
I believe the above representation can clear some doubts. The node 0 has two children i.e 1 and 3. Since it is bidirectional, the you can see the edge 0 is present in the child list of nodes 1 and 3.
To write a program to represent it as below we have to follow the adjacency list approach.
In this approach we take an array of linked list. The index of the array represents the parent node and we will keep adding the child nodes in the linked list as shown in the code snippet below.
And if the edge is bidirectional we will reverse the role of parent and child node.
The AddEdge method takes two nodes between which we have to add the edge.
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph(5);
graph.AddEdge(0, 1);
graph.AddEdge(0, 3);
graph.AddEdge(1, 2);
graph.AddEdge(2, 3);
graph.AddEdge(3, 4);
Console.WriteLine("The graph adjacency list representation:");
graph.PrintAdjanceyList();
Console.Read();
}
}
public class Graph
{
LinkedList<int>[] linkedListArray;
public Graph(int v)
{
linkedListArray = new LinkedList<int>[v];
}
/// <summary>
/// The method takes two nodes for which to add edge.
/// </summary>
/// <param name="u"></param>
/// <param name="v"></param>
/// <param name="blnBiDir"></param>
public void AddEdge(int u, int v, bool blnBiDir = true)
{
if (linkedListArray[u] == null)
{
linkedListArray[u] = new LinkedList<int>();
linkedListArray[u].AddFirst(v);
}
else
{
var last = linkedListArray[u].Last;
linkedListArray[u].AddAfter(last, v);
}
if (blnBiDir)
{
if (linkedListArray[v] == null)
{
linkedListArray[v] = new LinkedList<int>();
linkedListArray[v].AddFirst(u);
}
else
{
var last = linkedListArray[v].Last;
linkedListArray[v].AddAfter(last, u);
}
}
}
public void PrintAdjanceyList()
{
//Taversing over each of the vertices
for (int i = 0; i < linkedListArray.Length; i++)
{
//Printing the vertices
Console.Write(i + "->");
//Printing the linked list of vertex
foreach (var item in linkedListArray[i])
{
Console.Write(item + ",");
}
Console.WriteLine();
}
}
}This is such a simple way to create or represent a Graph Data structure in the memory.
This was the representation of Graph with numeric node, how will you represent a Graph with string node. Think about it and I will discuss in the next article.