Занятие 12. Справочник
| Сайт: | Информатикс |
| Курс: | Фирма "1С". "Алгоритмы. Олимпиадное программирование на языке Java для школьников" |
| Книга: | Занятие 12. Справочник |
| Напечатано:: | Гость |
| Дата: | Четверг, 4 Декабрь 2025, 01:07 |
Занятие 12. Справочник
Волновой алгорим без очереди
Cм. подробное условие в тексте Занятия №12.
int k = 2;
for (int i = 0; i <= X * Y; i++)
{
for (int y = 1; y <= Y; y++)
{
for (int x = 1; x <= X; x++)
{
if (a[y][x] == k)
{
if (a[y][x - 1] == 0) {a[y][x - 1] = k + 1;}
if (a[y - 1][x] == 0) {a[y - 1][x] = k + 1;}
if (a[y][x + 1] == 0) {a[y][x + 1] = k + 1;}
if (a[y + 1][x] == 0) {a[y + 1][x] = k + 1;}
}
}
}
k++;
}
BFS (Breadth-first search)
На естественном языкеПометить стартовую вершину и добавить ее в очередь.
Пока очередь непуста.
• Взять очередную вершину из очереди
• Пометить все непомеченные связанные с ней вершины меткой на единицу больше, чем ее собственная и добавить их в очередь
В графе, заданном матрицей смежности G
Количество вершин V. Массив расстояний d.
Подготовка
int INF = 1000*1000*1000;
for (int v = 0; v < V; v++)
{
d[v] = INF;
}
Функции передается номер стартовой вершины s и она заполняет глобальный массив расстояний d.
static void bfs(int s)
{
Queue q;
d[s] = 0;
q.offer(s);
while(!q.empty())
{
int v = q.poll();
for (int i = 0; i < V; i++)
{
if (G[v][i] == 1 && d[i] == INF)
{
d[i] = d[v] + 1;
q.offer(i);
}
}
}
}
Подсчет количества компонент связности при помощи bfs
int k = 0;// количество компонент связности
for (int i = 0; i < V; i++)
{
if (d[i] != INF)
{
bfs(i);
k++;
}
}