Сразу скажу, что статья больше подойдёт людям, желающим познакомиться с поиском в ширину, и новичкам, осваивающим программирование. К тому же, когда мне понадобился этот метод, я нигде не нашёл наглядного рабочего примера на C#.
Устно об алгоритме:
Разберём алгоритм на произвольном графе (для простоты примера рёбра не имеют вес).
Последовательность алгоритма заключается в следующим:
1. Выбирается произвольно вершина графа (отмечается серым).
2.Последовательно рассматриваются вершины (так же отмечаются серым), связанные с нашей первой вершиной (после этого она становится не серой, а чёрной).
3. Выполняется пункт 2 для отмеченных (серых) вершин до тех пор, пока все вершины не будут закрашены чёрным.
Теперь тоже самое, но более техническим языком:
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), то мы её туда добавляем, а так же добавляем в нашу очередь.
Собственно вот он весь алгоритм. Да, пожалуй далеко без изысков, и можно сделать куда лучше, но пишу статью исключительно для ознакомительных целей, надеясь, что кому-то, кто так же, как когда-то и я, искал наглядные примеры, она поможет.
Вот примерно как должна получиться программа:
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();
}
На этом всё. Большое спасибо за внимание!
P.S. Опытные программисты, увидев мой кодобред, помимо своих гневных постов о том кто я такой, пишите как можно сделать лучше, рад буду дельному совету — сделаем статью более удобной и комфортной для новичка.
Автор: Antipat
