algorithm - 确定图是否为树的算法

Question

什么是确定作为邻接矩阵给出的图是否是树的简单算法？

Answer 1

如果 E + 1 = V，您可以计算边数 (E) 和顶点数 (V)，您可以假设它是一棵树。您还需要检查是否有一个连接的组件。要弄清楚它只包含一个组件，您可以使用 DFS 或 BFS。

Answer 2

树是没有环的图，因此要检测您的图是否是树，请检查它是否有任何环。这可以通过遍历矩阵来完成，保留每个访问节点的历史记录，并在访问节点时检查它是否在访问的节点集中。

这是以前关于检测周期的 SO 帖子。这是一个起点： 如何检测有向图是否是循环的？

您还可以学习图遍历和邻接矩阵，以便更好地了解您需要做什么。

如果在所有这些之后，您仍然需要帮助，您可以发布您到目前为止所拥有的内容。

Answer 3

一些代码（在 Python 中）：

def is_tree(G):
    n = len(G)
    M = [False]*n

    def dfs_tree(u, v):
        M[v] = True

        return all(w==u or not M[w] and dfs_tree(v, w) for w in range(n) if G[v][w])

    return dfs_tree(0, 0) and all(M)

print is_tree([
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0],
])

'''
 0-1 
 |
 2

 True
'''


print is_tree([
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
])

'''
 0-1 
 |/
 2 

 False
'''