Цели¶

• Изучить, что такое граф и для чего он нужен.
• Реализовать абстрактный тип данных граф несколькими способами.
• Посмотреть, как можно использовать графы для решения широкого спектра задач.

В этой главе мы будем изучать графы. Это более общая структура, чем деревья из прошлой главы. Фактически, вы можете думать о дереве, как об отдельном подвиде графа. Графы можно использовать для представления множества интересных вещей из нашего мира, включая системы дорог, авиаперелёты между городами, коммутации в интернете и даже последовательность предметов, которые вам следует изучить для профилирования по информатике. В этой главе мы увидим, что, имея хорошее представление задачи, можно использовать для её решения стандартные алгоритмы на графах, тогда как без них это оказалось бы чрезвычайно сложным.

Хотя для человека относительно просто посмотреть на карту дорог и понять взаимоотношения между отдельными местами, компьютер такой способностью не обладает. Однако, о карте дорог тоже можно думать, как о графе. Тогда компьютер может делать для нас весьма любопытные вещи. Если вы когда-нибудь пользовались одним из сайтов с картами, то знаете, что он может найти кратчайший, быстрейший или легчайший маршрут из одного места в другое.

Как студенту-информатику, вам может быть любопытно, какие курсы и в каком порядке необходимо пройти, чтобы получить специализацию. Граф - хороший способ представления необходимых условий и других взаимозависимостей между предметами.

На рисунке 1 показан граф, представляющий курсы и порядок их прохождения для получения специализации по информатике в Luther College.

Figure 1: Необходимые условия для получения специализации по информатике.