Hi I am try to implement a graph using adjacency list using following code.

#include<iostream>
#include<list>
#include<vector>
#include<unordered_map>
using namespace std;

class graph{
    public:
    vector<int> adj[10000];

void insert(int u,int v, bool direction) {
    adj[u].push_back(v);

    if(direction==1) {
        adj[v].push_back(u);
    }

}

void print(int n) {


       for(int i=0;i<n 1;i  ) {
            cout<<i<<"->";
            for(auto j : adj[i]) {
                cout<<j<<",";
        }
        cout<<endl;
        }
    }
    
};
int main( ) {
    
    int n;
    cout<<"Enter no of node"<<endl;
    cin>>n;
cout<<"enter edges "<<endl;
int m;
cin>>m;
graph g;
for(int i=0;i<m;i  ) {
    int u, v;
    cin>>u>>v;
    g.insert(u,v,1);
}
g.print(n);
return 0;

}

But the problem with this code is that it will give correct answer only in the case when my node start from 0 in a continuous manner(0,1,2,3). But when I try to print adjacency list of this graph:

Then it is giving this output:

Can somebody tell me where am I wrong?

CodePudding user response：

The edges you are adding aren't the same as the graph i picture, you are inputting edge 1, 3 instead of edge 1, 5.

CodePudding user response：

It's printing the 0 because you started that for loop from i = 0 and it doesn't print node 5 for the same reason (the loop ends at 4 because you will have i < 4 1.

void print(int n) {
             //↓↓↓ HERE
       for(int i=0;i<n 1;i  ) {
            cout<<i<<"->";
            for(auto j : adj[i]) {
                cout<<j<<",";
        }
        cout<<endl;
        }
    }

Here is how I would change your code: First, I changed the print() function a little (added the if() to see if the current row is empty and I changed the int n parameter to int maximum which will hold the highest value node so we know when to stop the for).

void print(int maximum)
    {
        for(int i=0; i<=maximum; i  )
        {
            if(!adj[i].empty())
            {
                cout<<i<<"->";

                for(auto j : adj[i])
                {
                    cout<<j<<",";
                }
                cout<<endl;
            }
        }
    }

Then, in main() I added the maximum and aux variables in order to store the aforementioned highest value node. And I also changed the g.print(n) to g.print(maximum).

int main( )
{

    int n, maximum = 0, aux;
    cout<<"Enter no of node"<<endl;
    cin>>n;
    cout<<"enter edges "<<endl;
    int m;
    cin>>m;
    graph g;
    for(int i=0; i<m; i  )
    {
        int u, v;
        cin>>u>>v;
        g.insert(u,v,1);

        aux = max(u, v);
        maximum = max(maximum, aux);
    }
    g.print(maximum);
    return 0;
}

However, I might not be Terry A. Davis, but I know that if you say you have 4 nodes, those 4 nodes will be 1 2 3 and 4. And I also know that any graph related problem will have nodes starting from 1, therefore every for loop would start from i = 1, or at least that's how I was taught. The way you did it might be correct too, but I am not sure.