SkillGridИзучай computer science на практике

Графы: точки, линии и что они значат

Граф — это точки, соединённые линиями, и одна и та же картинка может описывать друзей, дороги или порядок сборки.

14 мин · 45 XP

Граф — это две вещи: множество вершин (точки) и множество рёбер (линии, которые их соединяют). В этом всё определение. Сила появляется благодаря тому, что ты сам решаешь, что означают точки и линии: одна и та же структура сразу отвечает на вопросы о друзьях, городах, компьютерах и задачах.

Вершины и рёбра — что может значить одна и та же картинка: люди - вершина = человек, ребро = «дружит с» семья - вершина = человек, ребро = «родитель» карты - вершина = город, ребро = дорога между ними сети - вершина = компьютер, ребро = кабель или Wi-Fi сборка - вершина = задача, ребро = «должна идти после» Направленное ребро: A -> B — это не то же самое, что B -> A. «родитель» направлено. «дружит с» — нет.

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

RouterLaptopPhoneServercableWi-Firequestreply comes back the same wayevery hop is one edge of the graph

Практика

  1. Сопоставь каждую ситуацию с тем, что в ней означают вершина и ребро.

    Подсказки
    • Спроси себя, что означает один шаг между двумя элементами в каждой ситуации.
    • В списке сборки стрелка говорит, что должно случиться раньше, а не что на что похоже.

    13 XP

  2. От Тома можно дойти до Аны, от Аны — до Лены, а ещё напрямую от Лены обратно к Тому. Что это за граф?

    Подсказки
    • У дерева вообще нет циклов: если можно пройти по кругу, это не дерево.
    • В родословной ты поднимаешься к общему родителю, а потом спускаешься обратно.

    14 XP

  3. Нарисуй граф сборки: база данных должна быть готова раньше API-сервера, кэш должен быть готов раньше API-сервера, и фронтенд должен быть готов раньше API-сервера. Только после API-сервера сайт запускается.

    Подсказки
    • Нарисуй по одной стрелке для каждого правила «должно быть закончено раньше» из условия.
    • Машина, от которой зависит всё, стоит между этими тремя и последним шагом.

    18 XP