C++中的图形实现

Question

我想对图形进行一些操作。在我开始操作之前，我试图构建图形。但我不确定我做得是否正确。你能说我的方向是否正确吗？输入将如下所示：

• 一个
• 乙
• C
• 阿 乙 1
• A C 2
• B C 3

我已经将节点放入像这样的字符向量中：

vector<char> nodes;

我已经将边缘

放入像这样的边缘向量中：

class Edge
{
    private : 
    int length;
    char node1; 
    char node2;
    public : 
    Edge(int l, char n1, char n2);
};

Answer 1

您似乎正在寻求有效的解决方案。

据我所知，有两种规范的方法来实现图数据结构。第一种是边缘列表，这似乎是您选择的方法。图形结构由具有可选权重的边列表表示。请注意，您可能希望添加更多内容以使其结构更有效，具体取决于图形的用途。例如，如果需要快速查找节点的所有邻居的列表，则最好为每个事件节点存储一个边缘列表。

第二种方法是将图表示为类似矩阵的结构，其中条目 （i，j） 是一个布尔值，表示从节点 i 到节点 j 是否存在边。

Answer 2

这不是实现图形的有效方法。顶点和边是不同的实体，因此它们需要由不同的数据结构表示。

像 2 类：类顶点和类边缘。

还必须使用循环依赖的概念。有关更多详细信息，请查看此网站：

http://badboys.7p.com/notes/Graph%20-%20链接%20实施%20（C++）.htm

Answer 3

首先，你需要一个简单的 Node 类。节点类通常包含一个子节点的链表（使用列表！）。在您的情况下，您使用的是带有边缘的图形，因此您的节点应包含连接到子级的边缘链表。另外，我不确定为什么使用char来引用节点，您应该使用带有节点引用的 Node 类。