svetasmirnova | Coursera: algs4partII-001. Неделя 1. Часть 1. Undirected Graphs

Попишу-ка я технические заметки про этот курс.

По опыту предыдущего курса: к экзамену забываются, во-первых, требуемый формат ответов, а во-вторых, что-то из усвоенного материала.

Тесты:

1. Depth-first search.

Что такое depth-first search - интуитивно понятно: берём текущую node, проходим путь от неё до тупика, возвращаемся к предыдущей node, проходим от неё до тупика и т.д. пока не доберёмся до цели. Пройденные node дважды не проходятся.

Сложность вопроса: выбрать порядок, принимаемый auto-grader, так как алгоритм сам по себе порядка не определяет.

Решение: смотреть только на текстовое представление графа и не обращать внимание на визуальное.

То есть если есть A: E B F, то надо первым выбрать E, пройти весь путь и только вернувшись обратно пройти сначала B, потом F.

2. Breath-first search.

Аналогично: не смотреть на картинку. Естественно, порядок будет: A E B F, потом по горизонтали E, B и F.

3. Connected components.

Совсем просто: как на слайдах пронумеровать по принадлежности к группе. Тут картинка, наоборот, всё упрощает.

Reference: algs4.cs.princeton.edu/41undirected/