邻接矩阵的深度广度遍历

邻接矩阵是图的一种表示方法，其中用一个二维数组来存储图中顶点之间的连接关系。深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法，它们可以帮助我们探索图的结构。

**深度优先遍历（DFS）**：
- 它从起点开始，尽可能深地探索分支，直到到达一个无法访问的节点为止，然后返回并探索其他分支。
- DFS通常使用递归或栈来实现。从起点开始，将当前节点标记为已访问，然后对每个相邻未访问的节点递归执行DFS。
- 优点：内存占用相对较小，可以找到最短路径到某个节点（如果图是有向无环图，且所有边权值为1）。
-

相关问题

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

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

邻接矩阵的深度优先遍历（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

图的邻接矩阵深度优先遍历和广度优先遍历c++

在C++中，使用邻接矩阵（Adjacency Matrix）进行深度优先搜索（DFS）和广度优先搜索（BFS）的步骤大致如下：

**深度优先搜索（DFS）**：

void dfs(int start, bool visited[]) {
    visited[start] = true;
    cout << start << " ";

    for (int i = 0; i < vertices; ++i) {
        if (graph[start][i] && !visited[i]) { // 检查边的存在并访问未访问节点
            dfs(i, visited);
        }
    }
}

// 示例用法
bool* initVisited(int n) { return new bool[n]; } // 初始化一个布尔数组记录已访问状态
dfs(0, initVisited(vertices)); // 从顶点0开始
delete[] initVisited(vertices); // 清理内存

**广度优先搜索（BFS）**：

void bfs(int start) {
    queue<int> q; // 使用队列存储节点
    vector<bool> visited(vertices, false); // 初始化访问标记

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front(); // 取出队首节点
        q.pop();
        cout << u << " ";

        for (int v = 0; v < vertices; ++v) {
            if (graph[u][v] && !visited[v]) { // 添加相邻且未访问的节点
                q.push(v);
                visited[v] = true;
            }
        }
    }
}

bfs(0); // 从顶点0开始

在上述代码中，`vertices`代表顶点数量，`graph`是邻接矩阵。`dfs`和`bfs`函数分别实现了这两种遍历方法，`initVisited`用于初始化一个布尔数组表示节点是否已被访问。