给定边列表时如何不转换格式直接执行DFS或BFS遍历

核心思路：不需要提前把边列表转成邻接表/邻接矩阵，每次需要获取当前节点的所有相邻节点时，直接遍历全量边列表，筛选出包含当前节点的边，取边的另一端节点作为邻居即可。这种方法的时间复杂度会比邻接表实现高，适合边规模不大的场景。

BFS实现逻辑 #

• 初始化队列存储待遍历节点，首先将起始节点入队，同时初始化访问标记集合，把起始节点加入集合
• 只要队列不为空，弹出队首的当前节点，执行对应处理逻辑（比如打印、计数等）
• 遍历整个边列表，筛选所有包含当前节点的边，取出边中不等于当前节点的另一端作为邻居节点
• 如果邻居节点没有被访问过，标记为已访问后加入队列
• 重复上述步骤直到队列为空

代码示例（Python，无向图场景）：

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
def bfs(start):
    visited = set([start])
    queue = [start]
    while queue:
        cur = queue.pop(0)
        print(cur, end=' ')
        # 直接遍历边列表匹配邻居
        for u, v in edges:
            neighbor = None
            if u == cur:
                neighbor = v
            elif v == cur:
                neighbor = u
            if neighbor is not None and neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
# 从节点1开始遍历输出示例：1 2 4 5 3
bfs(1)

DFS实现逻辑 #

DFS和BFS的核心差异仅在于待遍历节点的存储结构，用栈替代队列即可，递归实现逻辑也同理：

• 初始化栈存储待遍历节点，首先将起始节点入栈，同时初始化访问标记集合，把起始节点加入集合
• 只要栈不为空，弹出栈顶的当前节点，执行对应处理逻辑
• 遍历整个边列表，筛选当前节点的所有邻居
• 把未访问的邻居标记为已访问后入栈
• 重复步骤直到栈为空

代码示例（Python，无向图场景）：

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
# 迭代版DFS
def dfs_iter(start):
    visited = set([start])
    stack = [start]
    while stack:
        cur = stack.pop()
        print(cur, end=' ')
        for u, v in edges:
            neighbor = None
            if u == cur:
                neighbor = v
            elif v == cur:
                neighbor = u
            if neighbor is not None and neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
# 从节点1开始遍历输出示例：1 5 4 3 2
dfs_iter(1)

注意：如果是有向图，找邻居的逻辑需要调整，只取边的出方向节点即可，比如边[u, v]表示u指向v，那么只有当u等于当前节点时，v才是邻居，v等于当前节点时不需要处理u。

内容的提问来源于stack exchange，提问作者The Lazy Programmer