Wide Search (BFS) in C #

At once I will say that the article is more suitable for people who want to get acquainted with the search in width, and for beginners who master programming. Besides, when I needed this method, I could not find a visual working example in C # anywhere.

Orally about the algorithm:

Let us analyze the algorithm on an arbitrary graph (for the sake of simplicity, the edges do not have weight).
')
The sequence of the algorithm is as follows:

1. An arbitrary vertex of the graph is selected (marked in gray).
2. Consistently vertices are considered (also marked gray) associated with our first vertex (after that it becomes not gray, but black).
3. Step 2 is performed for the marked (gray) vertices until all the vertices are filled with black.



Now the same thing, but in a more technical language:
1. An arbitrary vertex in the graph is selected and placed in a queue.
2. All vertices of the graph adjacent to the vertex already in the queue are placed in the queue, after which this vertex is pushed out of the queue.
3. Point 2 is executed for all peaks in the queue.

Now let's go directly to the code ( C # ):
We will use an array as a graph, we will program on the console (for example, it will suffice). By the way, in the example we will use a directed graph.

Set the initial variables and fill our array.

Random rand = new Random(); Queue<int> q = new Queue<int>(); // ,    string exit = ""; int u; u = rand.Next(3, 5); bool[] used = new bool[u + 1]; //    int[][] g = new int[u + 1][]; //     for (int i = 0; i < u + 1; i++) { g[i] = new int[u + 1]; Console.Write("\n({0})  -->[", i + 1); for (int j = 0; j < u + 1; j++) { g[i][j] = rand.Next(0, 2); } g[i][i] = 0; foreach (var item in g[i]) { Console.Write(" {0}", item); } Console.Write("]\n"); } 

g is an array of arrays, where the first index defines our vertex with which we work, and the second array determines the indices of the vertices with which our vertex is connected and not connected (if the value is 0, it is not connected, therefore, if 1 is connected). That is, for example, g [1] [5] = 0, means that there is no connection from the first to the fifth vertex (but since the graph is oriented, the adjacency matrix is ​​not symmetric, hence if g [1] [5] = 0, this does not mean that g [5] [1] = 0).

used - a logical array in which we will bring visited vertices.

Let's go further, in fact, the algorithm itself in action:

  used[u] = true; //,   (    ) q.Enqueue(u); Console.WriteLine("   {0} ", u + 1); while (q.Count != 0) { u = q.Peek(); q.Dequeue(); Console.WriteLine("   {0}", u + 1); for (int i = 0; i < g.Length; i++) { if (Convert.ToBoolean(g[u][i])) { if (!used[i]) { used[i] = true; q.Enqueue(i); Console.WriteLine("    {0}", i + 1); } } } } 

while - will be executed until the queue is empty. At the beginning of each iteration, assign the variable u the value of the pushed queue element.

for is a loop passing through all vertices. To begin with, we check our vertex for the presence of adjacent vertices, if there is, and if such a vertex is not added to the array of visited vertices (used array), then we add it there, as well as add to our queue.

Actually, here it is the whole algorithm. Yes, perhaps far away without frills, and it can be done much better, but I am writing an article solely for informational purposes, hoping that it will help someone who, like I once did, looked for illustrative examples.

This is how the program should turn out:




That's all. Thank you very much for your attention!

PS Experienced programmers, after seeing my codebred, in addition to their angry posts about who I am, write how you can do better, I will be glad with good advice - we will make the article more convenient and comfortable for a beginner.