图的深度优先遍历和广度优先遍历递归算法

图的深度优先遍历和广度优先遍历都可以使用递归算法实现。

深度优先遍历的递归算法可以采用类似于树的前序遍历的方式，从起始节点开始，先访问该节点，然后递归访问该节点的所有邻居节点，直到所有节点都被访问过为止。

广度优先遍历的递归算法则需要借助队列来实现。从起始节点开始，将该节点入队，然后依次出队并访问其所有邻居节点，将这些邻居节点入队，直到队列为空为止。需要注意的是，为了避免重复访问节点，需要在访问节点时将其标记为已访问。

相关问题

实现图的深度优先遍历和广度优先遍历算法。

以下是Python实现的图的深度优先遍历和广度优先遍历算法：

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = {v: [] for v in vertices}
        
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)
        
    def dfs(self, start):
        visited = set()
        self._dfs(start, visited)
        
    def _dfs(self, v, visited):
        visited.add(v)
        print(v, end=' ')
        for neighbor in self.adj_list[v]:
            if neighbor not in visited:
                self._dfs(neighbor, visited)
                
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        while queue:
            v = queue.popleft()
            print(v, end=' ')
            for neighbor in self.adj_list[v]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

上述代码中，Graph类表示一个图，使用邻接表来存储图的信息。add_edge方法用于添加边，dfs方法和_bfs方法分别实现深度优先遍历和广度优先遍历。在dfs方法中，使用递归实现深度优先遍历；在bfs方法中，使用队列实现广度优先遍历。

图深度优先遍历和广度优先遍历

图的深度优先遍历和广度优先遍历是两种常见的图遍历算法。

深度优先遍历（Depth First Search，DFS）是一种先访问深度较深的节点的搜索方法。具体实现可以使用递归或栈来实现。在遍历过程中，每个节点只会被访问一次，因此时间复杂度为 O(V+E)，其中 V 表示节点数，E 表示边数。

广度优先遍历（Breadth First Search，BFS）是一种先访问离起始节点近的节点的搜索方法。具体实现可以使用队列来实现。在遍历过程中，每个节点只会被访问一次，因此时间复杂度为 O(V+E)，其中 V 表示节点数，E 表示边数。