intermediate
Graphs
Вершины, рёбра, adjacency structures, направленность, веса и последствия для обхода.
Graphs моделируют отношения через vertices и edges. Перед выбором BFS, DFS или shortest path решите, directed ли edges, weighted ли они, есть ли cycles, sparse или dense graph. Representation важен: adjacency lists обычно подходят для sparse graphs, matrices упрощают constant-time edge checks.
На интервью: Хорошие ответы сначала строят graph из input, затем проговаривают visited handling, traversal order и complexity через V и E.
Типовые ошибки: Забытый visited tracking дает infinite loops на cycles. Повторное построение neighbors может скрыть extra cost. Weighted graphs часто требуют Dijkstra, а не plain BFS.
Чеклист:
- Определите V и E.
- Выберите adjacency representation.
- Отслеживайте visited state.
- Соотнесите traversal с edge weights.