24 марта 2009

Занятие 19 марта: графы

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

Наш граф (интерфейс Graph) состоит из осязаемых объектов-вершин (интерфейс Vertex) и неосязаемых дуг. Граф умеет создавать вершины и отдавать список созданных. Вершина умеет создавать и удалять дуги в другие вершины и хранить произвольные свойства.

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

Интерфейсы можно скачать здесь: http://barashev.net/src/graph.zip
Тестов пока нет, будут позже. На следующем занятии работаем над простешими алгоритмами.