Вам может быть предоставлен список ребер и задача построить собственный граф для выполнения обхода.
Зачастую вопросы о лбщих представлениях о графах включают вопросы о:
1 . Матрицах смежности.
2. Списках примыканий.
3. Хашмап хэшмапов.
Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.
Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.
Список смежности можно представить как перечень элементов, где слева находится один узел, а справа — все остальные узлы, с которыми он соединяется.
Матрица смежности — это сетка с числами, где каждый ряд или колонка соответствуют отдельному узлу в графе. На пересечении ряда и колонки находится число, которое указывает на наличие связи. Нули означают, что она отсутствует; единицы — что связь есть. Чтобы обозначить вес каждой связи, используют числа больше единицы.
Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.
Вопросы про алгоритмы поиска:
Общие – поиск в ширину, поиск в глубину.
Необычные – топологическая сортировка, алгоритм Дейкстры.
Редкие – алгоритм Беллмана-Форда, Флойда-Уоршелла, Прима, Краскала.
В собеседованиях графы обычно представлены в виде двухмерных матриц, где ячейки являются узлами, и каждая ячейка может пересекаться с ячейками соседними (вверх/вниз/влево/вправо). Поэтому важно, чтобы вы были знакомы с пересечением двумерной матрицы. При рекурсивном перемещении матрицы убедитесь, что ваша следующая позиция находится в пределах матрицы. Больше советов по алгоритмам поиска можно найти здесь.
Простой шаблон для выполнения поиска в глубину выглядит следующим образом:
def traverse(matrix):
rows, cols = len(matrix), len(matrix[0])
visited = set()
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
def dfs(i, j):
if (i, j) in visited:
return
visited.add((i, j))
# Обход соседей
for direction in directions:
next_i, next_j = i + direction[0], j + direction[1]
if 0 <= next_i < rows and 0 <= next_j < cols: # Проверка границы
# Добавить любую другую проверку здесь ^
dfs(next_i, next_j)
for i in range(rows):
for j in range(cols):
dfs(i, j)Тупиковые ситуации:
- пустой граф;
- граф с одним или двумя узлами.
- непересекающиеся графы;
- граф с циклами.
@machinelearning_interview