如何填充带权图的邻接表？

Question

我正在尝试用C++读取一个文件，并填充表示邻接列表的向量。该文件包含一个无向加权图的邻接列表表示。每一行都由与该特定顶点相邻的节点元组以及该边的长度组成。例如，第6行具有6作为指示该行对应于标记为6的顶点的第一条目。这一行的下一个条目“141,820 0”指示在顶点6和顶点141之间存在长度为8200的边。这一行的其余对指示与顶点6相邻的其他顶点和相应边的长度。

文件例如：-

1 3,4 2,20 5,89
2 4,7 1 102

ifstream ifs;
string line;
ifs.open("dijkstraData.txt");
cout<<log(vertices)<<" "<<loops<<endl;
std::vector<vector < std::pair < int,int > > > CadjList(vertices);
while(getline(ifs,line)){
    // transfer the line contents to line_stream
    stringstream line_stream(line);
    //now what
}    

Answer 1

首先，我提取了顶点并将其放入a中，然后，我将所有后续字符串提取为rest,然后，只需要找到逗号并将两个子字符串转换为整数。我使用atoi将字符串转换为int，因为我的机器上没有C++11，但我将建议更新您的gcc并使用std：：stoi。

while(getline(ifs,line)){
        stringstream line_stream(line);
        line_stream>>a;
        while(line_stream>>rest){
            int pos = rest.find(",");
            string vertex = rest.substr(0,pos);
            string weight = rest.substr(pos+1,rest.length() - pos);
            int ver = atoi(vertex.c_str());
            int wei = atoi(weight.c_str());
            pair<int,int> foo(ver,wei);
            v[a-1].push_back(foo);
        }
    }