邻接矩阵存储图的深度优先遍历pintia

邻接矩阵是一种常见的图数据结构，用于表示一个无向图或有向图，其中每个节点都有一个二维数组（通常是布尔值）来记录其与其他所有节点的连接关系。对于无向图，矩阵是对称的；对于有向图，从i到j的边可能与从j到i的边不同。

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或查找树或图的算法。它的基本思想是从起点开始，尽可能深地探索分支，直到到达叶子节点，然后回溯到上一层继续搜索其他未访问过的节点。

在使用邻接矩阵存储的图中进行DFS，通常的做法如下：

1. 初始化：选择一个起始节点，将其标记为已访问（比如设置为1），并将它放入一个堆栈（或递归调用栈）。

2. 探索：如果堆栈不为空，弹出顶点v。对于v的所有邻居u，检查它们是否未被访问过：
- 如果u未访问，则标记它为已访问，将其添加到堆栈中（对于有向图，还要加上方向信息，如指向u的方向）。
- 继续对u的所有未访问邻居重复此步骤。

3. 结束条件：当堆栈为空时，说明已经处理完所有的可达节点，搜索结束。

以下是一个简单的C语言伪代码示例：

bool visited[graph_size] = {0}; // 假设 graph_size 是邻接矩阵大小
void dfs(int node) {
    visited[node] = true;
    for (int i = 0; i < graph_size; i++) {
        if (!visited[i] && matrix[node][i]) { // matrix[node][i] 表示是否有边从node到i
            dfs(i);
        }
    }
}

在实际应用中，`matrix[node][i]`会被替换为你邻接矩阵的具体引用，`graph_size`则根据实际情况调整。