FB3-查找有向图中所有根结点（到图中所有顶点都存在路径的结点）

代码实现

DFS

/**
 * 查找有向图中所有根结点
 * 
 * 定义：在有向图中，如果顶点r到图中所有顶点都存在路径，则称r为图的根结点
 * 
 * 算法思想：
 * 1. 对每个顶点r，检查从r是否能到达所有其他顶点
 * 2. 使用DFS/BFS从顶点r开始遍历
 * 3. 如果遍历完成后所有顶点都被访问过，则r是根结点
 * 
 * 核心思路：
 * - 外层循环遍历每个可能的根结点候选
 * - 内层使用DFS检查该候选结点是否能到达所有顶点
 * - 通过访问标记数组验证连通性
 * 
 * @param G 有向图的邻接表表示
 */
void findRootNodes(Graph G) {
    // 遍历每个顶点作为根结点候选
    for (int i = 0; i < G.numver; i++) {
        // 为每个候选结点创建新的访问标记数组
        int visit[maxsize] = {0};

        // 标记标志位：0表示是根结点，1表示不是根结点
        int flag = 0;

        // 从顶点i开始进行DFS遍历
        DFS(G, i, visit);

        // 检查是否所有顶点都被访问过
        for (int j = 0; j < G.numver; j++) {
            // 如果存在未被访问的顶点，则i不是根结点
            if (visit[j] == 0) {
                flag = 1;
                break;  // 可以提前退出，优化性能
            }
        }

        // 如果flag仍为0，说明从顶点i可以到达所有顶点，i是根结点
        if (flag == 0) {
            printf("%d ", i);
        }
    }
}

/**
 * 图的深度优先搜索遍历（辅助函数）
 * 
 * @param G 图的邻接表表示
 * @param v 起始顶点
 * @param visit 访问标记数组
 */
void DFS(Graph G, int v, int visit[]) {
    // 标记当前顶点为已访问
    visit[v] = 1;

    // 遍历当前顶点的所有邻接顶点
    Node p = G.adjlist[v].firstarc;
    for (; p != NULL; p = p->nextarc) {
        // 如果邻接顶点未被访问，则递归访问
        if (visit[p->adjvex] == 0) {
            DFS(G, p->adjvex, visit);
        }
    }
}

BFS

/**
 * 优化版本：使用BFS实现根结点查找
 * 
 * 优点：BFS在某些情况下可能有更好的缓存局部性
 */
void findRootNodes_BFS(Graph G) {
    // 遍历每个顶点作为根结点候选
    for (int i = 0; i < G.numver; i++) {
        // 为每个候选结点创建新的访问标记数组
        int visit[maxsize] = {0};

        // 使用BFS检查连通性
        BFS(G, i, visit);

        // 检查是否所有顶点都被访问过
        int isRoot = 1;  // 假设是根结点
        for (int j = 0; j < G.numver; j++) {
            if (visit[j] == 0) {
                isRoot = 0;  // 发现未访问顶点，不是根结点
                break;
            }
        }

        // 如果是根结点，则输出
        if (isRoot) {
            printf("%d ", i);
        }
    }
}

/**
 * BFS辅助函数
 */
void BFS(Graph G, int v, int visit[]) {
    int que[maxsize];
    int front = 0, rear = 0;

    // 起始顶点入队并标记
    que[rear++] = v;
    visit[v] = 1;

    // BFS遍历
    while (front != rear) {
        v = que[front++];

        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                que[rear++] = p->adjvex;
            }
        }
    }
}

DFS优化-计数

/**
 * 进一步优化版本：提前终止优化
 * 
 * 如果在遍历过程中发现不可能成为根结点，提前终止
 */
void findRootNodes_Optimized(Graph G) {
    // 遍历每个顶点作为根结点候选
    for (int i = 0; i < G.numver; i++) {
        int visit[maxsize] = {0};
        int visitedCount = 0;  // 记录已访问的顶点数

        // 使用DFS遍历并统计访问的顶点数
        DFS_Count(G, i, visit, &visitedCount);

        // 如果访问的顶点数等于总顶点数，则i是根结点
        if (visitedCount == G.numver) {
            printf("%d ", i);
        }
    }
}

/**
 * 带计数功能的DFS
 */
void DFS_Count(Graph G, int v, int visit[], int* count) {
    visit[v] = 1;
    (*count)++;  // 增加访问计数

    Node p = G.adjlist[v].firstarc;
    for (; p != NULL; p = p->nextarc) {
        if (visit[p->adjvex] == 0) {
            DFS_Count(G, p->adjvex, visit, count);
        }
    }
}

强连通分量

/**
 * 另一种思路：基于强连通分量的优化
 * 
 * 如果图不是强连通的，可以先找出强连通分量来优化计算
 */
void findRootNodes_SCC_Optimized(Graph G) {
    // 首先检查图是否强连通
    if (isStronglyConnected(G)) {
        // 如果强连通，则所有顶点都是根结点
        for (int i = 0; i < G.numver; i++) {
            printf("%d ", i);
        }
    } else {
        // 否则使用常规方法
        findRootNodes(G);
    }
}

/**
 * 检查图是否强连通的辅助函数
 */
int isStronglyConnected(Graph G) {
    // 从任意顶点开始检查是否能到达所有顶点
    int visit[maxsize] = {0};
    DFS(G, 0, visit);

    // 检查是否所有顶点都被访问
    for (int i = 0; i < G.numver; i++) {
        if (visit[i] == 0) {
            return 0;  // 不是强连通
        }
    }

    // 还需要检查反向图的连通性（此处简化处理）
    return 1;  // 强连通
}

复杂度分析

时间复杂度：O(V × (V + E))

• V: 顶点数，E: 边数
• 外层循环执行V次（检查每个顶点是否为根结点）
• 每次DFS/BFS需要O(V + E)时间
• 总时间复杂度：O(V × (V + E))

空间复杂度：O(V)

• visit[]数组：O(V)
• DFS递归调用栈：最坏情况O(V)
• 总空间复杂度：O(V)

图解说明

示例有向图结构：
顶点：0, 1, 2, 3, 4
边：0→1, 0→2, 1→3, 2→3, 3→4

图示：
0 ──→ 1 ──→ 3 ──→ 4
│              ↗
└────→ 2 ──────┘

检查每个顶点是否为根结点：

检查顶点0：
DFS(0): 访问顺序 0→1→3→4, 2→3→4
最终visit: [1,1,1,1,1] - 所有顶点都被访问
→ 顶点0是根结点 ✓

检查顶点1：
DFS(1): 访问顺序 1→3→4
最终visit: [0,1,0,1,1] - 顶点0,2未被访问
→ 顶点1不是根结点 ✗

检查顶点2：
DFS(2): 访问顺序 2→3→4
最终visit: [0,0,1,1,1] - 顶点0,1未被访问
→ 顶点2不是根结点 ✗

检查顶点3：
DFS(3): 访问顺序 3→4
最终visit: [0,0,0,1,1] - 顶点0,1,2未被访问
→ 顶点3不是根结点 ✗

检查顶点4：
DFS(4): 访问顺序 4
最终visit: [0,0,0,0,1] - 顶点0,1,2,3未被访问
→ 顶点4不是根结点 ✗

结果：只有顶点0是根结点

相关知识点延伸

1. 根结点的性质

// 根结点的重要性质
/*
1. 在强连通有向图中，所有顶点都是根结点
2. 在有向无环图(DAG)中，根结点就是入度为0的顶点
3. 根结点一定是图中某个生成树的根
4. 如果图不连通，则不存在根结点
*/

2. 应用场景

// 任务调度系统中的关键任务识别
void findCriticalTasks(TaskGraph G) {
    findRootNodes(G);  // 关键任务：能影响所有其他任务的任务
}

// 网络中的关键服务器识别
void findCriticalServers(NetworkGraph G) {
    findRootNodes(G);  // 关键服务器：能访问所有其他服务器的服务器
}

// 依赖管理系统中的根依赖
void findRootDependencies(DependencyGraph G) {
    findRootNodes(G);  // 根依赖：所有其他依赖都间接依赖的依赖项
}

3. 进一步优化思路

// 基于支配树的优化算法
void findRootNodes_DominatorTree(Graph G) {
    /*
    1. 构建支配树
    2. 根结点就是支配树的根节点
    3. 时间复杂度可以优化到O((V+E)logV)
    */
}

// 并行化处理
void findRootNodes_Parallel(Graph G) {
    /*
    1. 将顶点分组并行处理
    2. 使用多线程同时检查多个候选根结点
    3. 适用于大规模图处理
    */
}

4. 特殊图类型的处理

// DAG中的优化处理
void findRootNodes_DAG(Graph G) {
    // 在DAG中，根结点就是入度为0的顶点
    for (int i = 0; i < G.numver; i++) {
        if (getInDegree(G, i) == 0) {
            // 检查从该顶点是否能到达所有顶点
            if (canReachAll(G, i)) {
                printf("%d ", i);
            }
        }
    }
}

// 树结构中的处理
void findRootNodes_Tree(Graph G) {
    // 在树中，根结点就是能到达所有其他节点的节点
    // 可以通过计算节点的出度来优化
}

5. 错误处理和边界情况

// 完整的错误处理版本
void findRootNodes_Robust(Graph G) {
    // 输入验证
    if (G.numver <= 0) {
        printf("空图无根结点\n");
        return;
    }

    // 单顶点图
    if (G.numver == 1) {
        printf("0 ");
        return;
    }

    // 正常处理
    for (int i = 0; i < G.numver; i++) {
        int visit[maxsize] = {0};
        int flag = 0;

        DFS(G, i, visit);

        for (int j = 0; j < G.numver; j++) {
            if (visit[j] == 0) {
                flag = 1;
                break;
            }
        }

        if (flag == 0) {
            printf("%d ", i);
        }
    }
}

这个算法是图论中判断图的连通性的重要应用，对于理解图的结构特性和设计网络系统都有重要意义。