c语言dfs算法详解

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树形数据结构的算法，它通过尽可能深地探索分支来寻找目标节点。在C语言中，DFS通常用于解决图的遍历问题，如寻找是否存在连通路径、找出所有路径等。

以下是DFS的基本步骤：

1. **选择一个起始节点**：从给定图的某个顶点开始。
2. **标记当前节点**：将起始节点标记为已访问。
3. **递归处理相邻节点**：对于当前节点的所有未访问邻居，对每个邻居进行DFS操作。
4. **回溯**：在遍历完一个邻接节点后，返回到上一个节点继续查找其他路径，直到找到目标或者所有路径都尝试过。

**C语言伪代码示例**：

void dfs(int node, bool visited[], graph adj[]) {
    // Mark the current node as visited
    visited[node] = true;

    // Visit all its neighbors recursively
    for (int i = 0; i < adj[node].size(); i++) {
        int neighbor = adj[node][i];
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }
}

// 主函数调用
void dfsGraph(graph adj[], int V) {
    // 初始化标志数组
    bool* visited = new bool[V];

    // 对于图中的每个节点调用dfs
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, visited, adj);
        }
    }

    delete[] visited;
}

在这个例子中，`graph`是一个邻接表表示图的数据结构，`adj[]`存储了每条边连接的节点，`visited[]`数组记录了哪些节点已经访问过。