Trying to create a graph with adjacency list in C++

Question

I am trying to create a graph with adjacency list structure in C++. When I execute the code, it goes into infinite loop. Somewhere in the addEdge function, I am making a mistake, which I cannot seem to find out. Any help is greatly appreciated. Thank you.

 class Graph
    {
        struct AdjListNode
        {
            int dest;
            AdjListNode* next;
        };
        AdjListNode* array;
        int V;
        bool directed;
    public:
        Graph (int V, bool directed);
        ~Graph();
        void addEdge(int src, int dest);
        void printGraph();
    };

#include <iostream>
#include "Graph.h"

using namespace std;

Graph::Graph(int nVertices,bool directed)
{
    this->V = nVertices;
    this->directed = directed;
    // Create an array of adjacency lists.  Size of array will be V
    this->array = new AdjListNode[V];
    for (int i = 0; i < V; i++)
    {
        this->array[i].next = NULL;
    }
}

Graph::~Graph()
{
    delete[] array;
}

void Graph::addEdge(int src, int dest)
{
    AdjListNode* newNode = new AdjListNode;
    newNode->dest = dest;
    newNode->next = &(this->array[src]);
    this->array[src].next = newNode;
    cout << "Deneme = " << this->array[src].dest << endl;
    if (this->directed == false)
    {
        newNode = new AdjListNode;
        newNode->dest = src;
        newNode->next = &(this->array[dest]);
        this->array[dest].next = newNode;
    }
}
void Graph::printGraph()
{
    for(int i=0; i < this->V; i++)
    {
        AdjListNode* pCrawl = &(this->array[i]);
        cout << "Adjacency list of vertex " << i;
        while (pCrawl)
        {
            cout << "-> " << pCrawl->dest;  
            pCrawl = pCrawl->next;
        }
        cout << endl;
    }
}

int main()
{
    // create the graph given in above fugure

    int V = 5;
    Graph* g = new Graph(V,false);
    g->addEdge(0, 1);
    g->addEdge(0, 4);
    g->addEdge(1, 2);
    g->addEdge(1, 3);
    g->addEdge(1, 4);
    g->addEdge(2, 3);
    g->addEdge(3, 4);

    g->printGraph();
    return 0;
}

Create a small graph, then step through the code line by line in a debugger to see where and why your infinite loop happens. — Some programmer dude
– Some programmer dude, Commented Jan 12, 2015 at 11:50
Work through the first addEdge by hand and see if the adjacency list for src is really terminated with a NULL afterwards. (Adjacency lists are much easier if you store indexes rather than pointers.) — molbdnilo
– molbdnilo, Commented Jan 12, 2015 at 11:58

MichaelCMS · Accepted Answer · 2015-01-13 17:23:35Z

1

Translating to a pseudo-code-ish language , your addEdge looks something like this :

Create a new empty node called A
Set destiation as given by input.
Assign the next entry of A the reference of src (let's call it B)
Assign the next entry of B as beeing A.

So right now A is next to B and B is next to A ! your pCrawl will just loop between these 2.

answered Jan 13, 2015 at 17:23

MichaelCMS

4,7732 gold badges26 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Trying to create a graph with adjacency list in C++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related