CODEWITHSUNDEEP
c++c++11stlgraph-algorithm
Tushar
Tushar

Reputation: 97

How to use vector of vector for reading a graph?

#include <iostream>
#include <vector>
using namespace std;
void addEdge( vector<vector<int> > adj, int, int);
void print_graph(vector<vector<int> > adj);


int main()
{

    vector<vector<int> > adj(4);
    addEdge(adj,1,2);     // edge from node 1 to node 2
    addEdge(adj,1,3);
    addEdge(adj,1,4);
    addEdge(adj,2,3);
    addEdge(adj,3,4);
    print_graph(adj);
    return 0;
}

void addEdge(vector<vector<int> > adj, int u , int v)
{
    adj[u].push_back(v);

}

void print_graph( vector<vector<int> > adj)
{
    for( int i = 0; i < adj.size() ; i++ )
    {
        for( int j = 0 ; j < adj[i].size(); j++ )
        {
            cout<< i+1 << " , " << cout<< adj[i][j]<<endl;
        }
    }
}

I have written the code for reading the graph and printing it.
Prior to this for reading graph I used to use 

vector<int>adj[5];

But I have been told that , use 

`vector<vector<int> > adj`  or `list<list<int> > adj`

I tried but now I am getting No output. ( update)

Can anyone help me in using vector of vector ?? Please help for list of list also.

Upvotes: 1

Views: 5323

Answers (4)

peje
peje

Reputation: 370

Your version of addEdge takes adj as a copy. You manipulate that copy which is then destroyed when the function returns. You need to use reference to access the outer adj:

void addEdge(vector<vector<int> >& adj, int u , int v)
{
    adj[u].push_back(v);

}

and use:

void print_graph(const vector<vector<int> >& adj)

to avoid another copy

Upvotes: 2

m.matheson
m.matheson

Reputation: 1

When you create the vector adj, you have an empty vector. In your function addEdge, you access the entry at index u in adj. But remember, that is an empty vector. This is where your crash comes from.

I assume your function addEdge is supposed to add an entry to this adjacency matrix you are creating. Before that, you need to create space for that matrix. Meaning, you need to make space in your adj vector for the vectors it will contain, and you also need to make space in those vectors where you can put the edge information.

Once you have your vectors set up though, your print function will still print all 0's because your function addEdge makes a copy of the vector you are passing, then writes to that copy. The original adj vector will be unchanged. Be sure to pass the vector by pointer if you want to modify the original.

Upvotes: 0

6502
6502

Reputation: 114461

To use a vector of vectors you could write

std::vector<std::vector<int>> adj(5); // Note: round parentheses

This works because standard vectors have a constructor that accepts the requested size as parameter and default-initializes all elements.

Being adj a vector of vectors the elements of adj will be initialized as empty vectors, that you can later fill with push_back.

Upvotes: 3

Jay
Jay

Reputation: 656

Vectors use zero-based indexing. adj[0] is the first element in the vector.

Also vectors start with no size. There will be no adj[0] element until you add one.

You may want to adj.resize(4) before you try and call adj[u].push_back(v).

Upvotes: 0

Related Questions