Home > Article > Backend Development > 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.
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 Node
Class, used to represent nodes in the graph. A node contains a value and a list of neighbors. BFSAlgorithm
The 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.
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!