大厂算法真题面试题, DFS

QA

Step 1

Q:: 请解释深度优先搜索（DFS）的基本概念，并描述其工作原理。

A:: 深度优先搜索（DFS）是一种用于遍历或搜索树或图形数据结构的算法。该算法会尽可能深地搜索树的分支，直到不能再深入，然后回溯继续搜索下一个分支。其工作原理是利用栈（可以使用递归调用栈实现），从起始节点出发，访问一个未被访问的相邻节点，重复此过程直到所有节点都被访问。

Step 2

Q:: 编写一个使用DFS遍历二叉树的代码示例。

A::

 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# 深度优先遍历（前序遍历）
def dfs_preorder(node):
    if node:
        print(node.val)
        dfs_preorder(node.left)
        dfs_preorder(node.right)
 
# 示例
root = TreeNode(1, TreeNode(2), TreeNode(3))
dfs_preorder(root)

Step 3

Q:: DFS与BFS（广度优先搜索）的主要区别是什么？

A:: DFS（深度优先搜索）和BFS（广度优先搜索）都是图遍历算法。主要区别在于：DFS尽可能深地搜索树的分支，使用栈结构；而BFS按层级逐层搜索，使用队列结构。DFS适用于搜索深度较深的解，而BFS适用于寻找最短路径。

Step 4

Q:: 在图中检测环路是否存在，可以使用DFS吗？如果可以，如何实现？

A:: 可以使用DFS检测图中的环路。在DFS的过程中，如果遇到一个已经在当前DFS路径中的节点，则存在环路。实现方式是使用一个递归栈记录当前路径上的节点。若在遍历过程中遇到栈中的节点，则说明存在环路。

 
class Graph:
    def __init__(self, vertices):
        self.graph = {i: [] for i in range(vertices)}
        self.V = vertices
 
    def add_edge(self, u, v):
        self.graph[u].append(v)
 
    def is_cyclic_util(self, v, visited, rec_stack):
        visited[v] = True
        rec_stack[v] = True
 
        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                if self.is_cyclic_util(neighbor, visited, rec_stack):
                    return True
            elif rec_stack[neighbor]:
                return True
 
        rec_stack[v] = False
        return False
 
    def is_cyclic(self):
        visited = [False] * self.V
        rec_stack = [False] * self.V
        for node in range(self.V):
            if not visited[node]:
                if self.is_cyclic_util(node, visited, rec_stack):
                    return True
        return False
 
# 示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print(g.is_cyclic())  # 输出: True

Step 5

Q:: DFS在实际生产环境中有哪些应用场景？

A:: DFS在实际生产环境中有很多应用场景，例如： 1. 图的遍历与搜索：如网络爬虫、社交网络中的朋友推荐。 2. 路径查找：如迷宫求解、游戏中的路径查找。 3. 拓扑排序：如编译器中的语法解析。 4. 检测环路：如死锁检测。 5. 解决组合优化问题：如八皇后问题、数独求解等。

用途

面试中考察DFS是因为它是基本的图算法之一，理解和实现DFS有助于考察候选人的数据结构与算法基础。实际生产环境中，当需要遍历或搜索图或树结构时，DFS非常实用。例如，在网络爬虫中，需要深度遍历网站的链接结构；在游戏开发中，常用于路径查找和迷宫求解等问题。\n

相关问题

🦆

请解释广度优先搜索BFS的基本概念,并描述其工作原理.▷

广度优先搜索（BFS）是一种用于遍历或搜索树或图形数据结构的算法。其特点是按层次逐层搜索，每次优先访问当前层的所有节点，然后再访问下一层。BFS通常使用队列来实现。

🦆

编写一个使用BFS遍历二叉树的代码示例.▷

 
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# 广度优先遍历
def bfs(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
 
# 示例
root = TreeNode(1, TreeNode(2), TreeNode(3))
bfs(root)

🦆

拓扑排序是什么?可以使用DFS实现吗?如何实现?▷

拓扑排序是一种线性排序，适用于有向无环图（DAG），排序结果满足每条有向边(u, v)中顶点u在顶点v之前。可以使用DFS实现拓扑排序，通过对每个未访问的节点进行DFS，完成DFS时将节点添加到结果列表中。最终逆序输出该列表即为拓扑排序。

 
class Graph:
    def __init__(self, vertices):
        self.graph = {i: [] for i in range(vertices)}
        self.V = vertices
 
    def add_edge(self, u, v):
        self.graph[u].append(v)
 
    def topological_sort_util(self, v, visited, stack):
        visited[v] = True
        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                self.topological_sort_util(neighbor, visited, stack)
        stack.append(v)
 
    def topological_sort(self):
        visited = [False] * self.V
        stack = []
        for i in range(self.V):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        return stack[::-1]
 
# 示例
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
print(g.topological_sort())  # 输出: [5, 4, 2, 3, 1, 0]

🦆

什么是回溯算法?请举例说明.▷

回溯算法是一种系统地搜索问题解空间的方法，特别适用于解决组合优化问题。其基本思想是逐步构建解决方案，当发现某一步无法导出有效解时，回溯到上一步重新选择。例如，八皇后问题可以用回溯算法解决，通过逐行放置皇后并检查是否冲突，若冲突则回溯调整。

 
def solve_n_queens(n):
    def is_valid(board, row, col):
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == row - i:
                return False
        return True
 
    def solve(row, board):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                solve(row + 1, board)
                board[row] = -1
 
    result = []
    solve(0, [-1] * n)
    return result
 
# 示例
print(solve_n_queens(4))  # 输出: 2种解法的列表

华为 OD 面试题, DFS

QA

Step 1

Q:: 什么是深度优先搜索（DFS）？

A:: 深度优先搜索（DFS）是一种用于遍历或搜索树或图形数据结构的算法。算法从根节点开始，沿着树的每一分支尽可能深入直到节点没有未被访问的子节点为止，然后回溯到上一个节点并继续搜索其他分支。DFS 的特点是优先遍历尽可能远的路径，适合于探索所有可能的路径（如解决迷宫问题）或用于检查图中是否存在环等。

Step 2

Q:: 如何实现深度优先搜索？

A:: DFS 通常通过递归或使用栈（Stack）来实现。递归实现非常直观，涉及从根节点开始调用自身，直到遇到没有未被访问的子节点。非递归实现则使用显式的栈数据结构来模拟递归调用的过程。以下是一个简单的递归实现：

 
def dfs(node, visited):
    if node not in visited:
        visited.add(node)
        for neighbor in node.neighbors:
            dfs(neighbor, visited)

Step 3

Q:: DFS 和 BFS 的区别是什么？

A:: DFS 和广度优先搜索（BFS）都是用于图遍历的算法。DFS 是深入每一个可能的分支直到末端再回溯，而 BFS 是从根节点开始，先访问当前节点的所有子节点，然后逐层向下遍历。DFS 使用栈（或递归调用），而 BFS 使用队列。DFS 更适合搜索深度较大的树或寻找存在多条路径的解，而 BFS 更适合找到最短路径。

Step 4

Q:: 在什么情况下 DFS 会陷入死循环？如何避免？

A:: DFS 可能在遍历有向或无向图时遇到死循环，特别是图中有环的情况下。为避免这种情况，可以使用一个已访问集合（visited set）来跟踪所有已访问的节点，在每次访问新节点之前先检查该节点是否已经访问过。如果已访问，则跳过该节点。

Step 5

Q:: 如何在 DFS 中检测图中的环？

A:: 在使用 DFS 时，可以通过维护一个栈或递归调用路径中的节点列表来检测环。如果在递归过程中再次访问到已经在当前递归路径中的节点，则表明存在一个环。

Step 6

Q:: DFS 适合用来解决哪些类型的问题？

A:: DFS 适用于解决需要遍历整个解空间的问题，如组合问题（例如排列组合生成）、路径搜索（例如迷宫问题）、连通性问题（例如检测图中的连通分量），以及某些需要回溯的算法（例如数独解题）。

用途

DFS 是一种基础的图遍历算法，广泛应用于解决图和树相关的问题。在实际生产环境中，DFS 被用在需要深入搜索或遍历的问题中，如路径搜索、图连通性检测、解决组合优化问题等。例如，在网络爬虫中，DFS 可用于爬取深度嵌套的页面。在 AI 搜索算法中，DFS 也用于寻找可能的解路径。\n