DFS深度优先遍历算法详解（Java实现）

在数据结构中，图的深度优先遍历是树的先根遍历的推广。

图的深度优先遍历的思想是：从图中某个顶点 v0 出发，访问顶点 v0 的第一个邻接点，然后以该邻接点为新的顶点，访问该顶点的邻接点。重复执行以上操作，直到当前顶点没有邻接点为止。返回上一个已经访问过并且还有未被访问的邻接点的顶点，按照以上步骤继续访问该顶点的其他未被访问的邻接点。以此类推，直到图中所有的顶点都被访问过。

图的深度优先遍历如下图所示：

图 1 无向图 G6 及其深度优先遍历过程

访问顶点的方向用实箭头表示，回溯用虚箭头表示，图中的数字表示访问或回溯的次序。

无向图 G6 的深度优先遍历过程如下：

首先访问 A，顶点 A 的邻接点有 B、C、D，然后访问 A 的第一个邻接点 B。
顶点 B 未访问的邻接点只有顶点 E，因此访问顶点 E。
顶点 E 的邻接点只有 F 且未被访问过，因此访问顶点 F。
顶点 F 的邻接点只有 C 且未被访问过，因此访问顶点 C。
顶点 C 的邻接点只有 A 但已经被访问过，因此要回溯到上一个顶点 F。
同理，顶点 F、E、B 都已经被访问过，且没有其他未访问的邻接点，因此回溯到顶点 A。
顶点 A 未被访问的邻接顶点只有顶点 D，因此访问顶点 D。
顶点 D 的邻接点有顶点 G 和顶点 H，访问第一个顶点 G。
顶点 G 的邻接点有顶点 H 和顶点 I，访问第一个顶点 H。
顶点 H 的邻接点只有 D 且已经被访问过，因此回溯到上一个顶点 G。
顶点 G 的未被访问过的邻接点有顶点 I，因此访问顶点 I。
顶点I已经没有未被访问的邻接点，因此回溯到顶点 G。
同理，顶点 G、D 都没有未被访问的邻接点，因此回溯到顶点 A。
顶点 A 也没有未被访问的邻接点。

因此，图的深度优先遍历的序列为：A、B、E、F、C、D、G、H、I。

在图的深度优先遍历过程中，图中可能存在回路，因此，在访问某个顶点之后，沿着某条路径遍历，有可能又回到该顶点。例如，在访问顶点 A 之后，接着访问顶点 B、E、F、C，顶点 C 的邻接点是顶点 A，沿着边 (C,A) 会再次访问顶点 A。为了避免再次访问已经访问过的顶点，需要设置一个数组 visited[n]，作为一个标志记录结点是否被访问过。

深度优先遍历算法的实现

图的深度优先遍历（邻接表实现）的算法描述如下：

public void DFSTraverse(int visited[])
// 从第 1 个顶点起，深度优先遍历图
{
    for (int v = 0; v < vexnum; v++)
        visited[v] = 0; // 访问标志数组初始化为未被访问过
    for (int v = 0; v < vexnum; v++) {
        if (visited[v] == 0) // 对未访问的顶点 v 进行深度优先遍历
            DFS(v, visited);
    }
    System.out.println();
}

public void DFS(int v, int visited[])
// 从顶点 v 出发递归深度优先遍历图
{
    visited[v] = 1; // 访问标志设置为已访问
    System.out.print(vertex[v].data + " "); // 访问第 v 个顶点
    int w = FirstAdjVertex(vertex[v].data);
    while (w >= 0) {
        if (visited[w] == 0)
            DFS(w, visited); // 递归调用 DFS 对 v 的尚未访问的邻接顶点
        w = NextAdjVertex(vertex[v].data, vertex[w].data);
    }
}

如果该图是一个无向连通图或者该图是一个强连通图，则只需要调用一次 DFS(G,v) 就可以遍历整个图，否则需要多次调用 DFS(G,v)。

在上面的算法中，对于查找序号为 v 的顶点的第一个邻接点的算法 FirstAdjVex(G,G.vexs[v]) 以及查找序号为 v 的相对于序号 w 的下一个邻接点的算法 NextAdjVex(G,G.vexs[v],G.vexs[w]) 的实现，采用不同的存储表示，其耗费的时间也是不一样的。当采用邻接矩阵作为图的存储结构时，若图的顶点个数为 n，则查找顶点的邻接点需要的时间为 O(n^2)。若无向图中的边数或有向图的弧的数目为 e，当采用邻接表作为图的存储结构时，则查找顶点的邻接点需要的时间为 O(e)。

以邻接表作为存储结构，查找 v 的第一个邻接点的算法实现如下：

public int FirstAdjVertex(String v)
// 返回顶点 v 的第一个邻接顶点的序号
{
    int v1 = LocateVertex(v); // v1 为顶点 v 在图 G 中的序号
    ArcNode p = vertex[v1].firstarc;
    if (p != null) // 若顶点 v 的第一个邻接点存在，则返回邻接点的序号，否则返回-1
        return p.adjvex;
    else
        return -1;
}

以邻接表作为存储结构，查找 v 相对于 w 的下一个邻接点的算法实现如下：

public int NextAdjVertex(String v, String w)
// 返回 v 相对于 w 的下一个邻接顶点的序号
{
    int v1 = LocateVertex(v);    // v1 为顶点 v 在图 G 中的序号
    int w1 = LocateVertex(w);    // w1 为顶点 w 在图 G 中的序号
    ArcNode next = vertex[v1].firstarc;
    while (next != null) {
        if (next.adjvex != w1)
            next = next.nextarc;
        else
            break;
    }
    ArcNode p = next; // p 指向顶点 v 的邻接顶点 w 的结点
    if (p == null || p.nextarc == null) // 若 w 不存在或 w 是最后一个邻接点，则返回-1
        return -1;
    else
        return p.nextarc.adjvex; // 返回 v 相对于 w 的下一个邻接点的序号
}

图的非递归深度优先遍历的算法实现如下：

public void DFSTraverse2(int v, int visited[])
// 图的非递归深度优先遍历
{
    ArcNode stack[] = new ArcNode[vexnum];
    for (int i = 0; i < vexnum; i++) // 为所有顶点添加未访问标志
        visited[i] = 0;
    System.out.print(vertex[v].data + " "); // 访问顶点 v 并将访问标志置为 1，表示已被访问过
    visited[v] = 1;
    int top = -1; // 初始化栈
    ArcNode p = vertex[v].firstarc; // p 指向顶点 v 的第一个邻接点
    while (top > -1 || p != null) {
        while (p != null) {
            if (visited[p.adjvex] == 1) // 若 p 指向的顶点已经访问过，则 p 指向下一个邻接点
                p = p.nextarc;
            else {
                System.out.print(vertex[p.adjvex].data + " "); // 访问 p 指向的顶点
                visited[p.adjvex] = 1;
                top++;
                stack[top] = p; // 保存 p 指向的顶点
                p = vertex[p.adjvex].firstarc; // p 指向当前顶点的第一个邻接点
            }
        }
        if (top > -1) {
            p = stack[top--]; // 若当前顶点都已经被访问过，则退栈
            p = p.nextarc; // p 指向下一个邻接点
        }
    }
}

DFS深度优先遍历算法详解（Java实现）

深度优先遍历算法的实现

相关文章