关于邻接矩阵实现的问题

Question

我在使用邻接矩阵实现图时遇到问题。作为一个小背景，我必须从一个文件中读取每一行，其中包含一个演员、他们出演的一部电影以及电影的制作年份。我的工作是根据文件创建图表。然后，该图将由演员的顶点组成，演员的边关系是他们一起主演了同一部电影。在文件中，演员是顶点，电影和上映年份是边。我找到了一种将顶点存储在 std::vector 中的方法，并且还创建了一个名为 MovieInformation 的 struct 来存储 string movieName 和 int movie year。这些也存储在 vector< pair< int,MovieInformation>> 中。

但是，我不知道如何将信息插入 vector 中，以便演员的信息和他们出演的电影保持在一起。

来自文件的示例输入为：

Alex Weir   Stop Making Sense   1984
Steven Scales   Stop Making Sense   1984
Ruben Blades    Disorganized Crime  1989
Hoyt Axton  Disorganized Crime  1989
Fred Gwynne Disorganized Crime  1989

而输出将是

(actor)--[movie#@year]-->(actor)--...

至于代码部分，除了上面解释的内容外，没有写太多。

Answer 1

首先，您需要简化顶点识别过程。我建议通过将它们存储在一个无序映射中来枚举它们，其中演员名称作为字符串键，它们对应的索引作为值。这将产生 O(1) 访问演员索引的预期时间。然后，您可以形成集合电影，其中包含在同一部电影中出演的演员的索引。当然，您还必须考虑电影的年份，因为可能有两部名为 M 的不同电影在不同年份上映。一旦你形成了这些集合，那么你就会知道对于 Y 年上映的电影 M 对应的集合 s，[=14= 中的所有顶点对]他们之间有优势。

枚举过程类似于下面的代码。

void populate(vector<string>& actorNames, unordered_map<string, int>& indexMap) {
    int nextIndexToAssign = 0;
    for(int i=0; i < input.size(); ++i) {
        if(indexMap.find(input[i]) == indexMap.end()) {
            indexMap[input[i]] = nextIndexToAssign++;
        }
    }
}

在运行一段类似于上面实现的代码后，可以通过indexMap[actorName]访问演员的索引，其中actorName是存储演员姓名的字符串变量.您可以对电影做类似的事情，其中的键是 pair<string, int> 而不是 string.

枚举完成后，您可以使用 set 的向量作为存储桶来存储主演同一部电影的演员。

typedef pair< string, pair<string, int> > InputLine;
vector<InputLine> input; // defined somewhere, has size N
...

M = movieIndices.size();
vector< set<int> > actorsInMovie(M);
for(int i=0; i < N; ++i) {
    string& actor = input[i].first;
    string& movie = input[i].second;
    int actorIndex = actorIndices[actor];
    int movieIndex = movieIndices[movie];
    actorsInMovie[movieIndex].insert(actorIndex);
}

然后，您需要做的就是遍历 actorsInMovie 并为 actorsInMovie[i] 中的每对索引 u 和 v 放置一条边在 u 和 v 之间。

请注意，以上代码尚未经过测试，并且由于问题陈述中缺少任何源代码，因此仅用作伪代码。

考虑到有 N 行输入，可以有 O(N) 部电影和 O(N) 演员。有了这些信息，我们可以说枚举边缘（即电影和年份对）将花费 O(N) 预期时间。此外，枚举每部电影并为每部电影形成一个集合将花费 O(N) 预期时间。在所有演员都在同一部电影中的最坏情况下，形成图的边会花费 O(N*N) 时间，因为您需要在所有 O(N) 对演员之间设置一条边。总的来说，即使 unordered_map 的时间复杂度是最坏的情况，在最坏的情况下，最终的时间复杂度也会是 O(N*N)。

邻接矩阵的细节不会改变时间复杂度。你只需要用0初始化一个N x N矩阵adjacencyMatrix的所有单元格，表明任何顶点a和b之间没有连接。然后执行我上面介绍的枚举和分组（即集合）策略。最后，对于索引为 i 和 j 的每对演员，您设置 adjacencyMatrix[i][j] = adjacencyMatrix[j][i] = 1。整体时间复杂度还是O(N*N)。并且由于您需要 O(N*N) 时间和 space 复杂度来分配和填充 NxN 矩阵，这是您可能实现的最佳时间和 space 复杂度，除非任何额外的details/restrictions 已提供您的用例。

关于邻接矩阵实现的问题

Question about adjacency matrix implementation

c++

graph

adjacency-matrix

undirected-graph