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

Asked By I am Joe 260 points N/A Posted on - 05/13/2011

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?

• Status: Open
• Question Views: 2845
• Answer Count: 7
• Vote Up 26 Vote Down

• Answer Accepted: Yes
• Question Category: C++

Best Answer by softwaresynthesis

Go To Solution

Answered By softwaresynthesis 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

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

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By I am Joe 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.

About I am Joe

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By softwaresynthesis 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.

vector<int> adjList[mxNod];

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

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By I am Joe 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;
        adjList[n1].[latest++]=n2;    //n2 is adjacent to n1
    }

Its crashing when I run.

About I am Joe

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Best Answer

Best Answer

Answered By softwaresynthesis 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;
        adjList[n1].push_back(n2);    //n2 is adjacent to n1
    }

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By I am Joe 260 points N/A #92832

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

Thank you very much. I really appreciate that.

About I am Joe

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By softwaresynthesis 0 points N/A #92833

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

You are most welcome.

 

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++