Cykl Eulera

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?

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.

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.

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

1

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

1

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

remove_edge

i sprawdź jakie są konsekwencje.

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.

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