C++ 模板图形类，递归

Question

我正在尝试用 C++ 编写图形类，实现为邻接表。我正在尝试使此类成为模板，以便节点和边缘可以包含任意有效负载。这是一个简单的想法，但我对语言如何支持这一点感到困惑。

我希望能够声明一个图如下:
graph<int, int>或者
graph<string,double>等等

第一个想法，从图形声明向后工作:

template<class ntype, class etype>
class node {

    class edge {
    etype payload;
        node<ntype, etype>* to;
        node<ntype, etype>* from;
    }   

    ntype payload;
    vector< edge<> > incoming; // How to avoid recursion ???
    vector< edge<> > outgoing; // ????
}

template<class ntype, class etype>
class graph {

    vector< node<ntype, etype> > nodes;
}

我对所涉及的递归、模板参数的范围等感到非常困惑。我尝试查看嵌套类、类型名与模板以及其他问题，但这并没有使它变得更清楚。现在看来，C 和 void 指针是编写此代码的绝对最佳方式。非常感谢任何帮助或引用。

Answer 1

我首先会在节点类之外声明边类。在这种情况下，我看不出将其设为嵌套类有什么好处。实际上，一般来说，嵌套类带来的弊大于利。 This问题对原因有很好的解释。

至于图形类的设计，我建议使用一个模板参数来表示有效负载(您可能希望图形节点携带的任意数据类型)，并使用第二个模板参数来表示权重(任何数值，例如 int 、 float 、 double 、 long 等)。

一些图形用例可能不关心图形是否加权，因此在这些情况下，您可以忽略权重字段，并且不使用它(将其保留为某个默认值，如 0，将是好的做法)。我还建议使用 std::list而不是 std::vector保存节点，以便在您需要向图形中添加许多节点时，不会发生内存重新分配。

考虑到上述情况，图形类将如下所示。注意我使用 D对于数据字段(有效载荷)，以及 W用于权重字段。

DirectedGraph.h

template <class D, class W> class DirectedGraph{

public: 

    DirectedGraph(){/*...*/}
    ~DirectedGraph(){/*...*/}

    /*Pushes a node into this graph, which will have no connections initially.*/
    void push(GraphNode<D, W> *node){/*...*/}

    /*Erases a node from this graph.*/
    void erase(GraphNode<D, W> *node){/*...*/}

    std::list<GraphNode<D, W>> &getNodes(){/*...*/}

private:

    /*This is the master list holding all nodes of this graph.*/
    std::list<GraphNode<D, W>> nodes;

};

节点和边(我称之为“邻居”)类看起来像这样:

GraphNode.h

/*Forward declaration of the edge structure (see below).*/
template <class D, class W> struct Neighbor;

template <class D, class W> struct GraphNode{

public:

    GraphNode(D data) : data(data) {}
    ~GraphNode(){}

    /*Some data this node element will hold*/
    D data;

    /*Adds an outgoing connection.*/
    void addConnection(Neighbor<D, W> neighbor){ /*...*/}

    /*You may also want to develop a 'removeConnectoin' method here.*/
    /*...*/

    /*Nodes that this one is connected to. Since this actually represents
    a connection (an edge), the struct 'Neighbor' is used, which encapsulates
    a pointer to a 'GraphNode' as well as the weight of the edge.*/
    std::list<Neighbor<D, W>> neighbors;

    /*Nodes that connect to this one. These are the incoming connections. Note
    that this is not of type 'Neighbor' because it does not represente an edge.
    It is just a record of which nodes have an outgoing connection to this one.*/
    std::list<GraphNode<D, W>*> parents;
};


/*This struct represents an edge*/
template <class D, class W> struct Neighbor{
    Neighbor<D, W>(GraphNode<D, W> *node, W weight) : node(node), weight(weight){}
    GraphNode<D, W> *node;
    W weight;
};

这里要注意的一件事是，使用 Neighbor 类的唯一原因是我们可以表示边的权重。如果您要使用的图表将始终未加权，您可以只替换 std::list的 Neighbor<D, W>对于 std::list的 GraphNode<D, W>* .您还可以删除模板参数 W来自您的实现。

哦，当然图头文件必须包含节点一。

我希望这是一个好的起点。有任何问题，请告诉我。