• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

algorytm wyznaczania cyklu Eulera - problem z działaniem

VPS Starter Arubacloud
0 głosów
518 wizyt
pytanie zadane 6 sierpnia 2019 w C i C++ przez basher1705 Nowicjusz (210 p.)

Witam, mam problem z algorytmem wyznaczania cyklu Eulera w grafie nieskierowanym. Chcę zapisać algorytm wyszukiwania cyklu Eulera, opisany na tej stronie: https://eduinf.waw.pl/inf/alg/001_search/0135.php (chodzi o ten pierwszy algorytm wykrzystujący DFS_Postorder- nie Fleury ani Hierholzer), i moja poniższa implementacja w c++ jest zrobiona na tablicach list, a nie na macierzy sąsiedztwa, tak jak na stronie, i wywala mi błąd podczas przeszukiwania DFS, i potrzebuję pomocy kogoś doświadczonego, kto wskaże błędy w kodzie.

tutaj wklejam jeszcze test do algorytmu,  czyli graf, który posiada cykl Eulera:

6 10
1 5 1 6
2 3 2 4 2 5 2 6
3 4 3 5 3 6
5 6

Algorytm:

#include <iostream>
#include <list>
#include <stack>

using namespace std;

void DFS_EULER(int v, list<int> tab[], stack<int> Vertices)
{
    list<int>::iterator it;

    for(it = tab[v].begin(); it != tab[v].end(); it++)  //przeszukujemy sasiadow
    {
        tab[v].remove(*it);
        tab[*it].remove(v);  //usuwamy krawedzie
        DFS_EULER(*it, tab, Vertices); //wywolanie rekurencyjne
    }
    Vertices.push(v);
}

int main()
{
    int n, m, v1, v2;
    cin >> n >> m;
    //inkrementacja n i m, poniewaz wierzcholki beda wprowadzane od nr 1, a nie od 0
    n+=1;
    m+=1;

    list<int> *tab = new list<int>[n]; //utworzenie tablicy list, w której będzie graf

    for(int i = 1; i < m; i++)  //wczytywanie krawedzi grafu
    {
        cin >> v1 >> v2;
        tab[v1].push_back(v2);
        tab[v2].push_back(v1);
    }

    stack<int> Vertices;

    DFS_EULER(1, tab, Vertices);  //funkcja rekurencyjna wyznaczajaca wierzcholki cyklu eulera

    //wypisanie cyklu ze stosu
    cout << "Vertices: " << endl;
    while(Vertices.size() > 0)
    {
        cout << Vertices.top() << " ";
        Vertices.pop();
    }
    delete [] tab;

    return 0;
}

 

1 odpowiedź

0 głosów
odpowiedź 6 sierpnia 2019 przez RafalS VIP (122,820 p.)
edycja 6 sierpnia 2019 przez RafalS

i moja poniższa implementacja w c++ jest zrobiona na tablicach list, a nie na macierzy sąsiedztwa

i to jest błąd. Usuwanie elementów z kontenera po którym iterujesz w pętli jest upierdliwe.

Sam nie wiem czy chciałoby mi się rozkminiać takie usuwanie 2 elementów z listy na dowolnej pozycji w pętli. Pewnie przez parę godzin. A niby coś o cpp wiem.

Podobne pytania

0 głosów
1 odpowiedź 412 wizyt
pytanie zadane 17 marca 2016 w C i C++ przez Jędrzej Dembowski Użytkownik (740 p.)
0 głosów
1 odpowiedź 164 wizyt
pytanie zadane 28 grudnia 2019 w Matematyka, fizyka, logika przez Semcio Początkujący (340 p.)
0 głosów
1 odpowiedź 200 wizyt
pytanie zadane 20 września 2019 w C i C++ przez kawapa Nowicjusz (210 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...