图的链表实现

Question

我是 C++ 的新手。

我正在尝试创建具有链接节点的图的邻接表实现，视觉上看起来像这样：

[Headnode Vertex | Next Node] -> [Adjacent Node Vertex | Next] -> etc
[0 | ]-> [1 | ]-> [2 | ]-> [NULL node]
[1 | ]-> [0 | ]-> [2 | ]-> [NULL node]
[2 | ]-> [0 | ]-> [1 | ]-> [NULL node]

3 个节点的图，顶点编号为 0-2，对吗？

所以这是我正在实施的代码：

struct node {
    int vertex;
    node *next;
};

node *headnodes;
bool *Visited;
bool cycles = false;// determine if a graph has cycles.

class Graph {

    private: 
        int n; // number of vertices
        int e; // number of edges
        //node *headnodes;

    public:  
        Graph(int nodes) // construtor
        {
            n = nodes;
            headnodes = new node[n]; // headnodes is an array of nodes.
            for (int i = 0; i < n; i++)
            {
                headnodes[i].vertex = i;
                headnodes[i].next = 0; //points null
            }
        }

        //This function is based off lecture notes (Lecture 13)
        //node graph
        int Graph::create()
        {
            //iterate through the head nodes
            for (int i = 0; i < n; i++) {
                cout << "Initializing " << i << "-th node.\n";
                if (i == 0){
                    //headnode 0 points to its adjacent nodes 1, and 2
                    headnodes[n].next = new node; //initialize new node
                    node link = headnodes[n]; //assign to new variable
                    link.vertex = 1;
                    link.next->vertex = 2;
                    link.next->next = 0;
//This works
                    cout << "vertex of first node: " << headnodes[n].next->vertex; 
                } else if (i == 1){
                    headnodes[n].next = new node; //initialize new node
                    node link = headnodes[n];
                    link.vertex = 0; //the first node
                    link.next->vertex = 3; //the second node
                    //the 3rd node
                    /*link.next = new node;
                    node *link2 = link.next;
                    link.next->next->vertex = 4;
                    link.next->next->next = 0;*/
                } else if (i == 2){
                    headnodes[n].next = new node; //initialize new node
                    node link = headnodes[n];
                    link.vertex = 0;
                    link.next->vertex = 3;
                    link.next->next = 0;
                }
            }
//This doesn't?
            cout << "Checking vertex";
            cout << "First node's link vert: " << headnodes[0].next->vertex; //ERROR, Access Violation!
            return 0;
        }
};

我想因为 headnodes 变量是全局的，所以它会很好，但它会导致运行时错误（访问冲突），显然它指向一个空节点（但它是全局的所以 wth）？我不明白哪里出了问题。

有人能指出我正确的方向吗？我觉得我很接近。

Answer 1

你的问题很简单。在您的 create 函数中，您尝试遍历邻接列表，但是您不断索引 n-th headnode ，您可能知道它在数组的边界之外。

您将 3 作为 nodes 传入并将其分配给 n，然后在您的循环中继续将其索引为 headnodes[n]。您可以通过在每次访问 headnodes 之前添加 cout << n << endl; 来验证这一点；您每次都会看到 3。

您可能希望根据 i 对它们进行索引，因为那将是迭代索引。

图的链表实现

Linked List implementation of a Graph

c++

graph-theory