How to implement depth-first search algorithm in C#

How to implement the depth-first search algorithm in C

#Depth First Search (DFS) is a commonly used graph traversal algorithm, which is used One of the algorithms for traversing or searching a tree or graph. In C#, we can implement the depth-first search algorithm recursively. This article will introduce how to implement the depth-first search algorithm in C# and give relevant code examples.

1. Algorithmic Thought

The depth-first search algorithm starts from a vertex, gradually traverses downwards until it reaches the deepest point, then backtracks to the previous vertex, and then selects the next An adjacent vertex that has not been visited continues to be traversed until all vertices have been visited. The specific implementation can be achieved using recursion, by continuously calling functions recursively.

2. Algorithm implementation

Below we use a simple example to illustrate how to implement the depth-first search algorithm in C#. Suppose we have an adjacency matrix of a connected graph, and our goal is to start from a given starting vertex and traverse the entire graph to find all vertices. The following is a code example that implements a depth-first search algorithm:

using System;
using System.Collections.Generic;

namespace DFSExample
{
    class Program
    {
        static int[][] graph;
        static bool[] visited;

        static void Main(string[] args)
        {
            // 初始化邻接矩阵
            InitializeGraph();

            // 初始化visited数组
            visited = new bool[graph.Length];

            // 从顶点0开始遍历
            DFS(0);

            Console.ReadLine();
        }

        static void InitializeGraph()
        {
            // 定义邻接矩阵
            graph = new int[][]
            {
                new int[] {0, 1, 1, 0, 0, 0},
                new int[] {1, 0, 0, 1, 1, 0},
                new int[] {1, 0, 0, 0, 0, 1},
                new int[] {0, 1, 0, 0, 0, 0},
                new int[] {0, 1, 0, 0, 0, 0},
                new int[] {0, 0, 1, 0, 0, 0}
            };
        }

        static void DFS(int vertex)
        {
            // 标记当前顶点为已访问
            visited[vertex] = true;
            Console.WriteLine("Visited vertex: " + vertex);

            // 遍历当前顶点的邻接顶点
            for (int i = 0; i < graph.Length; i++)
            {
                if (graph[vertex][i] == 1 && !visited[i])
                {
                    DFS(i);
                }
            }
        }
    }
}

This code implements a simple depth-first search algorithm. We first define an adjacency matrix to represent the connectivity of the graph. Then a visited array is defined to record the visit status of each vertex. In the DFS function, the current vertex is first marked as visited and the value of the current vertex is output. Then traverse the adjacent vertices of the current vertex. If the adjacent vertices have not been visited, continue to call the DFS function recursively until all vertices have been visited.

3. Running results

Run the above code, you can get the following output results:

Visited vertex: 0
Visited vertex: 1
Visited vertex: 3
Visited vertex: 4
Visited vertex: 2
Visited vertex: 5

These output results indicate that starting from the starting vertex 0, according to The depth-first search algorithm visits each vertex in sequence.

Summary

This article introduces how to implement the depth-first search algorithm in C# and gives relevant code examples. Depth-first search algorithms can be easily implemented recursively to traverse a graph or tree. Depth-first search algorithms are widely used in many application scenarios, such as graph connectivity judgment, topological sorting, etc. Readers can make further extensions and applications based on the code examples in this article.

The above is the detailed content of How to implement depth-first search algorithm in C#. For more information, please follow other related articles on the PHP Chinese website!