networkx.is_isomorphic 的复杂度是多少？
What is the complexity of networkx.is_isomorphic?
networkx.is_isomorphic(graph1, graph2) 的复杂度是多少？
我特别想知道有向无环图的情况。
干杯。
根据nx.is_isomorphic的文档实现了vf2算法，甚至给出了原始的科学参考。
"L. P. Cordella, P. Foggia, C. Sansone, M. Vento, “An Improved Algorithm for Matching Large Graphs”, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, pp. 149-159, 2001."
boost 库声明 vf2-algorithm 具有以下复杂性：
"The spatial complexity of VF2 is of order O(V), where V is the (maximum) number of vertices of the two graphs. Time complexity is O(V^2) in the best case and O(V!·V) in the worst case."
networkx.is_isomorphic(graph1, graph2) 的复杂度是多少？
我特别想知道有向无环图的情况。
干杯。
根据nx.is_isomorphic的文档实现了vf2算法，甚至给出了原始的科学参考。
"L. P. Cordella, P. Foggia, C. Sansone, M. Vento, “An Improved Algorithm for Matching Large Graphs”, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, pp. 149-159, 2001."
boost 库声明 vf2-algorithm 具有以下复杂性：
"The spatial complexity of VF2 is of order O(V), where V is the (maximum) number of vertices of the two graphs. Time complexity is O(V^2) in the best case and O(V!·V) in the worst case."