سؤال

Tarjan's strongly connected components algorithm can only find fundamental cycles or all cycles that are in the graph ?

هل كانت مفيدة؟

المحلول

It cannot find all the cycles as long as it runs in O(V + E) (Polynomial time). If it could, it could solve hamiltonian cycle problem in polynomial time but this problem is NP-hard.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top