Алгоритмы на графах: Дейкстры, Прима, Краскала

Способы представления графа

Существуют различные виды представления графа:

  1. списки смежности,
  2. списки ребёр,
  3. матрица смежности,
  4. матрица инцидентности.

Списки смежности и списки ребёр

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

Исходный граф

Rendered by QuickLaTeX.com

Списки смежности:

[a] -> a:2 -> b:5 -> d:8
[b] -> c:7 -> d:9
[c] -> d:4
[d] -> c:3

Списки ребёр:

[a,a,2]
[a,b,5]
[a,d,8]
[b,c,7]
[b,d,9]
[c,d,4]
[d,c,3]

Матрица смежности и матрица инцидентности

Является более удобным представлением в том случае, когда нужно быстро отвечать на вопрос «является ли данное ребро инцидентно к…» или аналогичные. Но, если графы не плотные (а разреженные), то занимается существенное количество памяти. Матрица смежности состоит из таблицы размером |V| \times |V|, где на пересечении для каждой пары вершин находится или признак того, что ребро между ними существует (для неориентированных графов), либо вес ребра. Матрица инцидентности имеет размер |V| \times |E|, а её пересечении говорит о том, что данное ребро инцидентно вершине (то есть один из её концов содержит вершину). В случае ориентированного графа в матрице смежности используются положительные числа для того, чтобы обозначить, что ребро выходит из этой вершины:

Матрица смежности:


   a  b  c  d
a  2  5  0  8
b  0  0  7  9
c  0  0  0  4
d  0  0  3  0

Матрица инцидентности:


       a  b  c  d
(a,a)  2  0  0  0
(a,b)  0  5  0  0
(a,d)  0  0  0  8
(b,c)  0  0  7  0
(b,d)  0  0  0  9
(c,d)  0  0  0  4
(d,c)  0  0  3  0

Алгоритм Дейкстры

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

Продолжение следует

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: