graph - 在图上打印所有可能路径的复杂性

Question

在无向、未加权的图中，我试图打印（存储在文件中）图上给定 2 个顶点之间的所有可能连接路径，不包括循环。

当你考虑一个完整的图时，这个问题是一个 NP 完全问题。因为两个顶点之间有"(V-2)!"不同的路径。

但是，似乎可以使用时间复杂度O(|V|+|E|)相当多项式的图遍历 (DFS-BFS) 算法之一来实现。

我对在多项式时间内解决 NP 完全问题感到困惑？关于这里缺少什么的任何想法？

Answer 1

如果您想要所有可能的路径，并且图有 V 个顶点和 E 个边，那么路径的数量将取决于连接的数量。考虑一个完全连接的图，其中每个点都连接到其他每个点。那么有(v-2)!可能的路径，对吧？好吧(v-2)! > V+E（大得多）。