Обход в ширину

Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Если мы начали обход в вершине i, то в первую очередь мы посетим всех ее соседей по порядку, далее мы спустимся на один уровень ниже и продолжим алгоритм. Другими словами, сначала мы посетим вершины на уровне 1 от i, потом на уровне 2 от i и так далее до конца. С помощью этого алгоритма можно определить минимальное количество ребер между вершиной i и любой достижимой из i вершины.

Если в графе N вершин и M ребер, то сложность обхода составляет O(N + M).

Хранение графа

Граф будет храниться в массиве структур. Полностью про хранение графа в программе смотрите в разделе представление графа в программе.

Каждый элемент массива структур хранит информацию об одной из вершин графа, а именно:

1) пути из этой вершины;
2) количество таких путей;
3) посещали ли мы уже эту вершину или нет.

Вот так выглядит такая структура:

struct vertice {
	int* paths;  // пути
	int number_of_paths;  // кол-во путей
	int flag;  // были вершине или нет
};

Выделение памяти

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

scanf("%i%i", &v, &u);  // между этими вершинами есть путь
Graph[v - 1].paths = realloc(Graph[v - 1].paths, (Graph[v - 1].number_of_paths + 2) * sizeof(int));
Graph[u - 1].paths = realloc(Graph[u - 1].paths, (Graph[u - 1].number_of_paths + 2) * sizeof(int));

Сразу после этого добавляем в массив путей новую вершину, в которую можно попасть из текущей. Добавление путей для неориентированного графа:

Graph[v - 1].paths[Graph[v - 1].number_of_paths] = u - 1;
Graph[v - 1].number_of_paths++;
Graph[u - 1].paths[Graph[u - 1].number_of_paths] = v - 1;
Graph[u - 1].number_of_paths++;

Таким образом мы добавили путь из v в u и наоборот.

Для ориентированного графа необходимы только первые две строчки при условии, что ребро имеет направление из v в u.

Естественно изначально у каждой вершины количество путей равно нулю и никакую вершину мы еще не посещали, поэтому для любой i верно, что
Graph[i].flag = 0 и Graph[i].number_of_paths = 0.

Алгоритм BFS

Для обхода вершин графа используется очередь. Изначально в очередь добавляем стартовую вершину. Работа с очередью состоит из двух частей:
1. Добавление всех вершин доступных из v, которые мы еще не посещали, v - номер вершины, находящаяся в начале очереди;
2. Удаление вершины v.
Алгоритм завершается, когда в очереди не остается элементов.
В языке Си нет отдельного класса очереди, поэтому создаем его сами и используем для конкретных задач алгоритма. В данном примере проверяется правильность выделения памяти под динамические массивы.

Пример обхода на Cи:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define SIZE 100
 
struct vertice {
	int* paths;
	int number_of_paths;
	int flag;
};
 
struct queue {
	struct  queue* next;
	int X;
};
 
struct  queue* enqueue(struct queue* q, int a) {
	struct  queue* buf = malloc(sizeof(struct queue));
	if (buf) {
		buf->X = a;
		buf->next = NULL;
		q->next = buf;
		return buf;
	}
	return q;
}
 
struct  queue* dequeue(struct queue* q) {
	return q->next;
}
 
int main() {
	int n, m, i, v, u, l;
	struct vertice Graph[SIZE];
	scanf("%i%i", &n, &m);
	for (i = 0; i < SIZE; i++) {  // начальная инициализация 
		Graph[i].paths = malloc(sizeof(int));
		Graph[i].number_of_paths = Graph[i].flag = 0;
	}
	i = 0;
	while (i < m) {
	scanf("%i%i", &v, &u);
		if (v > 0 && v < SIZE && u > 0 && u < SIZE) {
			int* buf1 = realloc(Graph[v - 1].paths, ((Graph[v - 1].number_of_paths + 2) * sizeof(int)));
			int* buf2 = realloc(Graph[u - 1].paths, ((Graph[u - 1].number_of_paths + 2) * sizeof(int)));
			if (buf1 && buf2) {  // проверка realloc
				Graph[v - 1].paths = buf1;
				Graph[v - 1].paths[Graph[v - 1].number_of_paths] = u - 1;
				Graph[v - 1].number_of_paths++;
 
				Graph[u - 1].paths = buf2;
				Graph[u - 1].paths[Graph[u - 1].number_of_paths] = v - 1;
				Graph[u - 1].number_of_paths++;
				i++;
			}
			else printf("error\n");
		}
		else printf("Введите корректные значения\n");
	}
 
	int start = 0;  // с какой переменной начинается обход
	int cur;  // текущая переменная
	struct  queue* front = malloc(sizeof(struct  queue)), *end = malloc(sizeof(struct  queue));  
	if (front && end ) {
		end = front;
		end = enqueue(end, start);
		while (front->next != NULL) {  // BFS
			cur = front->next->X;
			Graph[cur].flag = 1;
			l = Graph[cur].number_of_paths;
			front = dequeue(front);
			for (i = 0; i < l; i++) {  // добавляем в очередь пути из вершины cur
				if (Graph[cur].paths != NULL) {
					if (Graph[Graph[cur].paths[i]].flag == 0) {  // если еще не посещали вершину
						Graph[Graph[cur].paths[i]].flag = 1;
						end = enqueue(end, Graph[cur].paths[i]);
					}
				}
				else  printf("error\n");
			}
		}
	}
	return 0; 
}

Если отбросить все сложности с динамическим выделением памяти и посмотреть на алгоритм на c++, реализованный с помощью контейнеров vector и queue, то можно убедиться в простоте алгоритма. Так же анализ кода на c++ поможет лучше разобраться с алгоритмом на Си.

Пример обхода на C++

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
struct  graph {
	vector<int> paths;  // пути
	int flag;  // были в вершине или нет
};
 
int main() {
	int n, m, i, x, y, j;
	struct  graph A[100];
	queue <int> q;
 
	cin >> n >> m;
	for (i = 0; i < n; i++) {  // начальная инициализация
		A[i].flag = 0;
	}
	for (i = 0; i < m; i++) {  // заполнение массива структур
		cin >> x >> y;
		A[x - 1].paths.push_back(y - 1);
		A[y - 1].paths.push_back(x - 1);
	}
 
	q.push(0);  // очередь вершин
	A[0].flag = 1;  // мы сейчас в этой вершин
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (j = 0; j < A[v].paths.size(); j++) {
			if (A[A[v].paths[j]].flag == 0) {
				q.push(A[v].paths[j]);
				A[A[v].paths[j]].flag = 1;
			}
		}
	}
	return 0;
}

Задача:

В городе P есть n домов, пронумерованных от 1 до n. Дома связывают дороги, при этом можно добраться из любого дома в любой другой. Саша живет в 1 доме, но ему приходится ходить в магазин, который находится в доме k. Саша хочет добираться до магазина как можно быстрее. Вам нужно вывести минимальное количество пройденных дорог от его дома до магазина.
Входные данные:
Первая строка содержит целые числа n(2 ≤ n ≤ 10^5), m(1 ≤ m ≤ 10^5), k(2 ≤ k ≤ 10^5), - количество домов, количества дорог и дом, в котором находится магазин соответственно.
Следующие m строк содержат два числа, обозначающие, что есть дорога между домами v и u.
Выходные данные:
Вывести минимальное количество дорог, которые должен пройти Саша от своего дома до магазина.

Пример:

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