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