Граф — это математическая абстракция, имеющая, тем не менее, очень широкое применение в программировании. Граф состоит из множества так называемых вершин, которые обычно изображаются как точки на плоскости, и рёбер(другое название ребра — дуга), которые эти вершины соединяют. Пример графа приведён на рисунке.
Чаще всего графы применяются для описания различных схем, например, соединения узлов в компьютерной сети или городов и других пунктов на карте местности. Типичная решаемая с помощью графа задача — поиск кратчайшего маршрута из одного пункта в другой. Довольно часто граф, помимо информации о своих вершин и рёбрах, содержит вспомогательную информацию. Например, для схемы дорог ей могут быть названия городов, соответствующих вершинам графа, или длины дорог, соответствующих рёбрам графа. Пример:
Структуры данных, подобные графам, могут возникать в различных задач поиска оптимального решения. Например, в lesson8/task2 имеется задача о поиске наиболее короткой траектории движения шахматного коня. Эту задачу можно описать с помощью графа, вершинами которого являются клетки шахматной доски, а рёбра соединяют те из них, между которыми может двигаться шахматный конь. Такой граф может выглядеть примерно так:
Описать граф на языке программирования можно разными способами. В той же задаче о маршруте шахматного коня лучше вообще не хранить информацию о вершинах графа, достаточно лишь уметь по конкретной клетке найти связанные с ней ребром — то есть, те клетки, в которые из данной клетки может прыгнуть конь. В других задачах, тем не менее, информацию о вершинах и рёбрах графа есть смысл сохранить, и тогда следует для этой цели использовать собственный класс. Пример реализации такого класса приведён ниже.
class Graph {
private data class Vertex(val name: String) {
val neighbors = mutableSetOf<Vertex>()
}
private val vertices = mutableMapOf<String, Vertex>()
private operator fun get(name: String) = vertices[name] ?: throw IllegalArgumentException()
fun addVertex(name: String) {
vertices[name] = Vertex(name)
}
private fun connect(first: Vertex, second: Vertex) {
first.neighbors.add(second)
second.neighbors.add(first)
}
fun connect(first: String, second: String) = connect(this[first], this[second])
fun neighbors(name: String) = vertices[name]?.neighbors?.map { it.name } ?: listOf()
}
Описанный здесь Graph является довольно сложным классом. Он включает в себя функцию addVertex (добавить вершину) и две функции connect (соединить) с разным набором параметров, причём одна из них является закрытой(private). Для доступа к списку вершин, соседних для данной, в классе имеется функция neighbors, Кроме этого, в классе имеется операторная функция get, которая также является закрытой, свойство (val) vertices (вершины), в котором хранится ассоциативный массив (MutableMap) и которое опять-таки закрыто, и вложенный класс Vertex(вершина) со свойствами name (имя) и neighbors (соседи). Рассмотрим все эти элементы класса Graph подробнее.
