如何填写加权图的邻接表？-Java 学习之路

我正在尝试读取c中的文件并填充表示邻接列表的向量 . 该文件包含无向加权图的邻接列表表示 . 每行包含与该特定顶点相邻的节点元组以及长度那边缘 . 例如，第6行有6作为第一个条目，表示该行对应于标记为6的顶点 . 该行的下一个条目“141,8200”表示在顶点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
}

2 回答

首先我提取顶点并将其放入 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);
        }
    }

回复于 2024-04-19T18:31:00+08:00

另一种解决方案，你不需要atoi，而且会有点短 .

while (getline(ifs, line)) {
    for (string& ch : line) if (ch == ',') ch = ' ';        

    stringstream line_stream(line);
    int a; line_stream >> a;

    for (int node, length; line_stream >> node >> length; ) {
        v[a].push_back({ node, length });
    }
}

回复于 2024-04-19T18:31:00+08:00

如何填写加权图的邻接表？

2 回答

相关问题