Построить цикл с наименьшой длиной, который проходит через каждое ребро графа по крайней мере один раз
Эйлеровые циклы.
Если матрица парная то программа работает верно, а если не парная то не хочет выводить на экран цикл.
Подскажите пожалуйста как пофиксить :?
В функции "void euler(vector<vector> A, vector&c)" в этой части выбивает ошибку черех дебаггер:
if (degree[i] % 2 != 0) // если непарная степень
{
Poisk_cukl(i, A, c);
}
Пример файла бд:
5
0 1 1 0 0
1 0 0 0 1
1 0 0 1 1
0 0 1 0 1
0 1 1 1 0
Вот full код:
#include<iostream>
#include<fstream>
#include<vector>
#include<windows.h>
using namespace std;
int n;
vector<vector<int>> G; // 2D вектор (матрица смежности)
vector<int>Cukl(0);
vector<int>Pathed;
void Poisk_euler(int v, vector<vector<int>>&A, vector<int>&c) // функция поиска эйлерового цикла
{
for (int i = 0; i < A[v].size(); i++)
if (A[v][i]) // якщо є ребро
{
// проходим по нему
A[v][i] = 0;
A[i][v] = 0;
Poisk_euler(i, A, c);
}
c.push_back(v);
}
void Poisk_cukl(int v, vector<vector<int>>&A, vector<int>&c)
{
for (int i = 0; i < A[v].size(); i++)
{
if (A[v][i]) // если есть ребро
{
// проходим по нему
A[v][i] = 0;
A[i][v] = 0;
Pathed.clear();
Poisk_cukl(i, A, c);
}
c.push_back(v);
for(int i=0; i<A[v].size(); i++)
{
if(A[v][i]) // существует непройденное ребро
{
Pathed.push_back(c.back());
c.pop_back();
Poisk_cukl(i, A, c);
}
}
}
}
void euler(vector<vector<int>> A, vector<int>&c)// проверяем существует ли в графе эйлеровый цикл
{
int n = A.size();
c.clear();
// учитываем степени вершин
vector<int>degree(n, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (A[i][j])
{
++degree[i];
}
}
if (degree[i] % 2 != 0) // если непарная степень
{
Poisk_cukl(i, A, c);
}
}
Poisk_euler(0, A, c); // находим цикл, который проходит по ребрам 1 раз
}
int main()
{
setlocale(LC_ALL, "Ukrainian");
ifstream FILE("Матриця.txt");
FILE >> n;
cout<< n <<endl;
if (n > 8 || n <= 0)
{
cout<< "Ошибка n должно быть 0 < n < 8" <<endl;
system("pause");
return 0;
}
G = vector<vector<int>>(n, vector<int>(n)); // выделение памяти для матрицы
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
FILE >> G[i][j];
cout<< G[i][j] << " ";
}
cout<<endl;
}
euler(G, Cukl);
if (Cukl.size() != 0)
{
cout<< " Цикл:";
for (int i = 0; i <Cukl.size(); i++)
{
if (i != 0) cout<< "->";
cout<<Cukl[i] + 1;
}
cout<<endl;
}
else
{
cout<< " Цикл не найден";
}
return 0;
}