c语言有向图的深度优先搜索递归方法和非递归方法

深度优先搜索（DFS）是一种遍历图的算法，它从指定的起始顶点开始遍历，尽可能深地遍历图的分支，直到到达叶子节点或者无法继续为止。C语言中实现DFS算法有递归方法和非递归方法。

1. 递归方法：

递归方法使用函数的递归调用实现深度优先搜索。具体实现步骤如下：

1. 定义一个visited数组，用于标记每个顶点是否被访问过。
2. 从指定的起始顶点开始，对每个未被访问过的相邻顶点进行深度优先遍历，遍历过程中将访问过的顶点标记为已访问。
3. 递归调用DFS函数，直到所有的顶点都被遍历完成。

以下是C语言中实现DFS递归算法的示例代码：

#define MAX_VERTEX_NUM 100
int visited[MAX_VERTEX_NUM]; // 标记每个顶点是否被访问过

void DFS(int v, int **G, int n) {
    visited[v] = 1; // 标记顶点v已被访问过
    for(int i=0; i<n; i++) {
        if(G[v][i] && !visited[i]) { // 如果顶点i与v相邻且未被访问过
            DFS(i, G, n); // 递归遍历顶点i
        }
    }
}

2. 非递归方法：

非递归方法使用栈来实现深度优先搜索。具体实现步骤如下：

1. 定义一个visited数组，用于标记每个顶点是否被访问过。
2. 定义一个栈S，将起始顶点压入栈中。
3. 当栈不为空时，取出栈顶元素v，若v未被访问过，则遍历v的所有未被访问过的相邻顶点，并将这些顶点压入栈中。
4. 遍历完v的所有相邻顶点后，将v标记为已访问。

以下是C语言中实现DFS非递归算法的示例代码：

#define MAX_VERTEX_NUM 100
int visited[MAX_VERTEX_NUM]; // 标记每个顶点是否被访问过

void DFS(int v, int **G, int n) {
    int stack[MAX_VERTEX_NUM]; // 定义栈S
    int top = -1; // 栈顶指针
    stack[++top] = v; // 将起始顶点v入栈
    visited[v] = 1; // 标记顶点v已被访问过
    while(top >= 0) {
        int cur = stack[top--]; // 取出栈顶元素
        for(int i=0; i<n; i++) {
            if(G[cur][i] && !visited[i]) { // 如果顶点i与cur相邻且未被访问过
                stack[++top] = i; // 将顶点i入栈
                visited[i] = 1; // 标记顶点i已被访问过
            }
        }
    }
}