这将取决于一些更细粒度的定义，例如，如果边缘具有反向链接。这很容易，因为您可以按照树的反向链接进行操作。否则，在没有O（lg 个节点数 ）空间的情况下，我无法想到一种可行 的方法 ，因为您至少需要记住“上方”的节点。
哦，等等，当然可以在O（1） 空间 中进行时空交易。您想在任何地方做反向链接，保存您的位置并进行BFS，跟踪最近的节点，直到找到您的节点。然后备份到最近访问的节点并继续。
问题是，这是O（1）空间，但是O（n ^ 2）时间。
假设我们已经到达节点n_i，并且想要到达该节点的父节点，我们将其称为wlg n_j。我们已经确定了专有根节点n_0。
修改呼吸优先搜索算法，以便当它遵循有向边（n_x，n_y）时，将存储传出或“传入”节点。因此，当您遵循（n_x，n_y）时，将保存n_x。
当您从n_0重新启动BFS时，可以确保（假设它确实是一棵树）在某个点处，您将过渡边缘（n_j，n_i）。到那时，您发现您回到了n_i。您已经存储了n_j，所以您知道反向边缘是（n_i，n_j）。
因此，您将获得只有两个额外单元的单个回溯，一个用于n_0，一个用于“保存”节点。这是O（1）
我不太确定O（n ^ 2）-已经很晚了，这已经很辛苦了，所以我不想撰写证明。我确定它是O（（| N | + | E |）^ 2）其中| N | 和| E | 分别是顶点集和边集的大小。
602392714
清零编程群