Python中基于节点坐标的两点连通性判断（DFS实现困惑）

嘿，别担心，新手阶段遇到这种没现成边结构的图问题太正常了！我来一步步帮你搞定～

第一步：从节点数据构建邻接表 #

DFS的核心是知道每个节点的直接邻居，而你现在只有带坐标的节点，所以首先得根据距离阈值limit生成邻接表——这是一个字典，键是节点ID，值是所有和它直接连通的节点ID列表。

计算两点距离用欧氏距离就行，Python里可以直接用math.hypot(x2-x1, y2-y1)计算，省得自己写平方和开根号的代码，既简洁又不容易出错。

第二步：基于邻接表实现DFS #

有了邻接表，DFS就和常规示例逻辑一致了，核心要点：

• 用集合记录已访问节点，避免无限循环
• 递归访问当前节点的所有邻居，直到找到目标节点或者遍历完所有可达节点

完整代码示例 #

import json
import math

class Node:
    def __init__(self, node_id, x, y):
        self.id = node_id
        self.x = x
        self.y = y

def build_adjacency_list(nodes, limit):
    adjacency = {}
    # 先给每个节点初始化空的邻居列表
    for node in nodes:
        adjacency[node.id] = []
    # 遍历所有节点对，判断是否连通
    for i in range(len(nodes)):
        node_a = nodes[i]
        for j in range(i+1, len(nodes)):
            node_b = nodes[j]
            # 计算欧氏距离
            distance = math.hypot(node_b.x - node_a.x, node_b.y - node_a.y)
            if distance <= limit:
                # 互相添加为邻居
                adjacency[node_a.id].append(node_b.id)
                adjacency[node_b.id].append(node_a.id)
    return adjacency

def dfs(current_id, target_id, adjacency, visited):
    # 找到目标节点，直接返回True
    if current_id == target_id:
        return True
    # 标记当前节点为已访问，避免重复遍历
    visited.add(current_id)
    # 递归访问所有未被访问的邻居
    for neighbor_id in adjacency[current_id]:
        if neighbor_id not in visited:
            if dfs(neighbor_id, target_id, adjacency, visited):
                return True
    # 遍历完所有可达节点都没找到目标，返回False
    return False

def are_nodes_connected(start_id, end_id, nodes, limit):
    # 先构建邻接表
    adjacency = build_adjacency_list(nodes, limit)
    # 初始化访问集合
    visited = set()
    # 调用DFS判断连通性
    return dfs(start_id, end_id, adjacency, visited)

# 测试你的JSON示例
if __name__ == "__main__":
    # 模拟JSON解析（假设你已经完成了这一步）
    json_data = '''{
        "limit": 32.0,
        "nodes": [
            {"y": 9.0, "x": 65.0, "id": 0},
            {"y": 44.6, "x": 3.4, "id": 1},
            {"y": 1.5, "x": 98.9, "id": 2},
            {"y": 2.67, "x": 7.0, "id": 3},
            {"y": 3.0, "x": 65.0, "id": 4}
        ]
    }'''
    data = json.loads(json_data)
    # 转换成Node实例集合
    nodes = [Node(node['id'], node['x'], node['y']) for node in data['nodes']]
    limit = data['limit']

    # 测试案例1：节点0和4（直接连通）
    print(f"节点0和4是否连通？{are_nodes_connected(0, 4, nodes, limit)}")  # 输出True
    # 测试案例2：节点0和1（孤立节点，不连通）
    print(f"节点0和1是否连通？{are_nodes_connected(0, 1, nodes, limit)}")  # 输出False
    # 测试案例3：节点1和3（距离超过阈值，不连通）
    print(f"节点1和3是否连通？{are_nodes_connected(1, 3, nodes, limit)}")  # 输出False

关键细节说明 #

• 邻接表构建：用两层循环遍历所有节点对（只算i<j的情况），避免重复计算，写法直观易懂，适合新手。如果节点数量特别多，可以考虑空间换时间的优化，但目前这个版本足够应对大部分场景。
• 访问集合：用set来记录已访问节点，保证每个节点只被处理一次，防止递归陷入循环（比如A和B互相连通的情况）。
• 递归终止条件：要么找到目标节点立即返回True，要么遍历完所有可达节点后返回False。

如果还有哪个环节没搞懂，随时问我哦！

内容的提问来源于stack exchange，提问作者Skyris