Поиск в ширину (BFS) на С#

в 13:12, , рубрики: bfs, C#, Алгоритмы, КодоБред, метки:

Сразу скажу, что статья больше подойдёт людям, желающим познакомиться с поиском в ширину, и новичкам, осваивающим программирование. К тому же, когда мне понадобился этот метод, я нигде не нашёл наглядного рабочего примера на C#.

Устно об алгоритме:

Разберём алгоритм на произвольном графе (для простоты примера рёбра не имеют вес).

Последовательность алгоритма заключается в следующим:

1. Выбирается произвольно вершина графа (отмечается серым).
2.Последовательно рассматриваются вершины (так же отмечаются серым), связанные с нашей первой вершиной (после этого она становится не серой, а чёрной).
3. Выполняется пункт 2 для отмеченных (серых) вершин до тех пор, пока все вершины не будут закрашены чёрным.

Поиск в ширину (BFS) на С# - 1

Теперь тоже самое, но более техническим языком:
1. Выбирается произвольная вершина в графе и помещается в очередь.
2. В очередь помещаются все вершины графа смежные с уже находящейся в очереди вершиной, после чего эта вершина выталкивается из очереди.
3. Выполняется пункт 2 для всех вершин, находящихся в очереди.

Теперь перейдём непосредственно к коду (C#):
В качестве графа мы будем использовать массив, программировать будем на консоли (для примера достаточно будет и её). К слову, в примере будем использовать ориентированный граф.

Зададим начальные переменные и заполним наш массив.

Random rand = new Random();
Queue<int> q = new Queue<int>();    //Это очередь, хранящая номера вершин
string exit = "";
int u;
int v;
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 — это массив массивов, где первый индекс определяет нашу вершину с которой мы работаем, а второй массив определяет индексы вершин, с которыми наша вершина связана и не связана (если значение равно 0 — не связана, следовательно, если 1 — связана). То есть, например g[1][5] = 0, означает, что от первой к пятой вершины нет связи (но так как граф ориентированный, то матрица смежности будет не симметричной, следовательно если g[1][5] = 0, то это не означает что и g[5][1] = 0).

used — логический массив, в который мы будем заносить посещённые вершины.

Идём далее, собственно, сам алгоритм в действии:

                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]))
                        {
                            v = i;
                            if (!used[v])
                            {
                                used[v] = true;
                                q.Enqueue(v);
                                Console.WriteLine("Добавили в очередь узел {0}", v + 1);
                            }
                        }
                    }
                }

while — будет выполняться до тех пор, пока очередь не опустеет. В начале каждой итерации присваиваем переменной u значение выталкиваемого элемента очереди.

for — цикл, проходящий по всем вершинам. В нём для начала проверяем нашу вершину на наличие у неё смежных вершин, если есть и если такая вершина не добавлена в массив посещённых вершин (массив used), то мы её туда добавляем, а так же добавляем в нашу очередь.

Собственно вот он весь алгоритм. Да, пожалуй далеко без изысков, и можно сделать куда лучше, но пишу статью исключительно для ознакомительных целей, надеясь, что кому-то, кто так же, как когда-то и я, искал наглядные примеры, она поможет.

Вот примерно как должна получиться программа:

BFS

static void Main(string[] args)
        {
            Random rand = new Random();
            Queue<int> q = new Queue<int>();    //Это очередь, хранящая номера вершин
            string exit = "";
            int u;
            int v;
            do
            {
                Console.WriteLine("Задать размер массива самостоятельно? ");
                if (Console.ReadLine() == "да")
                {
                    Console.WriteLine("Введите размер:");
                    u = Convert.ToInt32(Console.ReadLine()) - 1;
                    if (u < 3)
                    {
                        Console.WriteLine("Вы ввели некорректный размер массива. Программа автоматически заменила размер.");
                        u = rand.Next(3, 5);
                    }
                }
                else
                    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");
                    
                }


                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]))
                        {
                            v = i;
                            if (!used[v])
                            {
                                used[v] = true;
                                q.Enqueue(v);
                                Console.WriteLine("Добавили в очередь узел {0}", v + 1);
                            }
                        }
                    }
                }
                Console.WriteLine("Завершить программу?");
                exit = Console.ReadLine();
                Console.Clear();
            } while (exit != "да" || exit != "lf");
            Console.ReadKey();
        }

Поиск в ширину (BFS) на С# - 2

На этом всё. Большое спасибо за внимание!

P.S. Опытные программисты, увидев мой кодобред, помимо своих гневных постов о том кто я такой, пишите как можно сделать лучше, рад буду дельному совету — сделаем статью более удобной и комфортной для новичка.

Автор: Antipat

Источник

Поделиться

* - обязательные к заполнению поля