在networkx中，如何检查一个无向图是否为树

Question

我想知道在networkx中检查某个无向图是否为树的简单方法。

- papafe

---

我不知道是否有一种优雅的方法可以使用networkx来完成，但是一个简单的深度优先遍历，并标记已访问的节点将起作用（如果找到一个已经访问过的节点，则存在循环因此它不是一棵树）。 - Blckknght

Answer 1

检查图G（V，E）的最快方法可能是检查| V | = | E | + 1并且G已经连接：

import networkx as nx
def is_tree(G):
    if nx.number_of_nodes(G) != nx.number_of_edges(G) + 1:
        return False
    return nx.is_connected(G)

if __name__ == '__main__':

    print(is_tree(nx.path_graph(5)))
    print(is_tree(nx.star_graph(5)))
    print(is_tree(nx.house_graph()))

- Aric

Answer 2

networkx 中有内建函数可以检查给定图的类型。

若要检查它是否为树形结构，请运行 networkx.is_tree(g)。请参见networkx 文档中有关树形算法的部分。

- Edward

---

这是一个很老的问题，在当时其实并没有这个函数。不仅如此，我知道这一点是因为我自己实现了它 ;) 但把它作为参考还是很有用的。 - papafe