В этой статье мы рассмотрим алгоритм получения списка фундаментальных циклов для неориентированного, связного графа без петель. Кроме того, граф не является мультиграфом. Весь алгоритм можно расписать следующим образом:
Определяем, связан ли граф (Если нет — циклов нет);
Строим матрицу смежности остовного дерева графа;
Устраиваем цикл по хордам;
Выводим список фундаментальных циклов графа.
Приступим к реализации алгоритма
Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры.
Алгоритм Форда-Белмана для поиска кратчайшего расстояния в графе. private void algFordaBelmana() { int s=Convert.ToInt32(textBox5.Text) — 1; //произвольная вершина графа, которая послужит началом пути int[] D=new int[n]; initGraph(); initMatrixWeight(); if (s < 0 || s >= n) return; for (int i = 0; i < n; i++) { D[i] = A[s, i]; } [...]
Циклом Эйлера называется путь проходящий только 1 раз через каждое ребро графа. Для существования циклов Эйлера необходимо чтобы граф был связанный и все его вершины имели четную степень (кол-во ребер инцидентных вершине четно).
Компонентом связности называют максимально связанный порожденный подграф. Числом связности графа – кол-во компонент связности.