Алгоритм Флери для нахождения цикла Эйлера в графе - C (СИ)

Формулировка задачи:

Может кто-нибудь делал такую работу, я просто не представляю как ее делать. Помогите пожалуйста.

Решение задачи: «Алгоритм Флери для нахождения цикла Эйлера в графе»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
 
#define N 6
#define STACK_SIZE 100
 
 
int G[N][N] =
{
    {0, 1, 1, 1, 1, 0},
    {1, 0, 0, 1, 0, 0},
    {1, 0, 0, 1, 1, 1},
    {1, 1, 1, 0, 0, 1},
    {1, 0, 1, 0, 0, 0},
    {0, 0, 1, 1, 0, 0}
};
 
int k;
int Stack[STACK_SIZE];
 
void Search(int v)
{
    int i;
    for(i = 0; i < N; i++)
        if(G[v][i])
        {
            G[v][i] = G[i][v] = 0;
            Search(i);
        }
    Stack[++k] = v;
}
 
 
 
int main()
{
    int T, p, q, s;
    int j, vv;
 
    T = 1;
    for(p = 0; p < N; p++)
    {
        s = 0;
        for(q = 0; q < N; q++)
        {
            s += G[p][q];
        }
        if(s%2) T = 0;
    }
    k = -1;
    printf("start vertex: "); scanf("%d", &vv);
    if(T)
    {
        Search (vv);
        for(j = 0; j <= k; j++)
            printf("%d ", Stack[j]);
    }
    else
        printf("not Eulerian graph\n");
    return 0;
}

Объяснение кода листинга программы

В данном коде реализован алгоритм Флери для поиска цикла Эйлера в графе. Список действий:

Подготовительные действия:
- Включаем необходимые заголовочные файлы: и .
- Определяем значения переменных N и STACK_SIZE. Значение N - количество вершин в графе, а STACK_SIZE - размер стека.
- Задаем матрицу смежности графа в виде двумерного массива G[N][N]. Если ребро между вершинами v и i существует, то G[v][i] равно 1, иначе 0.
- Инициализируем переменную k значением -1, которая будет использоваться как счетчик для стека.
- Объявляем функцию Search, которая будет выполнять поиск цикла Эйлера.
- В функции main задаем значения переменных T, p, q, s, а также инициализируем переменную vv значением 0 (начальная вершина).
- Задаем значения переменных T, p и q, используя цикл for. Значение T будет равно 1, если в графе есть цикл Эйлера, и 0 в противном случае. Значения p и q используются для прохода по матрице G.
- С помощью цикла for инициируем переменную s значением суммы элементов матрицы G[p][]. Если сумма нечетная, то T присваивается 0.
- После завершения цикла, инициализируем переменную k значением -1 и выводим сообщение с просьбой ввести начальную вершину.
- Если T равно 1, то вызываем функцию Search с аргументом vv.
- В цикле for, начинающемся с k = -1 и выполняющемся до k <= k, выводим значения стека.
- Если T равно 0, то выводим сообщение not Eulerian graph.
- Завершаем функцию main. Алгоритм Флери работает следующим образом:
Начинаем с любой вершины графа и помещаем ее в стек.
В цикле, пока стек не пуст, извлекаем из него вершину и помечаем все ее соседи, как посещенные.
Если вершина является конечной, то ищем цикл Эйлера.
Если цикл найден, то выводим его, в противном случае выводим сообщение о том, что граф не является эйлеровым. Пример работы алгоритма:
Запускаем программу.
Вводим начальную вершину (например, 0).
Программа начинает работу.
Переменная T становится равной 1, так как в графе есть цикл Эйлера.
Программа вызывает функцию Search с аргументом 0.
В функции Search, в цикле for, начиная с 0 и до 5 (так как N = 6), для каждой вершины, если ребро существует, то помечаем вершину и ее соседей, как посещенные, и помещаем их в стек.
После завершения цикла, в стеке остаются вершины {0, 2, 4, 6}.
Переменная k становится равной 4, так как в стеке осталось 4 вершины.
В цикле for, начиная с k = 4 и до k <= 4, выводятся значения стека {0, 2, 4, 6}.
Программа завершается, выводя сообщение Eulerian graph.