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

Asked By 260 points N/A Posted on -

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
Answered By 0 points N/A #92825

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

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

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

Answered By 260 points N/A #92828

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

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?

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.

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?

Thanks.

But how do I populate it?

int latest=0;

for(int i=0;i<numberOfEdges;++i)
{
cin>>n1;
cin>>n2;
}

Its crashing when I run.

Answered By 0 points N/A #92831

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

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

Answered By 260 points N/A #92832

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

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?

You are most welcome.