37.2° Blog

1.描述

设计算法，判断一个以邻接表为存储结构的有向图是否存在环。

2.分析

使用DFS的拓扑排序进行判断环是否存在。

算法设计步骤：

• 1. 通过极端特里法进行手算研究
• 2. 发现特例的规律
• 3. 算法思想
• 4. 代码

通过DFS+清除访问标记visited的方法能求出所有从src到dst的所有路径(src到每个顶点的所有路径)。增加了新的限定，规定路径的长度为d(过滤出来)。

3.算法思想

• 顶点v在递归函数执行状态中(递归函数没执行完)，通过某个顶点w的DFS又被重复访问，则有向图存在从顶点v出发再回到顶点v的环路。
• 将访问标记区分：未访问的、正在访问的、已访问过的；
• 使用枚举{白色，红色，黑色}分别表示{未访问的、正在访问的、已访问过的}；
• 如果在搜索过程中，遇到标记为红色的顶点，则说明图中存在环；

4.手算示例

从4号顶点（src）到6号顶点（dst），长度为d的路径

5.代码

全局变量

// 访问标记数组，防止顶点重复出现在路径中
typedef enum
{
    WHITE = 0,  // 未访问的结点
    RED   = 1,  // 正在访问的结点
    BLACK = 2,  // 已访问的结点
}COLOR;
COLOR colorVisited[MAX_VERTEX] = { WHITE };

核心代码

注意限制条件，第16行和22行

/**
 * 使用DFS获得从某一顶点开始遍历，是否存在环
 *
 * @param alG       - 邻接表存储的图
 * @param vertex    - 起始顶点
 *
 * @return @c bool
 */
bool getRing(ALGraph alG, VertexType vertex)
{
    if (colorVisited[vertex] == RED)
        return true;
    colorVisited[vertex] = RED;    // vertex顶点正在被访问
    path[pathLength++] = vertex;
    ArcNode* pNextArcNode = alG.vertices[vertex].first;
    int neighborVertex = 0;
    bool ret = false;
    while (pNextArcNode != NULL)
    {
        neighborVertex = pNextArcNode->adjvex;
        // 从顶点 vertex 开始DFS搜索环
        if(colorVisited[vertex] != BLACK)
            ret = getRing(alG, neighborVertex);
        if (ret == true)
            return true;
        pNextArcNode = pNextArcNode->next;
    }
    colorVisited[vertex] = BLACK;
    pathLength--;
    return false;
}
/**
 * 使用DFS判断图中是否存在环
 *
 * @param alG       - 邻接表存储的图
 *
 * @return @c bool
 */
bool isExistRing(ALGraph alG)
{
    bool ret = false;
    // 从0开始深度优先遍历
    for (int v = 1; v <= alG.vexnum; v++)
    {
        if (colorVisited[v] == WHITE)
            ret = getRing(alG, v);
    }
    return ret;
}

6.运行

注意：图的类型为有向不带权图

数据准备

顶点数据：vSet.txt

1
2
3
4
5
6
7

弧数据：arcSet.txt

2 1
3 1
3 2
4 5
5 7
6 5
7 6

读取顶点信息

读取弧信息

创建图

调用DFS判环

printf("isExitRing: %d\n", isExistRing(alG));

运行结果