1

我有一个文本文件，可以从中读取无向图。格式如下：

1 2 3
2 1
3 1

行中的每个第一个元素对应一个顶点，其余的基本上是顶点的邻接表。

所以我的两个问题是：

  • 1) 在 C++ 中阅读此信息的最佳方式是什么？使用以下代码段，我可以依次读取所有信息，但这当然不是我最终想要实现的。我希望能够以一种体面的方式分离不同行的信息。（这部分实际上与我的第二个问题密切相关，如下所示）

    void inputHandle(ifstream& f, int arr[], string fileName)
{

    f.open(fileName);

    if (!f) {
        cout << "Unable to open file";
        exit(1); // terminate with error
    }

    string temp;
    int i = 0, numTemp;

    while(f >> temp){
        numTemp= atoi(temp.c_str());
        arr[i] = numTemp;
        cout<<arr[i];
        i++;
    }

    f.close();
}

  • 2) 保存此图的最佳数据结构是什么？我将实现一个 mincut 算法，因此我将在每次迭代时修改图形（删除/修改行）。

在此先感谢您的帮助。

4

1 回答 1

2

我会将图形存储为邻接列表或矩阵，在 C++ 中，这是一种编码方式。根据性能/存储要求，您可能需要对此进行调整。

vector< list<int> > graph;

或者您可以使用邻接矩阵。

vector< vector<bool> > graph;

至于读取您的文件格式，我会使用getline()逐行读取文件，然后解析每一行的整数值（可能使用istringstream），可能是这样的：

ifstream f;

vector< list<int> > graph;

f.open(fileName);
while(!f.eof() && !f.fail())
{
    char line[1024]; // Reserve enough space for longest line
    f.getline(line, 1024);

    istringstream iss(line, istringstream::in);

    int vertex;
    iss >> vertex;
    if(!f.fail())
    {
        if(vertex > graph.size()) // Max number of vertex is unknown
        {
            graph.resize(vertex); 
        }
        vertex--; // From your 1-base to zero-based
        list<int>& vertex_list = graph[vertex];
        do
        {
            int to_vertex;
            iss >> to_vertex;
            if(!iss.fail())
            {
               vertex_list.push_back(to_vertex - 1);
            }
        } while(!iss.eof() && !iss.fail());
    }
}
于 2012-04-09T21:50:55.737 回答