c++ - 如何在 C++ 的模板化图形类中使用 vector 创建邻接矩阵？

Question

是的，这是一项家庭作业(在你提问之前)，但我遇到了麻烦，我觉得这里的人比我的 CS 同学更自命不凡。

我的问题是，我需要做什么才能使用二维 vector 在 C++ 的模板图类中创建矩阵。我总能想象出我需要做什么，但在输入时遇到麻烦。

这是我目前所拥有的:

using namespace std;

namespace GraphNameSpace
{

   enum isDirected {DIRECTED, UNDIRECTED};
   enum isWeighted {WEIGHTED, UNWEIGHTED};

   template <class T>
   class Graph
   {
      public:
         Graph<T>();
         Graph<T>(isDirected);
         Graph<T>(isWeighted);
         Graph<T>(isDirected, isWeighted);
         Graph<T>(isWeighted, isDirected);

         void createMatix();
         void destroy();
         bool isEmpty() const;
         bool isFull() const;
         bool isAdjacentTo(T fromVertex, T toVertex) const;
         int edgeWeight(T fromVertex, T toVertex) const;
         int edgeCount() const;
         int vertexCount() const;
         void insertVertex(T Vertex);
         void insertEdge(T fromVertex, T toVertex, int weight);
         void deleteVertex(T Vertex);
         void deleteEdge(T fromVertex, T toVertex);
         int findVertex(T Vertex) const;
         void dump() const;

      private:
         vector<int> row(100);
         int numVertices;
         int numEdges;
         static isDirected dir;
         static isWeighted wght;
   };
}

我猜问题出在 vector row(100) 上，但也可能出在 void createMatrix() 上。我只是拼命地想了解如何执行此操作，因此将不胜感激带有示例代码的解释。 (其余代码完全如他所愿)。在此先感谢您尝试帮助我，非常感谢。

Answer 1

看起来你需要一个 T 的二维 vector 来存储你的顶点

像这样:

vector < vector < T > > Vertices;

但是，这是非常低效的!

也许要做的事情是拥有一个一维顶点 vector ，然后定义一条边并将所有边存储在另一个一维 vector 中。如果需要，您可以从中即时生成邻接矩阵。

vector < T > vertices;
typedef pair <int,int> edge_t;    // Indices into vertices vector
vector < edge_t > edges;

这不会浪费内存。

我看到的问题是在这个方案中没有办法存储边的属性(例如重量或长度或成本)。为此，您需要同时为边和顶点设置模板

 template <class V, class E>
   class Graph

因此，现在您需要一个用于用户边的 vector 、一个用于顶点的 vector 以及一个用于三个索引的 vector :源 vetrex、目标顶点和边。

也许是这样的:

vector < V > vertices;
vector < E > edges;
struct adjacency_s {
   int src;
   int dst;
   int edge;
};
vector < adjacency_s > adjacencies;

实际上，推出自己的图形代码并不是一个好主意。最好学习如何使用已建立的库作为 discussed here