Представление графа с использованием связанного списка

У меня возникли проблемы с попыткой выяснить, как правильно настроить указатели при добавлении ребер к определенной парной вершине.

Ниже приведена краткая идея о том, как должен выглядеть связанный список после завершения ввода вершин и узлов.

Как я могу поддерживать порядок в соседнем списке? Должно ли быть другое условие, если в текущей вершине уже есть ребро вершины?

Вот структурированный класс, который я пытаюсь построить:

class graph{
private:
    typedef struct node{
        char vertex;
        node * nodeListPtr;
        node * neighborPtr;

    }* nodePtr;
    nodePtr head;
    nodePtr curr;
public:
    graph();
    ~graph();

    void AddNode(char AddData);
    void AddEdge(char V, char E);
    void printList();
};

graph::graph(){
    head = NULL;
    curr = NULL;
}

// Adds a node to a linked list
void graph::AddNode(char AddData){
    nodePtr n = new node;
    n->nodeListPtr = NULL;
    n->vertex = AddData;

    if(head != NULL){
        curr = head;
        while(curr->nodeListPtr != NULL){
            curr = curr->nodeListPtr;
        }
        curr->nodeListPtr = n;
    }
    else{
        head = n;
    }
}

// takes 2 Parameters (V is pointing to E)
// I want to set it up where the neighborptr starts a double linked List basically
void graph::AddEdge(char V, char E){
    // New Node with data
    nodePtr n = new node;
    n->neighborPtr = NULL;
    n->vertex = E;
    // go to the first node in the nodeList and go through till you reach the Vertex V
    curr = head;
    while(curr->vertex != V){
        curr = curr->nodeListPtr;
    }
    //Once the Vertex V is found in the linked list add the node to the neighborPtr.
    curr->neighborPtr = n;

}

Чего я пытаюсь достичь в моем представлении диаграммы связанного списка


c++ class graph doubly-linked-list
person Conor    schedule 02.08.2013    source источник
comment
Это должен быть общий график? Если это так, рассмотрите возможность использования списка смежности: en.wikipedia.org/wiki/Adjacency_list   -  person Codie CodeMonkey    schedule 02.08.2013

Ответы (1)


arrow_upward
0
arrow_downward

Одна проблема, с которой вы сейчас сталкиваетесь, заключается в том, что у каждого узла может быть только один «краевой» узел. На вашем рисунке все узлы A, C и D возможны, но узел B не обходится без того, чтобы немного по-другому.

Проблема возникает здесь:

curr->neighborPtr = n;

Каждый раз, когда вы вызываете AddEdge() для одной и той же вершины, он просто перезаписывает соседний элемент этой вершины. Вы не предпринимаете никаких усилий, чтобы обойти соседние точки, пока не найдете нулевой указатель.

Рассмотрите возможность добавления еще одного цикла while для рекурсивного добавления ребер:

while (curr->neighborPtr != null)
    curr = curr->neighborPtr;
curr->neighborPtr = n;

Обратите внимание, что это не единственная проблема в вашем коде; у вас есть несколько мест, где вы должны защищаться от нулевых указателей, а не против. Например: в AddEdge(), что произойдет, если вершина V не может быть найдена? Вы действуете исходя из предположения, что он уже создан. Если это не так, вы получите некоторые ошибки нулевого указателя. Имейте это в виду, если вы пытаетесь создать не только функциональный, но и надежный код.

person Zeimyth    schedule 02.08.2013