CODEWITHSUNDEEP
c++graph-theory
mastrgamr
mastrgamr

Reputation: 631

Linked List implementation of a Graph

I'm pretty new to C++.

I'm trying to create an adjacency list implementation of a graph with linked nodes, visually it'll look something like this:

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

A graph of 3 nodes, with vertices numbered 0-2, right?

So Here is the code I am implementing:

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;
        }
};

I figured since the headnodes variable is global it would be fine but it's causing a RunTime error (Access Violation), apparently it's pointing to a null node (but it's global so wth)? I don't get what's wrong.

Can someone point me in the right direction. I feel I'm close.

Upvotes: 0

Views: 1620

Answers (1)

ChiefTwoPencils
ChiefTwoPencils

Reputation: 13940

Your problem is pretty straight forward. In your create function you try to iterate over the adjacency lists however you continually index the n-th headnode which you probably know is outside the bounds of the array.

You pass in 3 as nodes and assign it to n and in your loop continue to index it as headnodes[n]. You can verify this by adding cout << n << endl; before each access of headnodes; you'll see 3 each time.

You likely want to index them according to i as that would be the iteration index.

Upvotes: 1

Related Questions