Graph Data Structure in C#

We have discussed the linked list, Stack, Queue in our previous article. In this article, we will implement a Graph Data Structure in C#.

What is a Graph Data Structure?

In the Graph data structure, each  Node can be connected to many other Nodes. It can be compared with a road network. Many cities are connected with different routes. We call these routes as edges in Graph Data structure. Graph Data structure widely used to solve many real-world problems. 

It is used to solve many real-world problems. Take an example of a social media network each one connected to many others. This is a good example to visualize this data structure.

Implementation of Graph Data Structure in C#

Let’s talk about implementation. Since each node in the Graph can be connected to all the vertices of the graph we will have many edges. So for storing edges we can use the 2D matrix. Also, the edges in the graph can be unidirectional or bidirectional. Here we are assuming that the edges are bidirectional.

Below is the graphical representation of the Graph data structure. Each node connected to other nodes.In the right of the representation edges of the graph is shown. Example : Edge 0 1 meaning there exist an edge from vertex 0 to vertex 1.There are total 9 edges in this example.

Traversing Graph Data Structure

In this section, we will discuss the traversing graph. There may be many different ways to travel from one node to another node. But here we will try to cover two common method Depth First Search and Bread First Search.

The below code is the main method We will be printing DFS & BFS Traversal of a graph to the console. Here we will cover the disconnected graph also while printing DFS& BFS.

        public static void Main(string[] args)
        {
            int v, e;

            Console.WriteLine("Enter Number of vertices");
            int.TryParse(Console.ReadLine(), out v);

            Console.WriteLine("Enter Number of edges");
            int.TryParse(Console.ReadLine(), out e);

            int[] vertices = new int[v];
            int[,] edges = new int[v, v];
            bool[] visited = new bool[v];

            Console.WriteLine("Enter Edges");
            for (int i = 0; i < e; i++)
            {
                int s, d;
                string[] input = Console.ReadLine().Split(' ');
                int.TryParse(input[0], out s);
                int.TryParse(input[1], out d);
                edges[s, d] = 1;
                edges[d, s] = 1;

            }

            Console.WriteLine("DFS");
            //for loop to handle disconnected Graph
            for (int i = 0; i < v; i++)
            {
                if (!visited[i])
                    DFS(edges, v, visited, i);
            }


            for (int i = 0; i < v; i++)
            {
                visited[i] = false;
            }

            Console.WriteLine();
            Console.WriteLine("BFS");
            //for loop to handle disconnected Graph
            for (int i = 0; i < v; i++)
            {
                if (!visited[i])
                    BFS(edges, v, visited, i);
            }


        }

DFS

In Depth First Search we will be starting from one node & traversing in one branch covering all the nodes there before coming to the next branch. There may be different variations based on Pre Order, In order, or Post Order.

Below Code shows the DFS traversal of the Graph. Variables edges, vertices, and visited will store edges of the graph, all the vertices & visited nodes respectively. We are starting with a node passed into the function with variable si . We are running a for loop iterating over each vertex & marking each node visited, also for each node recursively calling DFS functions.

        public static void DFS(int[,] edges, int v, bool[] visited, int si)
        {
            visited[si] = true;
            Console.Write(si + " ");

            for (int i = 0; i < v; i++)
            {
                if (i == si)
                    continue;
                if (!visited[i] && edges[si, i] == 1)
                {
                    DFS(edges, v, visited, i);
                }
            }
        }

BFS

In Breadth First Search we will be covering all the nodes at the same level or at the same depth, first before moving to the next level. Here we will be using a queue for storing all the edges of the node that we are currently iterating i.e currentVertex.

        public static void BFS(int[,] edges, int v, bool[] visited, int si)
        {

            Queue<int> queue = new Queue<int>();
            queue.Enqueue(si);
            visited[si] = true;
            while (queue.Count != 0)
            {
                int currentVertex = queue.Dequeue();
                Console.Write(currentVertex + " ");
                for (int i = 0; i < v; i++)
                {
                    if (i == currentVertex)
                        continue;
                    if (!visited[i] && edges[currentVertex, i] == 1)
                    {
                        queue.Enqueue(i);
                        visited[i] = true;
                    }
                }

            }
        }

Below is the output for the example.