如何用JS递归函数结合邻接表追踪子图？

核心问题解决思路 #

• 函数返回值：返回包含所有初始节点及其连通节点的去重ID列表，用集合存储中间结果避免重复，最终转为列表输出
• 遍历与终止逻辑：采用DFS（递归）或BFS（非递归）实现，终止条件为遍历完所有可达节点，通过已访问集合避免重复遍历

完整代码实现 #

基础邻接表类（基于你提供的骨架） #

class AdjacencyList:
    def __init__(self):
        self.graph = {}  # 键: 节点ID，值: 相邻节点ID列表

    def add_edge(self, u, v):
        # 双向添加边
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)

递归DFS实现的traceSubGraph函数 #

class AdjacencyList:
    # 保留__init__和add_edge方法...

    def traceSubGraph(self, start_nodes):
        visited = set()

        def dfs(node):
            # 终止条件：节点已访问过，直接返回
            if node in visited:
                return
            # 首次访问时加入已访问集合
            visited.add(node)
            # 递归遍历所有邻接节点
            for neighbor in self.graph.get(node, []):
                dfs(neighbor)

        # 遍历所有初始节点，启动DFS
        for node in start_nodes:
            if node in self.graph:  # 跳过图中不存在的初始节点
                dfs(node)
        
        # 返回去重后的节点ID列表
        return list(visited)

非递归BFS实现（适合大规模图，避免栈溢出） #

class AdjacencyList:
    # 保留__init__和add_edge方法...

    def traceSubGraph(self, start_nodes):
        visited = set()
        from collections import deque

        # 初始化队列，加入有效初始节点
        queue = deque()
        for node in start_nodes:
            if node in self.graph and node not in visited:
                visited.add(node)
                queue.append(node)
        
        # BFS遍历逻辑
        while queue:
            current_node = queue.popleft()
            # 遍历所有邻接节点
            for neighbor in self.graph.get(current_node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return list(visited)

关键逻辑说明 #

• 节点加入时机：首次访问节点（包括初始节点和邻接节点）时，立即加入visited集合，确保不遗漏、不重复
• 终止条件：
  • DFS中，若节点已在visited中则直接终止递归分支
  • BFS中，当队列为空时终止循环，所有可达节点已被遍历
• 边界处理：跳过图中不存在的初始节点，避免KeyError

测试驱动代码 #

if __name__ == "__main__":
    # 初始化图
    al = AdjacencyList()
    al.add_edge(1, 2)
    al.add_edge(2, 3)
    al.add_edge(4, 5)
    al.add_edge(5, 6)
    al.add_edge(3, 6)

    # 测试初始节点列表[2, 4]
    subgraph_nodes = al.traceSubGraph([2, 4])
    print(subgraph_nodes)  # 输出示例：[1,2,3,4,5,6]（顺序可能因遍历方式不同变化）

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