3 вопрос

Граф – конечное множество вершин и множеств рёбер. Каждому ребру сопоставлены 2 вершины – концы ребра.
Представление графов в памяти
Обычно используются 2 типа матриц: 1) матрица смежности 2) весовая матрица
Матрица смежности – матрица размером N*N, где каждый эл-т с индексами i,j является логическим значением и показывает есть ли дуга между i и j.
Весовая матрица – квадратичная матрица, где каждый эл-т с индексами i,j равен весу ребра из вершины i в j.
Поиск в ширину
Метод обхода графа и поиска пути в графе. Поиск в ширину работает путем последовательного просмотра отдельных уровней графа, начиная с узла-источника.
Рассмотрим все рёбра графа (u,v), выходящие из узла u. Требуется найти длину кратчайшего пути от заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф в котором для каждого ребра найдётся обратное, соединяющее те же вершины в другом направлении.
Для алгоритма нам потребуется очередь и множество посещенных вершин was, которые изначально содержат вершину s. На каждом шагу алгоритм берет из начала очереди вершину v и добавляет все непосещенные смежные с v вершины в was и в конец очереди. Если очередь пуста, то алгоритм завершает работу.
source – исходная вершина
destination – конечная вершина
G – граф, состоящий из списка вершин V и списка смежности E
Q – очередь
В поле d[u] хранится расстояние от source до u
int BFS (G: (V,E), source: int, destination: int):
	d = int [|V|];
	fill(d,infinity);
	d[source] = 0;
	Q = 0;
	Q.push(source);
	While Q != 0 {
		U = Q.pop();
		for v: (u,v) in E
			if d[v] == infinity
				d[v] = d[u] + 1;
				Q.push(v);
	}
	Return d[destination];

Восстановление кратчайшего пути
ЕСЛИ финишная ячейка помечена
ТО
  перейти в финишную ячейку
  ЦИКЛ
    выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
    перейти в выбранную ячейку и добавить её к пути
  ПОКА текущая ячейка — не стартовая
  ВОЗВРАТ путь найден
ИНАЧЕ
  ВОЗВРАТ путь не найден