邻接表递归遍历实现dfs

邻接表递归遍历实现DFS的过程如下：

1. 首先，我们需要定义一个访问标志数组visited，用于标记顶点是否已经被访问过。初始化visited数组为0，表示所有顶点都未被访问。

2. 接下来，我们定义一个DFS函数，该函数接受两个参数：图g和要遍历的起始顶点i。

3. 在DFS函数中，首先访问并输出顶点i的数据，然后将visited[i]标记为1，表示该顶点已经被访问。

4. 接着，我们通过访问顶点i的邻接链表，遍历所有与顶点i相邻的顶点。

5. 对于每个未被访问过的邻接顶点j，我们递归调用DFS函数，将j作为起始顶点，以便继续深度遍历。

6. 最后，我们通过遍历图中的所有顶点，保证非连通图的遍历，对于每个未被访问过的顶点v，我们调用DFS函数进行深度优先遍历。

下面是具体的代码实现：

void DFS(graph g, int i) {
    ArcNode *p;
    printf("<%d>", g.adjlist[i].data); // 访问第i个顶点
    
    visited[i = 1; // 标记顶点i已经被访问
    
    p = g.adjlist[i].firstedge; // 获取顶点i的第一个邻接点
    
    while (p != NULL) {
        if (visited[p->adjvex == 0)
            DFS(g, p->adjvex); // 对未访问的邻接顶点进行递归调用DFS
        p = p->next;
    }
}

void DFSTraverse(graph g) {
    int v;
    
    for (v = 0; v < g.vex; v++)
        visited[v = 0; // 初始化标志数组
    
    for (v = 0; v < g.vex; v++) {
        if (!visited[v])
            DFS(g, v); // 从第v个顶点出发递归地深度优先遍历图g
    }
}

以上就是使用邻接表实现DFS深度优先搜索的过程。首先定义了DFS函数，在该函数中访问并输出顶点数据，并通过递归调用DFS函数，对未访问的邻接顶点进行深度优先遍历。然后定义了DFSTraverse函数，用于遍历图中的所有顶点，保证非连通图的遍历。