Пошук у ширину (BFS) на З#

Відразу скажу, що стаття найбільше підійде людям, охочим познайомитися з пошуком в ширину, і новачкам, які освоюють програмування. До того ж, коли мені знадобився цей метод, я ніде не знайшов наочного робочого прикладу на 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), то ми її туди додаємо, а так само додаємо в нашу чергу.

Власне ось він весь алгоритм. Так, мабуть далеко без вишукувань, і можна зробити куди краще, але пишу статтю виключно для ознайомлювальних цілей, сподіваючись, що комусь, хто так само, як колись і я, шукав наочні приклади, вона допоможе.

Ось приблизно як повинна вийти програма:

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 != "пропонує");
Console.ReadKey();
}




На цьому все. Велике спасибі за увагу!

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

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.