图的深度优先遍历代码

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

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是遍历的起点。该算法使用了一个栈来存储待访问的节点，每次取出栈顶元素，将其未访问的邻居节点入栈，直到栈为空为止。

相关问题

图的广度优先遍历与深度优先遍历代码实现

### 回答1：
以下是图的广度优先遍历和深度优先遍历的Python实现代码：

# 图的广度优先遍历
def bfs(graph, start):
    visited = set()  # 已访问过的节点集合
    queue = [start]  # 初始化队列
    while queue:
        node = queue.pop(0)  # 取出队首节点
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 图的深度优先遍历
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()  # 已访问过的节点集合
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 广度优先遍历
print('BFS:', end=' ')
bfs(graph, 'A')
print()

# 深度优先遍历
print('DFS:', end=' ')
dfs(graph, 'A')
print()

输出结果：

BFS: A B C D E F 
DFS: A B D E F C 

其中，`graph`是一个字典类型的图表示，键为节点，值为与该节点相邻的节点列表。`start`为遍历的起点节点。

### 回答2：
图的广度优先遍历（BFS）和深度优先遍历（DFS）是两种常用的图遍历算法，下面是它们的代码实现：

广度优先遍历代码实现（BFS）：

def BFS(graph, start):
    visited = set()  # 记录已访问过的节点
    queue = []  # 使用队列来辅助实现BFS
    
    visited.add(start)  
    queue.append(start)
    
    while queue:
        node = queue.pop(0)  # 弹出队首节点
        print(node, end=" ")  # 访问节点
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

深度优先遍历代码实现（DFS）：

def DFS(graph, start, visited):
    visited.add(start)
    print(start, end=" ")  # 访问节点
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

在以上两种代码中，`graph`是图的表示方式，通常使用邻接表或邻接矩阵来表示；`start`是起始节点；`visited`是记录已访问节点的集合。

广度优先遍历使用队列来辅助遍历，从起始节点开始，将其加入队列并标记为已访问，然后从队列中弹出一个节点，访问它，并将其未访问过的邻居加入队列；一直重复这个过程，直到队列为空。

深度优先遍历使用递归方式实现，从起始节点开始，首先将其标记为已访问，然后递归地访问它的邻居节点，直到没有未访问的邻居节点为止，然后回溯到上一级节点，继续递归访问其未访问的邻居节点。这样一直递归下去，直到遍历完整个图。

BFS和DFS都可以遍历图的所有节点，并且每个节点仅被访问一次。

### 回答3：
图的广度优先遍历（BFS）和深度优先遍历（DFS）是常用的图遍历算法。以下是它们的代码实现：

广度优先遍历（BFS）：
1. 建立一个队列，并将起始节点加入队列；
2. 创建一个visited列表，用于记录已经遍历过的节点；
3. 循环队列，直到队列为空：
- 从队列中弹出一个节点，并将其标记为visited；
- 遍历该节点的所有相邻节点：
- 如果相邻节点未被visited，则将其加入队列；
4. 返回visited列表，即为广度优先遍历的结果。

下面是使用Python实现的广度优先遍历的代码：

def bfs(graph, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            neighbors = graph[node]
            for neighbor in neighbors:
                queue.append(neighbor)
    
    return visited

深度优先遍历（DFS）：
1. 创建一个visited列表，用于记录已经遍历过的节点；
2. 定义一个递归函数，用于进行深度优先遍历：
- 将当前节点标记为visited；
- 遍历当前节点的所有相邻节点：
- 如果相邻节点未被visited，则递归调用该函数；
3. 在主函数中调用递归函数，并返回visited列表，即为深度优先遍历的结果。

下面是使用Python实现的深度优先遍历的代码：

def dfs(graph, start, visited):
    visited.append(start)
    neighbors = graph[start]
    for neighbor in neighbors:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def dfsTraversal(graph, start):
    visited = []
    dfs(graph, start, visited)
    return visited

需要注意的是，上述代码中的graph是以字典形式表示的图，其中键表示节点，值表示与该节点相邻的节点列表。此外，代码还需要预先定义起始节点start。

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

以下是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);
      }
    }
  }
}