图中邻接表

Question

嗨，我正在尝试用下面的代码实现一个使用邻接列表的图形。

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

}

但是这个代码的问题是，只有当我的节点以连续的方式从0开始(0、1、2、3)时，它才会给出正确的答案。但是当我试图打印这个图的邻接列表时：

​

​

然后它给出了这个输出：

​

​

有人能告诉我我哪里错了吗？

Answer 1

您要添加的边与我所描绘的图形不一样，您正在输入边缘1, 3而不是边缘1, 5。

Answer 2

它打印0是因为您从i = 0启动了for循环，并且出于同样的原因它没有打印节点5 (循环结束于4，因为您将拥有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;
        }
    }

下面是我将如何更改您的代码:首先，我稍微更改了print()函数(添加了if()以查看当前行是否为空，并将int n参数更改为int maximum，该参数将容纳最高值节点，以便我们知道何时停止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;
            }
        }
    }

然后，在main()中添加maximum和aux变量，以存储上述最高值节点。我还把g.print(n)改成了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;
}

然而，我可能不是特里·A·戴维斯，但我知道如果你说你有4个节点，那4个节点将是12，2，3和4。我也知道，任何与图相关的问题都会有从1开始的节点，因此每个for loop都会从i = 1开始，或者至少这就是我被教导的方式。你的做法也许也是正确的，但我不确定。