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

Наиболее наглядное представление графов даст рисунок:

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

На рисунке представлен граф состоящий из пяти узлов.

Двунаправленные графы

Двунаправленные графы (bi-directional graphs) - самый простой тип графов. Именно этот тип представлен на рисунке. В данном типе графов, если два узла соединены друг с другом, то между этими узлами можно свободно "перемещаться".

Однонаправленные графы

В однонаправленных графах, если между двумя узлами есть дуга, то она "указывает" только в одну сторону. На рисунке у дуги только одна стрелочка. Для перехода в обе стороны потребуется две дуги.

В будущем мы будем пользоваться именно однонаправленными графами, так как они наиболее гибкие.

В программах графы могут быть представлены разными способами: списком смежности, таблицей инциденций, массивом дуг и др. Некоторые из этих способов мы рассмотрим позже.

Сейчас же мы рассмотрим довольно сложную реализацию графов. Обычно, в учебниках по алгоритмам/структурам данных приводится довольно простая реализация графов, например, списком смежности. Подобные реализации обычно используют только двухмерный массив. Но нам этот вариант не подойдёт. Мы создадим хоть и сложную структуру данных, но очень гибкую. Создавать мы будем именно однонаправленные графы. Для данной реализация нам понадобятся двусвязные списки. Для этого воспользуемся библиотекой algorithms_v0.1. Для понимания кода, вы должны уметь довольно уверенно пользоваться связными списками, которые мы уже рассмотрели. Конечно же в нашей реализации будут использоваться шаблонные классы. В графе присутствует две основные сущности: дуги и узлы. Соответственно, нам понадобятся два типа: ArcType и NodeType. В узлах может хранится, например, какие-нибудь объекты класса. В дугах же можно расстояния между узлами (вес дуги). Весь код размещается в двух файлах в проекте algorithms решения libraries, т.е. в том же проекте, что и реализация двусвязного списка. Необходимые файлы: Graph.h и Graph.cpp GraphArc Класс дуг очень прост. GraphNode Обратите внимание, что данный класс не содержит указатели на другие узлы, вместо этого используется указатель на связный список в котором хрянятся все дуги этого графа. Последняя переменная marked очень важна. Она используется при поиске по графу. NodeGraph содержит три функции: добавление дуги, удаление дуги и поиск дуги.

Добавление дуги к узлу

И последний, самый сложный класс - Graph. Объект класса хранит все узлы графа. Для хранения узлов в графе, мы конечно же будем использовать связные списки.
Пока что, завершим краткий обзор графов. Конечно же мы ещё вернёмся к рассмотрению этой поистине обширной теме. На данный момент, нам хватит информации для рассмотрения других структур данных - частных случаев графов, прежде всего деревьев.