How to write a breadth-first search algorithm using C#

How to use C# to write a breadth-first search algorithm

Breadth-First Search (BFS) is a commonly used graph search algorithm, used in a Breadth-wise traversal in a graph or tree. In this article, we will explore how to write a breadth-first search algorithm using C# and provide concrete code examples.

1. Algorithm Principle
   The basic principle of the breadth-first search algorithm is to start from the starting point of the algorithm and expand the search range layer by layer until the target is found or the entire graph is traversed. It is usually implemented through queues.
2. Code implementation
   The following is a sample code for writing a breadth-first search algorithm using C#:

using System;
using System.Collections.Generic;

public class BFS
{
    public class Node
    {
        public int value;
        public List<Node> neighbors;

        public Node(int v)
        {
            value = v;
            neighbors = new List<Node>();
        }
    }

    public static void BFSAlgorithm(Node start)
    {
        Queue<Node> queue = new Queue<Node>();
        HashSet<Node> visited = new HashSet<Node>();

        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            Node node = queue.Dequeue();
            Console.Write(node.value + " ");

            foreach (Node neighbor in node.neighbors)
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        Node node1 = new Node(1);

        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.neighbors.Add(node2);
        node1.neighbors.Add(node3);

        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node2.neighbors.Add(node4);
        node2.neighbors.Add(node5);
        node3.neighbors.Add(node6);

        BFSAlgorithm(node1);
    }
}

In the above code, we first define a NodeClass, used to represent nodes in the graph. A node contains a value and a list of neighbors. BFSAlgorithmThe function implements the breadth-first search algorithm, which uses a queue to store nodes to be processed and a collection to record visited nodes. The algorithm starts from the starting point, adds it to the queue and visited set, and then iteratively processes the nodes in the queue and adds its neighbor nodes to the queue and visited set. Finally, we created a simple graph in the Main function of the program and called the BFSAlgorithm function to search.

3. Example output
   The output of the above code is: 1 2 3 4 5 6. Indicates that the breadth-first search algorithm traverses the nodes in the graph in order starting from 1.

Summary:
This article introduces how to use C# to write a breadth-first search algorithm and gives detailed code examples. By using queues and collections to implement the breadth-first search algorithm, we can traverse breadth-wise in a graph or tree to find the target node or traverse the entire structure. I hope that readers can master the basic skills of writing breadth-first search algorithms in C# through this article.

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