Занятие 12. Справочник

Занятие 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++;
	}
}