Этапы решения алгоритмической задачи. Базовые структуры данных

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

Математически граф `G(V, E)` есть совокупность двух множеств:

• конечное непустое множество элементов V, называемых вершинами;
• множества Е, содержащего пары `(u,v)`, где `u,v in V`, называемые ребрами.

Если вершины в паре неупорядочены, т.е. пара `(u, v)` означает то же самое, что и пара `(v, u)`, то граф `G` называют неориентированным.

Если порядок в паре важен, то граф `G` называют ориентированным (орграфом). Ребра в орграфе называют дугами.

Ребра, начинающиеся и заканчивающиеся в одной вершине называются петлями.

Граф, в котором каждая пара вершин соединяется ребром, называется полным. В полном графе количество ребер равно `k=(n*(n-1))/2`, где `n` - количество вершин в графе. Граф, в котором количество ребер близко к `k`, называется плотным. Граф, в котором количество ребер близко к `n`, называется разреженным.

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

Матрица смежности используется для представления плотных графов и представляет собой булеву матрицу размером `n xx n`, в которой каждая строка и каждый столбец соответствуют одной из вершин графа. Элемент этой матрицы, находящийся на пересечении `i`-ой строки и `j`-ro столбца, равен 1 в случае, если `i`-я и `j`-я вершины графа соединяются ребром, и 0 в противном случае.

Cписки смежных вершин предпочтительно использовать для разреженных графов. Это одномерный массив, каждый элемент которого соответствует одной из вершин графа и содержит список всех смежных вершинах текущей вершины. В списках присутствуют вершины графа, которым в матрице смежности соответствуют единичные элементы.

Под взвешенным графом подразумевается граф, ребрам которого поставлены в соответствие числа, которые могут означать вес или стоимость или пропускную способность ребра. Оба способа представления легко приспособить для случая взвешенных графов. Элемент матрицы весов `A_{ij}` должен равняться весу ребра, соединяющего `i`-ю и `j`-ю вершины. Если вершины не соединены ребром, то элемент `А_{ij}` должен содержать какое-нибудь специальное значение `+oo` или 0. Для списков смежных вершин в каждый узел списка нужно включить не только номер смежной вершины, но и вес соответствующего ребра.

Граф называется связным, если для любой пары его вершин `u` и `v` существует путь от `u` к `v`. Граф, не содержащий циклов, называют ациклическим.