Cykl Eulera

Odpowiedz Nowy wątek
2016-01-24 16:22
0

Napisałem tu program wyznaczajacy cykl Eulera w grafie, a sam graf jest stworzony w dość prymitywny sposób w mainie (ten graf posiada cykl Eulera)

 #include <iostream>
#include <stack>

using namespace std;

class node;
class vertex;

stack <int> Stack;

class node
{
public:
    node() : ptr(NULL){}
    vertex *ptr;
};
//vertex czyli dowolny wierzcholek w naszym grafie
class vertex
{
public:
    vertex(int iden,vertex *nxt):id(iden),next(nxt){}
    vertex *next;
    int id;
};

void remove_edge(node Graph[],int w, int v)
{
    vertex *ptr=Graph[w].ptr;
    if(ptr->id==v)
    {
        vertex *temp=ptr->next;
        delete temp;
        Graph[w].ptr=temp;
        return;
    }

    while(ptr->next)
    {
        if(ptr->next->id==v)
        {
            vertex *temp=ptr->next->next;
            delete ptr->next;
            ptr->next=temp;
            return;
        }
        ptr=ptr->next;
    }
}

int tour (node Graph[], int v)
{
    while (true)
    {   //  program destroys graph
        vertex *ptr = Graph[v].ptr;
        if (ptr == NULL)
            return v;
        int w = ptr->id;
        Stack.push(w);
        remove_edge(Graph,v, w);    //  delete two Graph objects
        remove_edge(Graph,w, v);
        v = w;
    }
}

int main()
{
    const int Nodes=7;
    node my_graph[Nodes];
    my_graph[0].ptr=new vertex(1,new vertex(5,new vertex(6,NULL)));
    my_graph[1].ptr=new vertex(0,new vertex(2,NULL));
    my_graph[2].ptr=new vertex(1,new vertex(3,NULL));
    my_graph[3].ptr=new vertex(2,new vertex(4,NULL));
    my_graph[4].ptr=new vertex(2,new vertex(3,new vertex(5,new vertex(6,NULL))));
    my_graph[5].ptr=new vertex(0,new vertex(4,NULL));
    my_graph[6].ptr=new vertex(0,new vertex(4,NULL));

    int v=0;
    while (tour(my_graph, v) == v && !Stack.empty())
    {
        v = Stack.top();
        Stack.pop();
        cout << " -" << v;
    }
    //remove_edge(my_graph,4,7);

    return 0;
}

Dlaczego program się wysypuje?

edytowany 2x, ostatnio: Mikilll, 2016-01-24 16:23

Pozostało 580 znaków

2016-01-24 16:54
2

Error wskazuje na problem z wywołaniem delete. Robisz to dwa razy więc przyjrzyj się temu dokładnie. Z tego co widzę, możesz użyć delete tylko na wskaźniku stworzonym przy pomocy new.

edytowany 1x, ostatnio: szweszwe, 2016-01-24 17:01
po deletach mam return od razu, więc gdzie niby 2 razy - Mikilll 2016-01-24 17:02
Dwa razy w sensie, że masz to w 2 miejscach w programie. - szweszwe 2016-01-24 17:04

Pozostało 580 znaków

2016-01-24 16:58
kq
3

Nie do końca rozumiem ten kod:

        delete temp;
        Graph[w].ptr=temp;

Dlaczego nie używasz unique_ptr? Znacząco uprościłby kod.


ale tak jak to robie tez chyba moze byc (nie wiem co to jest unique_ptr) - Mikilll 2016-01-24 17:01
Po wywołaniu na wskaźniku delete nie masz prawa go użyć w żaden inny sposób poza nadpisaniem go nową wartością. unique_ptr:http://en.cppreference.com/w/cpp/memory/unique_ptr - kq 2016-01-24 17:05

Pozostało 580 znaków

2016-01-24 17:44
0

Dobra. Znalazłem jeden błąd, Funkcja remove_edge powinna tak wyglądać:

void remove_edge(node Graph[],int w, int v)
{
    vertex *ptr=Graph[w].ptr;
    if(ptr->id==v)
    {
        vertex *temp=ptr->next;
        delete ptr; //tu byl blad
        Graph[w].ptr=temp;
        return;
    }

    while(ptr->next)
    {
        if(ptr->next->id==v)
        {
            vertex *temp=ptr->next->next;
            delete ptr->next;
            ptr->next=temp;
            return;
        }
        ptr=ptr->next;
    }
} 

Dalej jednak program się wysypuje i nie wiem co moze byc powodem

Pozostało 580 znaków

2016-01-24 17:45
kq
1

Debugger w rękę i do dzieła!


no ja tu mam struktury danych to nie wiem jak się debuguje w sumie. Ja pisze w code blocks to tam debuger nie wchodzi do funkcji - Mikilll 2016-01-24 17:53

Pozostało 580 znaków

2016-01-24 18:17
1

Przyjrzyj się jeszcze temu fragmentowi gdzie wywołujesz 2 razy pod rząd

remove_edge

i sprawdź jakie są konsekwencje.

Pozostało 580 znaków

2016-01-24 18:58
0

Mam tu do czynienia z grafem nieskierowanym. Graf jest reprezentowany w postaci tablicy list. Muszę 2 razy wywołać tę funkcję, aby usunąć krawędzie w dwie strony. W funkcji remove_edge mam coś takiego:

void remove_edge(node Graph[],int w, int v)
{
    vertex *ptr=Graph[w].ptr;
...
}

Czyli wskaźnik ptr wskazuje na sąsiada, który jest na szczycie listy dla wierzchołka w grafie w.

Dla wywołania drugi raz tej funkcji z argumentami v, w, będę działał na innej liście czyli nie powinno być żadnych problemów.

edytowany 1x, ostatnio: Mikilll, 2016-01-24 18:59

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0