2

隣接行列として与えられたグラフがツリーであるかどうかを判断するための簡単なアルゴリズムは何ですか？

4

3 に答える 3

7

E + 1 = Vの場合、エッジの量（E）と頂点の量（V）を数えることができ、それは木であると見なすことができます。また、接続されているコンポーネントが1つあることを確認する必要があります。コンポーネントが1つしかないことを理解するには、DFSまたはBFSのいずれかを使用できます。

于 2012-12-04T05:13:00.397 に答える
6

ツリーはサイクルのないグラフであるため、グラフがツリーであるかどうかを検出するには、サイクルがあるかどうかを確認してください。これは、マトリックスをトラバースし、訪問したすべてのノードの履歴を保持し、ノードを訪問したときに、訪問したノードのセットに含まれているかどうかを確認することで実行できます。

これは、サイクルの検出に関する以前のSO投稿です。それは出発点です： 有向グラフが循環的であるかどうかを検出する方法は？

また、グラフの走査と隣接行列を調べて、実行する必要のあることをより適切に理解することもできます。

このすべての後で、まだ助けが必要な場合は、これまでに持っているものを投稿できます。

于 2012-12-04T00:18:54.647 に答える
2

いくつかのコード（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
'''
于 2012-12-05T17:58:19.333 に答える