algorithm - 在图中，找到连接到一个节点但未连接到另一个节点的所有节点的最快方法是什么？

Question

假设您有两个节点 P 和 Q。现在我们必须找到与 Q 有边但与 P 没有边的节点。最快的方法是什么？我应该使用什么算法或数据结构？目前，每当添加边时，我都会为每个节点维护一个向量，该向量保存连接到该节点的所有节点(让我们为第 ith 个节点调用此 Vi)。我也有邻接矩阵。我正在做的大致是这样的事情。

for each node in Vq<br/> check if it is connected to P using adjacency matrix<br/> do something with this node<br/>

您认为在这里可以更快地完成任何事情吗？

Answer 1

几乎相同的事情:

• 从邻接矩阵中取出P行和Q行
• 对于节点 I，
  • 如果第I列P行为0，Q行为1，则进行运算。

这是明确表示在 for 循环内没有另一个循环来“检查它是否已连接”。

这是理论上最快的速度(这是 O(n)，理论上的下限是 O(n))。在实践中，您可以根据您使用的语言和优化的目的来优化它。例如，如果您将其表述为 Matlab 会喜欢它:

nodes = (~rowP)*rowQ';