c++ - C++中的邻接表实现

Question

我正在寻找 C++ 中图形的简洁而精确的邻接表表示。我的节点只是节点 ID。我是这样做的。只是想知道专家对此有何看法。有没有更好的办法？

这是类实现(没什么特别的，现在不关心公共(public)/私有(private)方法)

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>

using namespace std;

class adjList {
public:
    int head;
    vector<int> listOfNodes;
    void print();
};

void adjList :: print() {
    for (int i=0; i<listOfNodes.size(); ++i) {
        cout << head << "-->" << listOfNodes.at(i) << endl;
    }
}

class graph {
public:
    vector<adjList> list;
    void print();
};

void graph :: print() {
    for (int i=0; i<list.size(); ++i) {
        list.at(i).print();
        cout << endl;
    }
}

我的主函数逐行解析输入文件。每行解释如下:

<source_node> <node1_connected_to_source_node> <node2_connected_to_source_node <node3_connected_to_source_node> <...>

这是主要的:

int main()
    {
        fstream file("graph.txt", ios::in);
        string line;
        graph g;
        while (getline(file, line)) {
            int source;
            stringstream str(line);
            str >> source;
            int node2;
            adjList l;
            l.head = source;
            while (str >> node2) {
                l.listOfNodes.push_back(node2);
            }
            g.list.push_back(l);
        }
        file.close();
        g.print();
        getchar();
        return 0;
    }

我知道我应该在 adjList 类中添加 addEdge() 函数，而不是直接从 main() 修改它的变量，但是，现在我只是想知道最好的结构。

编辑:我的方法有一个缺点。对于具有大量节点的复杂图，节点确实是一个结构/类，在这种情况下，我将通过存储整个对象来复制值。在那种情况下，我认为我应该使用指针。例如，对于无向图，我将在 adjList 中存储节点对象的拷贝(节点 1 和 2 之间的连接意味着 1 的邻接列表将具有 2，反之亦然)。我可以通过将节点对象的指针存储在 adjList 而不是整个对象中来避免这种情况。检查从这种方法中受益的 dfs 实现。在那里我需要确保每个节点只被访问一次。拥有同一个节点的多个拷贝会让我的生活更加艰难。没有？

在这种情况下，我的类定义将像这样更改:

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>

using namespace std;

class node {
public:
    node() {}
    node(int id, bool _dirty): node_id(id), dirty(_dirty) {}
    int node_id;
    bool dirty;
};

class adjList {
public:
    node *head;
    vector<node*> listOfNodes;
    void print();
    ~adjList() { delete head;}
};

void adjList :: print() {
    for (int i=0; i<listOfNodes.size(); ++i) {
        cout << head->node_id << "-->" << listOfNodes.at(i)->node_id << endl;
    }
}

class graph {
public:
    vector<adjList> list;
    void print();
    void dfs(node *startNode);
};

void graph::dfs(node *startNode) {
    startNode->dirty = true;
    for(int i=0; i<list.size(); ++i) {
        node *stNode = list.at(i).head;
        if (stNode->node_id != startNode->node_id) { continue;}
        for (int j=0; j<list.at(i).listOfNodes.size(); ++j) {
            if (!list.at(i).listOfNodes.at(j)->dirty) {
                dfs(list.at(i).listOfNodes.at(j));
            }
        }
    }
    cout << "Node: "<<startNode->node_id << endl;
}

void graph :: print() {
    for (int i=0; i<list.size(); ++i) {
        list.at(i).print();
        cout << endl;
    }
}

这就是我实现 main() 函数的方式。我正在使用 map<> 来避免对象重复。仅在先前未定义时创建新对象。通过对象的 id 检查对象是否存在。

int main()
{
    fstream file("graph.txt", ios::in);
    string line;
    graph g;
    node *startNode;
    map<int, node*> nodeMap;
    while (getline(file, line)) {
        int source;
        stringstream str(line);
        str >> source;
        int node2;
        node *sourceNode;
        // Create new node only if a node does not already exist
        if (nodeMap.find(source) == nodeMap.end()) {
                sourceNode = new node(source, false);
                nodeMap[source] = sourceNode;
        } else {
                sourceNode = nodeMap[source];
        }
        adjList l;
        l.head = sourceNode;
        nodeMap[source] = sourceNode;
        while (str >> node2) {
            // Create new node only if a node does not already exist
            node *secNode;
            if (nodeMap.find(node2) == nodeMap.end()) {
                secNode = new node(node2, false);
                nodeMap[node2] = secNode;
            } else {
                secNode = nodeMap[node2];
            }
            l.listOfNodes.push_back(secNode);
        }
        g.list.push_back(l);
        startNode = sourceNode;
    }
    file.close();
    g.print();
    g.dfs(startNode);
    getchar();
    return 0;
}

第二次编辑在 Ulrich Eckhardt 建议将邻接表放在节点类中之后，我认为这是一种更好的数据结构来存储图形并执行 dfs()、dijkstra() 类操作。请注意，邻接表在节点类中合并。

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>

using namespace std;

class node {
public:
    node() {
    }
    node(int id, bool _dirty): node_id(id), dirty(_dirty) {
        //cout << "In overloaded const\n";
    }
    int node_id;
    bool dirty;
    vector<node*> listOfNodes;
};

class graph {
public:
    vector<node*> myGraph;
    void dfs(node* startNode);
};

void graph::dfs(node* startNode) {
    startNode->dirty = true;
    for (int j=0; j<startNode->listOfNodes.size(); ++j) {
            if (!startNode->listOfNodes.at(j)->dirty) {
                dfs(startNode->listOfNodes.at(j));
            }
        }

    cout << "Node: "<<startNode->node_id << endl;
}

我们能做得更好吗？

Answer 1

有些地方可以改进，但总的来说您的方法是合理的。备注:

• 您正在使用 int作为容器的索引，这会给你一些编译器的警告，因为容器的大小可能超过表示为 int 的大小.相反，使用 size_t .
• 重写你的 for (int i=0; i<list.size(); ++i)至 for(size_t i=0, size=list.size(); i!=size; ++i) .使用 !=而不是 <将与迭代器一起工作。一次读取和存储大小使调试更容易，甚至可能更高效。
• 在要打印的循环内，你有list.at(i).print(); . list.at(i)将验证索引是否有效并在无效时引发异常。在这个非常简单的例子中，我确信索引是有效的，所以使用 list[i]相反更快。此外，它还隐含地记录了索引是有效的，而不是您期望它无效。
• print()函数应该是常数。
• 我不明白int head是什么意思是。这是节点的某种 ID 吗？ ID 不就是 graph::list 中的索引吗？ ？如果它是索引，您可以根据需要使用元素的地址减去第一个元素的地址来计算它，因此不需要冗余存储它。此外，请考虑在读取时验证该索引，这样您就没有任何边会到达不存在的顶点。
• 如果您不关心节点级别的封装(这是合理的!)，您也可以将其设为结构，这样可以节省一些输入。
• 存储指针而不是索引很棘手，但可以提高速度。问题是为了读取，您可能需要一个指向尚不存在的顶点的指针。有一个 hack 允许在不使用额外存储的情况下这样做，它需要首先将索引存储在指针值中(使用 reinterpret_cast)，然后在读取之后，对数据进行第二次传递，将这些值调整为实际地址。当然，你也可以使用第二遍来验证你没有任何边去到根本不存在的顶点(这是 at(i) 函数变得有用的地方)所以第二遍验证无论如何，一些保证是件好事。

根据明确要求，这里有一个如何在指针中存储索引的示例:

// read file
for(...) {
    size_t id = read_id_from_file();
    node* node_ptr = reinterpret_cast<node*>(id);
    adjacency_list.push_back(node_ptr);
}

/* Note that at this point, you do have node* that don't contain
valid addresses but just the IDs of the nodes they should finally
point to, so you must not use these pointers! */

// make another pass over all nodes after reading the file
for(size_t i=0, size=adjacency_list.size(); i!=size; ++i) {
    // read ID from adjacency list
    node* node_ptr = adjacency_list[i];
    size_t id = reinterpret_cast<size_t>(node_ptr);
    // convert ID to actual address
    node_ptr = lookup_node_by_id(id);
    if(!node_ptr)
        throw std::runtime_error("unknown node ID in adjacency list");
    // store actual node address in adjacency list
    adjacency_list[i] = node_ptr;
}

我很确定这在一般情况下是有效的，但我不是 100% 确定这是否一定有效，这就是为什么我不愿意在这里发布它。但是，我希望这也能说明为什么我要问“头”到底是什么。如果它真的只是容器中的索引，则几乎不需要它，无论是在文件内部还是在内存中。如果它是您从文件中检索到的某个节点的某种名称或标识符，那么您绝对需要它，但是您不能将它用作索引，那里的值也可以以 1 或 1000 开始它们的 ID，你应该捕获并处理它而不会崩溃!