图的深度优先遍历代码

以下是邻接矩阵存储图的深度优先遍历的代码实现：

def DFS(graph, start):
    visited = [False] * len(graph) # 初始化visited数组
    stack = [start] # 初始化栈
    while stack:
        vertex = stack.pop() # 取出栈顶元素
        if not visited[vertex]:
            visited[vertex] = True # 标记为已访问
            print(vertex, end=' ') # 输出遍历结果
            for i in range(len(graph)):
                if graph[vertex][i] == 1 and not visited[i]:
                    stack.append(i) # 将未访问的邻居节点入栈

其中，graph是邻接矩阵，start是遍历的起点。该算法使用了一个栈来存储待访问的节点，每次取出栈顶元素，将其未访问的邻居节点入栈，直到栈为空为止。

相关问题

数据结构深度优先遍历代码

深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，也可以用于树的遍历。下面是一个示例的深度优先遍历代码：

# 定义图的类
class Graph:
    def __init__(self):
        self.graph = {}

    # 添加边
    def add_edge(self, node, neighbor):
        if node in self.graph:
            self.graph[node].append(neighbor)
        else:
            self.graph[node] = [neighbor]

    # 深度优先遍历
    def dfs(self, start):
        visited = set()  # 用集合记录已访问的节点
        self._dfs(start, visited)

    def _dfs(self, node, visited):
        visited.add(node)
        print(node)  # 打印当前节点
        neighbors = self.graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                self._dfs(neighbor, visited)

# 创建图对象
graph = Graph()

# 添加边
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'F')
graph.add_edge('E', 'G')

# 深度优先遍历
graph.dfs('A')

上述代码中，首先定义了一个`Graph`类来表示图，其中`add_edge`方法用于添加边，`dfs`方法用于进行深度优先遍历。在深度优先遍历中，使用一个集合`visited`来记录已访问的节点，遍历过程中递归地访问每个节点的邻居节点。

图的深度优先遍历和广度优先遍历代码

以下是JavaScript实现图的深度优先遍历和广度优先遍历的代码：

深度优先遍历：

function dfs(node) {
  if (!node) return;
  console.log(node.val);
  node.visited = true;
  for (let i = 0; i < node.neighbors.length; i++) {
    const neighbor = node.neighbors[i];
    if (!neighbor.visited) {
      dfs(neighbor);
    }
  }
}

广度优先遍历：

function bfs(node) {
  if (!node) return;
  const queue = [node];
  node.visited = true;
  while (queue.length) {
    const curr = queue.shift();
    console.log(curr.val);
    for (let i = 0; i < curr.neighbors.length; i++) {
      const neighbor = curr.neighbors[i];
      if (!neighbor.visited) {
        neighbor.visited = true;
        queue.push(neighbor);
      }
    }
  }
}