时间复杂度:节点 A 和节点 B 之间的所有路径是否与节点 X 或节点 Y 相交

Question

如果我有一个至少 4 个节点的图，那么它的最小时间复杂度是多少？

注意：我不是计算机科学家，我是哲学博士生，所以我提前为我的无知道歉。

Answer 1

算法：从图中移除节点 X 和 Y，然后查看 A 和 B 是否仍然连接。你可以从A到B.删除X和Y的时间复杂度是常数O（1），广度优先搜索的时间复杂度是O（E + V），这被认为是图形的"线性"。因此，对于一般图形，整体复杂性将是"线性的"。