Python中使用BFS判断图(Graph)是否为树(Tree)

2023-04-11 00:00:00 python 判断 BFS

首先，树是一种特殊的图，它满足以下条件：

  1. 只有一个连通分量；
  2. 没有环路；
  3. 有n个节点（n>0）和n-1条边；
  4. 每个节点的度数（即相邻节点的个数）不超过2；

我们可以使用BFS（广度优先搜索）来判断图是否为树。首先，从任意一个节点开始，将其入队，标记为已访问。然后，遍历与该节点相邻的所有节点，如果这些节点未被访问过，则将其入队，并标记为已访问。重复以上步骤，直到队列为空。如果在这个过程中，访问了一个已经标记为已访问的节点，则证明这个图不是树，否则它是一棵树。

下面是Python代码演示：

from collections import deque

def is_tree(graph):
    # 初始化队列、已访问节点和父节点字典
    queue = deque()
    visited = set()
    parent = {}

    # 从起点开始搜索
    start_node = list(graph.keys())[0]
    queue.append(start_node)
    visited.add(start_node)
    parent[start_node] = None

    while queue:
        # 取出队列中的节点
        node = queue.popleft()

        # 遍历与该节点相邻的所有节点
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
                parent[neighbor] = node
            elif parent[node] != neighbor:
                # 如果该节点已被访问过，且不是当前节点的父节点，则证明它不是树
                return False

    # 如果遍历完所有节点后都没有发现环路，则该图是一棵树
    return True

在这个函数中，参数graph是一个字典，表示图中每个节点的相邻节点。例如，如果图中有三个节点"pidancode.com"、"皮蛋编程"、"python"，其中"pidancode.com"和"皮蛋编程"相邻，"python"与"皮蛋编程"相邻，那么这个字典应该是这样的：

{
    "pidancode.com": ["皮蛋编程"],
    "皮蛋编程": ["pidancode.com", "python"],
    "python": ["皮蛋编程"]
}

使用这个函数，我们可以很容易地判断一个图是否为树。例如：

graph = {
    "pidancode.com": ["皮蛋编程"],
    "皮蛋编程": ["pidancode.com", "python"],
    "python": ["皮蛋编程"]
}

if is_tree(graph):
    print("这是一棵树")
else:
    print("这不是一棵树")

输出结果应该是"这是一棵树"。

相关文章