邻接矩阵的深度优先遍历

邻接矩阵的深度优先遍历可以通过使用栈来实现。具体步骤如下：

1. 首先将起始节点压入栈中，并将其标记为已访问。
2. 当栈不为空时，弹出栈顶元素，并遍历其所有未访问的邻居节点。
3. 对于每个未访问的邻居节点，将其压入栈中，并将其标记为已访问。
4. 重复步骤2、3，直到栈为空。

下面是邻接矩阵的深度优先遍历的代码实现：

def dfs(adj_matrix, start):
    stack = [start]  # 用列表模拟栈
    visited = []     # 用列表记录已访问的节点
    while stack:
        node = stack.pop()  # 弹出栈顶元素
        visited.append(node)  # 将节点标记为已访问
        for i in range(len(adj_matrix[node])):
            if adj_matrix[node][i] == 1 and i not in visited:  # 遍历邻居节点
                stack.append(i)  # 将邻居节点压入栈中
    return visited

其中，`adj_matrix` 是邻接矩阵，`start` 是起始节点的索引。函数返回遍历的节点列表。

相关问题

邻接矩阵深度优先遍历

邻接矩阵深度优先遍历的基本思想是从某个顶点开始，沿着一条未被访问过的边走到未访问过的顶点，直到该顶点没有未访问过的邻接点为止，然后回溯到前一个顶点，继续寻找其未访问过的邻接点，直到所有顶点都被访问过为止。

具体实现时，我们可以使用一个栈来存储当前正在访问的顶点，每次从栈顶取出一个顶点进行处理，将其未访问过的邻接点入栈，直到栈为空为止。

以下是邻接矩阵深度优先遍历的伪代码：

DFS(v)
    visited[v] = true // 标记当前顶点已被访问
    for i = 1 to n do
        if graph[v][i] = 1 and visited[i] = false then // 如果当前顶点与顶点i之间有边且i未被访问
            DFS(i) // 递归访问顶点i

其中，`graph`为邻接矩阵，`visited`为记录顶点是否被访问过的数组，`n`为顶点个数，`v`为当前正在访问的顶点。

邻接矩阵深度优先遍历和广度优先遍历

邻接矩阵是一种图的存储结构，它可以用来表示有限个顶点之间的关系。邻接矩阵的深度优先遍历和广度优先遍历是图的两种基本遍历方式。

邻接矩阵的深度优先遍历（Depth First Search，DFS）：
深度优先遍历是一种用于遍历或搜索树或图的算法。在这个算法中，首先访问根节点，然后递归地访问每个子节点。当访问一个节点时，将其标记为已访问，以避免重复访问。深度优先遍历使用栈来实现，因此它是一种先进后出（Last In First Out，LIFO）的算法。

下面是邻接矩阵的深度优先遍历的Python代码示例：

def DFS(graph, start):
    visited = set()  # 用集合来存储已经访问过的节点
    stack = [start]  # 用列表来模拟栈
    while stack:
        vertex = stack.pop()  # 取出栈顶元素
        if vertex not in visited:
            visited.add(vertex)  # 标记为已访问
            print(vertex, end=' ')
            # 将未访问的邻居节点入栈
            stack.extend([i for i in range(len(graph[vertex])) if graph[vertex][i] and i not in visited])

# 示例
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]
DFS(graph, 0)  # 输出：0 1 3 2

邻接矩阵的广度优先遍历（Breadth First Search，BFS）：
广度优先遍历是一种用于遍历或搜索树或图的算法。在这个算法中，首先访问根节点，然后逐层访问每个子节点。当访问一个节点时，将其标记为已访问，以避免重复访问。广度优先遍历使用队列来实现，因此它是一种先进先出（First In First Out，FIFO）的算法。

下面是邻接矩阵的广度优先遍历的Python代码示例：

from collections import deque

def BFS(graph, start):
    visited = set()  # 用集合来存储已经访问过的节点
    queue = deque([start])  # 用双端队列来模拟队列
    while queue:
        vertex = queue.popleft()  # 取出队首元素
        if vertex not in visited:
            visited.add(vertex)  # 标记为已访问
            print(vertex, end=' ')
            # 将未访问的邻居节点入队
            queue.extend([i for i in range(len(graph[vertex])) if graph[vertex][i] and i not in visited])

# 示例
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]
BFS(graph, 0)  # 输出：0 1 2 3