C# program to Depth First Search (DFS)

Here's an example of a C# program that illustrates Depth First Search (DFS) algorithm on a graph:

using System;
using System.Collections.Generic;

class Graph
{
    private int numVertices;
    private List> adjacencyList;

    public Graph(int vertices)
    {
        numVertices = vertices;
        adjacencyList = new List>(numVertices);
        for (int i = 0; i < numVertices; i++)
        {
            adjacencyList.Add(new List());
        }
    }

    public void AddEdge(int source, int destination)
    {
        adjacencyList[source].Add(destination);
        adjacencyList[destination].Add(source);
    }

    public void DFS(int startVertex)
    {
        bool[] visited = new bool[numVertices];
        DFSRecursive(startVertex, visited);
        Console.WriteLine();
    }

    private void DFSRecursive(int currentVertex, bool[] visited)
    {
        visited[currentVertex] = true;
        Console.Write(currentVertex + " ");

        List neighbors = adjacencyList[currentVertex];
        foreach (int neighbor in neighbors)
        {
            if (!visited[neighbor])
            {
                DFSRecursive(neighbor, visited);
            }
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph(6);

        // Adding edges to the graph
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);

        // Performing Depth First Search (DFS) on the graph
        Console.WriteLine("Depth First Traversal:");
        graph.DFS(0);
    }
}

In this program, we have a Graph class that represents a graph data structure. It has a constructor to initialize the number of vertices and an adjacency list to store the edges between vertices.

The AddEdge method is used to add an edge between two vertices. It takes the source vertex and destination vertex as input and adds them to each other's adjacency list.

The DFS method performs the Depth First Search algorithm. It takes a start vertex as input and performs DFS starting from that vertex. It uses a boolean array visited to keep track of visited vertices. The method calls a private recursive method DFSRecursive to perform the DFS traversal. The recursive method visits the current vertex, marks it as visited, and recursively visits its unvisited neighbors.

In the Main method, we create an instance of the Graph class with 6 vertices and add edges to the graph. We then call the DFS method with a start vertex of 0 to perform DFS on the graph.

Depth First Traversal:
0 1 3 4 2 5

This demonstrates the implementation of Depth First Search (DFS) algorithm in C#. The program performs DFS on the graph starting from vertex 0 and outputs the traversal sequence. The DFS traversal visits all vertices in the graph in depth-first order.