寻求最小化单根DAG同类型子图划分的高效C++算法

问题定义 #

给定一个含约1000个节点的有根有向无环图（DAG），每个节点带有“颜色”属性，需要将图划分为尽可能少的子图，满足：

1. 每个子图内所有节点颜色完全相同
2. 子图构成的收缩图（子图间保留原节点的依赖边）仍是无环图

核心思路 #

采用拓扑序贪心策略：利用DAG的拓扑排序特性，按从根到叶子的顺序处理节点，优先尝试将当前节点加入同颜色的最新子图，若加入后会导致收缩图出现环则创建新子图。该策略能在保证效率的前提下，尽可能减少子图数量。

算法步骤 #

1. 拓扑排序：对原DAG执行Kahn算法生成拓扑序列，确保处理节点时所有前驱节点已完成分配。
2. 子图分配：
   • 遍历拓扑序列中的每个节点，优先尝试加入同颜色的最后一个子图
   • 检查加入后是否会形成环：收集当前节点的所有前驱子图，若存在任意前驱子图T，使得候选子图S能到达T（收缩图中存在路径S→T），则加入S会导致T→S（来自前驱节点到当前节点）与S→T形成环，无法加入
   • 若无法加入现有子图，创建新子图并分配当前节点
3. 维护收缩图：每次分配节点后，更新收缩图的邻接关系，确保后续环检查的准确性

C++实现代码 #

数据结构定义 #

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

const int MAX_NODES = 1000;

// 原DAG结构
vector<vector<int>> adj;               // 正向邻接表：u -> v
vector<vector<int>> reverse_adj;       // 反向邻接表：存储节点的所有前驱
vector<int> node_color;                // 每个节点的颜色（可替换为string类型）

// 子图管理数据
vector<int> node_to_subgraph;          // 节点对应的子图ID
unordered_map<int, vector<int>> color_to_subgraphs; // 颜色到对应子图列表
vector<int> subgraph_color;            // 子图对应的颜色
vector<vector<int>> subgraph_adj;      // 收缩图的邻接表
int subgraph_counter = 0;              // 子图ID计数器

拓扑排序函数 #

vector<int> topological_sort(int node_count) {
    vector<int> in_degree(node_count, 0);
    for (int u = 0; u < node_count; ++u) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }

    queue<int> q;
    // 找到唯一根节点（入度为0）
    for (int u = 0; u < node_count; ++u) {
        if (in_degree[u] == 0) {
            q.push(u);
            break;
        }
    }

    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        for (int v : adj[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    return topo_order;
}

收缩图路径检查（环检测核心） #

bool has_path(int start_subgraph, int end_subgraph) {
    if (start_subgraph == end_subgraph) return true;
    unordered_set<int> visited;
    queue<int> q;
    q.push(start_subgraph);
    visited.insert(start_subgraph);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int neighbor : subgraph_adj[curr]) {
            if (neighbor == end_subgraph) return true;
            if (!visited.count(neighbor)) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
    return false;
}

主处理函数 #

void partition_dag(int node_count) {
    vector<int> topo_order = topological_sort(node_count);
    // 初始化数据结构
    node_to_subgraph.assign(node_count, -1);
    subgraph_adj.clear();
    subgraph_color.clear();
    color_to_subgraphs.clear();
    subgraph_counter = 0;

    for (int u : topo_order) {
        int curr_color = node_color[u];
        int selected_sub = -1;

        // 尝试加入同颜色的最新子图
        if (color_to_subgraphs.find(curr_color) != color_to_subgraphs.end() && !color_to_subgraphs[curr_color].empty()) {
            int candidate_sub = color_to_subgraphs[curr_color].back();
            // 收集当前节点的前驱子图（去重）
            unordered_set<int> pred_subs;
            for (int pred : reverse_adj[u]) {
                pred_subs.insert(node_to_subgraph[pred]);
            }

            bool can_add = true;
            for (int t : pred_subs) {
                if (t == candidate_sub) continue;
                // 检查候选子图是否能到达前驱子图，若存在则会形成环
                if (has_path(candidate_sub, t)) {
                    can_add = false;
                    break;
                }
            }
            if (can_add) {
                selected_sub = candidate_sub;
            }
        }

        // 无法加入现有子图，创建新子图
        if (selected_sub == -1) {
            selected_sub = subgraph_counter++;
            color_to_subgraphs[curr_color].push_back(selected_sub);
            subgraph_color.push_back(curr_color);
            subgraph_adj.emplace_back(); // 初始化新子图的邻接表
        }

        // 分配节点到子图
        node_to_subgraph[u] = selected_sub;

        // 更新收缩图的边（去重）
        unordered_set<int> pred_subs;
        for (int pred : reverse_adj[u]) {
            pred_subs.insert(node_to_subgraph[pred]);
        }
        for (int t : pred_subs) {
            if (t == selected_sub) continue;
            // 避免重复添加边
            bool edge_exists = false;
            for (int neighbor : subgraph_adj[t]) {
                if (neighbor == selected_sub) {
                    edge_exists = true;
                    break;
                }
            }
            if (!edge_exists) {
                subgraph_adj[t].push_back(selected_sub);
            }
        }
    }

    // 输出划分结果（可选）
    cout << "Total subgraphs created: " << subgraph_counter << endl;
    for (int i = 0; i < subgraph_counter; ++i) {
        cout << "Subgraph " << i << " (color " << subgraph_color[i] << "): ";
        for (int u = 0; u < node_count; ++u) {
            if (node_to_subgraph[u] == i) {
                cout << u << " ";
            }
        }
        cout << endl;
    }
}

复杂度分析 #

• 拓扑排序：O(V+E)，V=1000，E为边数，最坏O(1e6)操作，效率极高
• 节点遍历与子图分配：每个节点最多执行一次环检查，每次环检查为BFS，时间复杂度O(S+E_s)（S为子图数量，E_s为收缩图边数），总操作量约1e6，在C++中可快速完成
• 整体时间：完全满足1000节点的运行时间要求

内容的提问来源于stack exchange，提问作者fromhell777