c++ - 动态添加到图形数据结构

Question

首先让我声明，我只是想要方向，不一定是实际代码，除非一个小片段是表达要点的唯一方法。

我需要在 C++ 中使用邻接表或矩阵创建一个有向图数据结构，并从标准输入添加顶点/边，这意味着动态。

如果我能够首先实例化一组顶点，然后创建边并将它们添加到图中，我认为我能够很好地创建一个图，但我不明白如何添加一个包含尚未实例化的顶点的边。

例如，标准输入的第一行是:

迈阿密 -> 纽约/1100 -> 华盛顿/1000 -> 阿尔伯克基/1700

如果纽约顶点尚未添加到图中，我应该如何添加从迈阿密到纽约的边？

谢谢大家指点!

Answer 1

how it is possible to add an edge which contains a vertex that hasn't been instantiated yet.

简单:实例化它..

我看不出有任何问题。假设 V 是目前看到的顶点集。 V 最初是空的。当您读取输入 x->y 时，您会得到它的终点(x 和 y)。如果其中任何一个未实例化(即不在 V 中)，则将其实例化并将其添加到顶点集中。

另一种看待它的方式:假设我们通过边集 E 来定义图。根据定义，任何边都是一对顶点，它们又定义了图的顶点集。