我在使用邻接矩阵的图形实现中遇到问题。作为一点背景，我必须从文件中读取每一行，其中包含演员，他们上映的电影以及制作年份。我的工作是从文件创建图形。然后，该图将由演员的顶点组成，这些演员的边线关系是他们一起出演同一部电影。在文件中，演员是顶点，电影和发布年份是边缘。我找到了一种将顶点存储在std :: vector中的方法，并且还创建了一个名为struct的MovieInformation，它存储了string movieName和int movie year。这些也存储在vector< pair< int,MovieInformation>>中。
但是，我不知道如何将信息插入vector中，以使演员和他们上演的电影的信息保持在一起。
来自文件的示例输入为：
亚历克斯·韦尔1984史蒂文·斯卡尔斯（Steven Scales）停止有道理1984鲁宾·布拉德斯（Ruben Blades）无组织犯罪1989霍伊特·阿克斯顿（Hoyt Axton）1989年的无组织犯罪弗雷德·格温（Fred Gwynne）《无组织犯罪》，1989年
而输出将是
（演员）-[电影＃@ year]->（演员）--...
至于代码部分，除了上面解释的内容之外，没有太多的书面内容。
首先，您需要简化顶点识别过程。我建议通过将参与者名称存储为字符串键，并将其对应的索引存储为无序映射中的值来枚举它们。这将产生O(1)预期的访问演员索引的时间。然后，您可以形成一组电影，其中包含在同一部电影中出演的演员的索引。当然，您还必须考虑电影的年份，因为可能会有两部不同的电影，它们的名称M在不同的年份问世。形成这些集合后，便会知道，对于与s年中出现的电影M相对应的集合Y，s中的所有顶点对之间都具有边。 >
考虑到输入有N行，可以有O(N)电影和O(N)演员。有了这些信息，我们可以说枚举边将花费O(N)预期时间。另外，枚举每部电影并为每部电影形成一个集合也将花费O(N)预期时间。在使所有演员都在同一电影中的最坏情况下，边缘的形成将花费O(N*N)时间。总体而言，即使考虑了unordered_map的最坏情况下的时间复杂度，您最终也会获得O(N*N)的最坏情况下的性能。
邻接矩阵的情况相差不大。您只需要使用N x N初始化adjacencyMatrix矩阵0，表示任何节点之间都没有连接。然后，您执行我上面介绍的枚举和分组（即集合）策略。然后，对于具有索引i和j的每对演员，设置adjacencyMatrix[i][j] = adjacencyMatrix[j][i] = 1。总体复杂度仍为O(N*N)。并且由于您将需要O(N*N)的时间和空间复杂度来分配和填充NxN矩阵，因此，除非提供任何其他详细信息/限制，否则您可能可以实现最佳的时间和空间复杂度。