How to represent a graph in a C++ program logically?

Asked By 260 points N/A Posted on -
qa-featured

Hi there.

I am just beginning to learn some C++ programming. It is quite interesting and flexible. I think it is a good habit to understand algorithms through implementing them in code. I studied some ways to represent graph in the computer. It seems to me that adjacency matrix is most simplest.

I have heard that they take a lot of space. My question is, how do I use adjacency list to reduce this memory consumption? Do I have to allocate the array size dynamically during runtime? How do I do it?

Is there any simpler way to manage adjacency list?

SHARE
Best Answer by softwaresynthesis
Answered By 0 points N/A #92825

How to represent a graph in a C++ program logically?

qa-featured

Joe

If you are using C++ , then why bother using an array with memset ()? Just use vectors instead. It's much easier; trust me. Instead of using

int arr [100]; //fixed use

Vector<int> arr; //no initial size

When adding an element to the last. Instead of

For (end=0; end<100; ++end) if (arr [end] =0) Brea;       

arr [end] = new value;

Use

arr. push_back (newval); //auto extend the arr and push the novel to the end

To know more about vector go to

http://en.cppreference.com/w/cpp/container/vector

Answered By 260 points N/A #92828

How to represent a graph in a C++ program logically?

qa-featured

Thanks a lot,

But how do I declare  a two dimensional vector?

vector<vector < int> > vv; 

I guess its becoming more complicated.

Answered By 0 points N/A #92829

How to represent a graph in a C++ program logically?

qa-featured

You don't need a two dimensional vector.  If your number of nodes has a max limit, you can use an array of vectors instead.

vector<int> adjList[mxNod];

And yes, vector of vector will also do the job. But it is not necessary to save space that much.

Answered By 260 points N/A #92830

How to represent a graph in a C++ program logically?

qa-featured

Thanks.

But how do I populate it?

int latest=0;

 for(int i=0;i<numberOfEdges;++i)
    {
        cin>>n1;
        cin>>n2;
        adjList[n1].[latest++]=n2;    //n2 is adjacent to n1
    }

Its crashing when I run.

Best Answer
Best Answer
Answered By 0 points N/A #92831

How to represent a graph in a C++ program logically?

qa-featured

That is because the size of the vector located at adjList[n1] is initially 0. So your program wont find it by accessing adjList[n1][pos] at the first time.

That is obvious because it is not yet created. Instead do something like this;

  for(int i=0;i<numberOfEdges;++i)
    {
        cin>>n1;
        cin>>n2;
        adjList[n1].push_back(n2);    //n2 is adjacent to n1
    }

Answered By 260 points N/A #92832

How to represent a graph in a C++ program logically?

qa-featured

Thank you very much. I really appreciate that.

Answered By 0 points N/A #92833

How to represent a graph in a C++ program logically?

qa-featured

You are most welcome.

 

Related Questions