Граф

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

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Граф, содержащий ребра между всеми парами вершин, является полным.

Встречаются такие графы, ребрам которых поставлено в соответствие конкретное числовое значение, они называются взвешенными графами, а это значение – весом ребра.

Когда у ребра оба конца совпадают, т. е. оно выходит из вершины и входит в нее, то такое ребро называется петлей.

Петля

Классификация графов

Графы делятся на

  • связные
    Связный граф
  • несвязные
    Несвязный граф

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

В несвязном графе существует хотя бы одна вершина, не связанная с другими.

Графы также подразделяются на

  • ориентированные
    Ориентированный граф
  • неориентированные
    Неориентированный граф
  • смешанные.

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

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

Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

Представление графа

Рассмотрим граф V с n вершинами. Его матрицей смежности называется матрица a[n][n] такая, что

  • a[i][j] = 1, если есть ребро из вершины vi в vj
  • a[i][j] = 0 в противном случае.

Матрица смежности неориентированного графа, таким образом, является симметричной.

Основным недостатком матрицы смежности является большой объем памяти, требуемый для ее хранения.

Альтернативным способом представления графа является список смежности. Требуемая при этом память пропорциональна размеру графа (сумме числа
вершин и числа рёбер). Элементами списка смежности являются связные списки, по одному для каждой вершины графа. Для каждой вершины в таком списке хранятся вершины, в которые ведут рёбра из указанной вершины. Для ориентированного графа каждое ребро входит только в один из этих списков (для начальной вершины), а для неориентированного в два (для двух концов ребра).

Что лучше, матрица смежности или список смежности? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными, с малым - разреженными. Плотные графы удобнее хранить в виде матрицы смежности, разреженные - в виде списка смежности.

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

Назад

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *