C# Coding Test Course, Depth First Search

Hello, everyone! Today, we will delve deeply into the Depth-First Search (DFS) algorithm for preparing coding tests using C#. Depth-First Search is an efficient algorithm used to explore tree or graph structures. In this article, we will explain the basic concepts of DFS, how to implement it, and how to apply it through real problems step by step.

1. What is Depth-First Search (DFS)?

Depth-First Search (DFS) is a search technique that visits all nodes of a graph. This algorithm explores as deeply as possible from one node before returning to the most recently visited node when there are no further nodes to explore, in order to explore other paths.

1.1 Basic Principles

DFS can be implemented using a stack or conveniently handled using a recursive function. The fundamental principles of DFS are as follows:

Select a starting node.
Keep track of visited nodes.
Choose an unvisited adjacent node and recursively call DFS.
If there are no more nodes to visit, return to the previous node.

2. Time Complexity of DFS

The time complexity of DFS is O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because it visits all nodes once and checks all edges once. The space complexity depends on the stack used and is O(V) in the worst case.

3. Implementing DFS

Now, let’s implement DFS using C#. The following code represents a graph in the form of an adjacency list and implements DFS.


using System;
using System.Collections.Generic;

class Graph
{
    private int V; // Number of vertices
    private List[] adj; // Adjacency list

    public Graph(int v)
    {
        V = v;
        adj = new List[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w); // Add node w to node v
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V]; // Visited nodes array
        DFSUtil(v, visited); // Recursive call
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true; // Visit current node
        Console.Write(v + " "); // Print current node

        foreach (int neighbor in adj[v])
        {
            if (!visited[neighbor]) // If adjacent node has not been visited
            {
                DFSUtil(neighbor, visited); // Recursive call
            }
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph g = new Graph(4);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("Depth First Traversal (starting node 2):");
        g.DFS(2);
    }
}

3.1 Code Explanation

The above code has the following structure:

Graph Class: Contains the number of vertices and the adjacency list.
AddEdge Method: Adds an edge between two nodes.
DFS Method: Initializes the visited array for DFS traversal and calls DFSUtil.
DFSUtil Method: Recursively performs DFS and prints the visited nodes.

4. Algorithm Problem: Counting Islands

Now, let’s solve a real problem using DFS. The problem is ‘Counting Islands’.

4.1 Problem Description

The given 2D array consists of water (0) and land (1). An island is a collection of land (1), formed by land that is connected to each other. An island is defined as a collection of land that is adjacent either vertically or horizontally. Write a program that counts the number of islands in this 2D array.

4.2 Approach

To solve this problem, we will perform the following steps:

Traverse the 2D array and call DFS when land (1) is found.
Within DFS, visit all connected lands and increase the count.
After exploring all lands, return the number of islands.

4.3 C# Code Implementation


using System;

class IslandCounter
{
    private int[,] grid;
    private int rows, cols;

    public IslandCounter(int[,] grid)
    {
        this.grid = grid;
        rows = grid.GetLength(0);
        cols = grid.GetLength(1);
    }

    public int CountIslands()
    {
        bool[,] visited = new bool[rows, cols];
        int count = 0;

        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (grid[i, j] == 1 && !visited[i, j])
                {
                    DFS(i, j, visited); // Call DFS
                    count++;
                }
            }
        }
        return count;
    }

    private void DFS(int i, int j, bool[,] visited)
    {
        if (i >= rows || i < 0 || j >= cols || j < 0 || grid[i, j] == 0 || visited[i, j])
            return;

        visited[i, j] = true; // Mark as visited

        // Call DFS in 8 adjacent directions
        DFS(i + 1, j, visited);
        DFS(i - 1, j, visited);
        DFS(i, j + 1, visited);
        DFS(i, j - 1, visited);
        DFS(i + 1, j + 1, visited);
        DFS(i - 1, j - 1, visited);
        DFS(i + 1, j - 1, visited);
        DFS(i - 1, j + 1, visited);
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[,] grid = new int[,]
        {
            { 1, 1, 0, 0, 0 },
            { 0, 1, 0, 0, 1 },
            { 0, 0, 0, 1, 1 },
            { 0, 0, 0, 0, 0 },
            { 1, 0, 1, 0, 1 }
        };

        IslandCounter counter = new IslandCounter(grid);
        Console.WriteLine("Number of islands: " + counter.CountIslands());
    }
}

4.4 Code Explanation