C++ DSatur 图着色算法

2025年3月24日 | 阅读 13 分钟

DSatur 算法由 Daniel Brelaz 于1979年开发，旨在通过高效地为图的顶点分配颜色来最小化使用的颜色总数，从而实现图着色。DSatur 算法高效且简单，尤其在处理大型图时效果显著。饱和度（Degree of Saturation）是该算法的名称，它对算法有着特殊的含义，解释了其主要原理。

DSatur 的核心是基于饱和度参数的顶点排序。这个值反映了分配给其邻接顶点的颜色数量。通过利用饱和度概念，DSatur 旨在仔细选择顶点，在着色图时优先考虑饱和度较高的顶点。通过这种策略，具有更多可用着色选项的顶点会被优先处理，这可能会产生最佳的着色结果。

该算法通过精心设计的步骤序列展开。首先建立一个空的优先队列，并将每个节点的饱和度设置为零。然后，根据饱和度从优先队列中移除顶点，如果存在平局则随机决定。首先为选定的顶点分配颜色，然后满足邻接顶点必须具有不同颜色的条件。当为邻接顶点分配新颜色后，每个顶点的饱和度都会被调整。当所有顶点都被着色后，该过程终止；迭代将持续到这一点。

此外，DSatur 的创新使得过多的选择和颜色的智能应用相结合。它处理具有较高饱和度的顶点，以便优先处理颜色选项较少的顶点。这可能是红色；使用所需的颜色数量来覆盖所有顶点。此外，DSatur 的简单性和通用性使其可用于处理无向图和有向图以及图的着色。

图着色

图着色是图论中的一个基本问题，它将颜色分配给图的顶点，使得两个相邻顶点不具有相同的颜色。主要目标是在遵守此约束的情况下最小化使用的颜色数量。这个问题出现在各种实际应用中，如调度、寄存器分配和地图着色。

饱和度

顶点的饱和度是指分配给其邻接顶点的唯一颜色的数量。饱和度较高的顶点受到更多限制，可供分配的颜色更少。因此，饱和度较高的顶点在着色过程中通常会被优先考虑，因为为它们分配颜色可能会在较小程度上限制它们的邻接顶点。理解和利用饱和度对于在最小化颜色使用数量的同时高效地为图着色至关重要。

方法 1：使用优先队列的邻接表表示

C++ 中 DSatur 算法的“使用优先队列的邻接表表示”方法使用邻接表来表示图，其中每个顶点存储其邻接顶点。优先队列根据饱和度管理顶点，确保着色过程中的高效选择。此方法有效地更新饱和度，并选择饱和度较高的顶点进行着色。它在简单性和性能之间取得平衡，是 C++ 中实现 DSatur 算法的流行选择，尤其适用于大型图。

程序

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>
using namespace std;
// Structure to represent a vertex in the graph
struct Vertex {
    int id;
    int colour;
    int saturationDegree;
    unordered_set<int> neighbors;

    Vertex(int id) : id(id), colour(-1), saturationDegree(0) {}
};
//Function to print the adjacency list representation of the graph
void printGraph(const vector<Vertex>& graph) {
    for (const Vertex& v : graph) {
        cout << "Vertex " << v.id << ": ";
        for (int neighbor : v.neighbors) {
            cout << neighbor << " ";
        }
        cout << endl;
    }
}
//Function to implement DSatur algorithm for graph colouring
void DSaturColouring(vector<Vertex>& graph) {
    // Priority queue to manage vertices based on saturation degree
    auto cmp = [](const Vertex& v1, const Vertex& v2) {
        return v1.saturationDegree < v2.saturationDegree;
    };
    priority_queue<Vertex, vector<Vertex>, decltype(cmp)> pq(cmp);

    // Initialize the saturation degree of each vertex
    for (Vertex& v : graph) {
        for (int neighbor : v.neighbors) {
            v.saturationDegree++;
        }
        pq.push(v);
    }

    // Colouring process
    while (!pq.empty()) {
        Vertex current = pq.top();
        pq.pop();

        // Find the smallest available colour for the current vertex
        unordered_set<int> usedColours;
        for (int neighbor : current.neighbors) {
            if (graph[neighbor].colour != -1) {
                usedColours.insert(graph[neighbor].colour);
            }
        }
        int colour = 0;
        while (usedColours.find(colour) != usedColours.end()) {
            colour++;
        }

        // Assign colour to the current vertex
        graph[current.id].colour = colour;

        // Update saturation degrees of neighbours
        for (int neighbor : current.neighbors) {
            if (graph[neighbor].colour == -1) {
                graph[neighbor].saturationDegree--;
                pq.push(graph[neighbor]); // Re-insert into priority queue
            }
        }
    }
}

int main() {
    // Sample graph 1
    vector<Vertex> graph1 = {
        Vertex(0),
        Vertex(1),
        Vertex(2),
        Vertex(3),
        Vertex(4)
    };
    graph1[0].neighbors = {1, 2};
    graph1[1].neighbors = {0, 2, 3};
    graph1[2].neighbors = {0, 1, 3, 4};
    graph1[3].neighbors = {1, 2, 4};
    graph1[4].neighbors = {2, 3};

    // Sample graph 2
    vector<Vertex> graph2 = {
        Vertex(0),
        Vertex(1),
        Vertex(2),
        Vertex(3)
    };
    graph2[0].neighbors = {1, 2};
    graph2[1].neighbors = {0, 2, 3};
    graph2[2].neighbors = {0, 1};
    graph2[3].neighbors = {1};

    // Print the adjacency list representations of the graphs
    cout << "Graph 1:" << endl;
    printGraph(graph1);
    cout << "Graph 2:" << endl;
    printGraph(graph2);
    // Colour the graphs using the DSatur algorithm
    DSaturColouring(graph1);
    DSaturColouring(graph2);
    // Print the colours assigned to vertices
    cout << "\nColours for Graph 1:" << endl;
    for (const Vertex& v : graph1) {
        cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
    }
    cout << "\nColours for Graph 2:" << endl;
    for (const Vertex& v : graph2) {
        cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
    }
    return 0;
}

输出

Graph 1:
Vertex 0: 2 1 
Vertex 1: 2 3 0 
Vertex 2: 4 3 1 0 
Vertex 3: 2 4 1 
Vertex 4: 3 2 
Graph 2:
Vertex 0: 2 1 
Vertex 1: 2 3 0 
Vertex 2: 1 0 
Vertex 3: 1 
Colours for Graph 1:
Vertex 0: Colour 2
Vertex 1: Colour 1
Vertex 2: Colour 0
Vertex 3: Colour 2
Vertex 4: Colour 1
Colours for Graph 2:
Vertex 0: Colour 2
Vertex 1: Colour 0
Vertex 2: Colour 1
Vertex 3: Colour 1

说明

提供的代码演示了使用邻接表表示和优先队列在 C++ 中实现 DSatur 算法进行图着色的详细过程。

它说明了计算饱和度、根据饱和度选择顶点以及在确保邻接顶点颜色不同的同时为顶点分配颜色的过程。此实现可应用于各种图着色问题，并且是实践中理解 DSatur 算法的基本示例。

图的表示

代码定义了一个 Vertex 结构来表示图中的每个顶点。每个顶点包含一个 ID、一个颜色（初始化为 -1）、一个饱和度和一个存储在无序集中的邻接顶点集合。

使用 Vertex 对象向量创建了两个示例图。这些图的邻接表是通过手动指定每个顶点的邻接顶点来定义的。

优先队列初始化

DSatur 算法依赖于优先队列来根据饱和度管理顶点。定义了一个自定义比较器函数，用于根据饱和度比较顶点，并使用此比较器创建了优先队列 pq。

饱和度计算

通过遍历每个顶点的邻居来计算其饱和度，并为每个邻接顶点增加饱和度。然后将每个顶点推入优先队列 pq 以便进一步处理。

着色过程

主要的DSatur 算法开始时，从优先队列中反复选择具有最高饱和度的顶点。对于每个选定的顶点，算法会找到一个未被其邻接顶点使用的最小可用颜色。

然后，将选定的顶点分配此颜色，并相应地更新其邻居的饱和度。该过程一直持续到优先队列 pq 为空，这表示所有顶点都已着色。

输出

使用 DSatur 算法着色图后，代码会打印出分配给两个图中每个顶点的颜色。颜色以“顶点 ID：颜色”的格式显示。

复杂度分析

时间复杂度

初始化（图创建）

创建图的邻接表表示涉及遍历所有顶点及其邻居。

时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。

饱和度计算

算法在计算饱和度时会遍历每个顶点的邻居。

时间复杂度：O(V * avg_degree)，其中 avg_degree 是图中顶点的平均度。

优先队列操作

在主要的DSatur 算法循环中执行插入、删除和查找最大元素等优先队列操作。在每次迭代中，算法可能需要执行与顶点数量成比例的优先队列操作。

考虑优先队列操作，平均时间复杂度：O(V * log(V))。

颜色分配和饱和度更新

在DSatur 算法循环内，顶点颜色分配和邻接顶点饱和度更新涉及遍历邻接顶点，但迭代次数取决于饱和度。

循环内的总时间复杂度：O(V * avg_degree)，与饱和度计算类似。

总时间复杂度

对时间复杂度贡献最大的因素是初始化(O(V + E))和 DSatur 算法循环 (O(V * log(V)))。

因此，DSatur 算法实现的总体时间复杂度通常是O(V * log(V))。

空间复杂度

邻接表表示

DSatur 算法采用邻接表来存储顶点及其邻接顶点。这种表示需要与顶点和边数量成比例的额外空间，导致空间复杂度为O(V + E)。

优先队列

DSatur 使用优先队列来根据饱和度存储顶点。优先队列需要空间来存储所有顶点，从而为总体空间复杂度贡献O(V)。

其他数据结构

使用了各种其他数据结构，例如用于存储已用颜色的集合、用于邻接顶点的无序集以及用于饱和度的变量。尽管它们的空间需求通常与顶点数量成比例，但它们额外贡献了O(V)的空间复杂度。

总空间复杂度

对空间复杂度贡献最大的因素是邻接表表示，DSatur 算法实现的总体空间复杂度为O(V + E)。

方法 2：使用优先队列的邻接矩阵表示

“使用优先队列的邻接矩阵表示”方法使用邻接矩阵来表示图，其中矩阵中的每个单元格指示两个顶点之间是否存在边。此外，还使用优先队列来根据饱和度管理顶点，确保着色过程中的高效选择。每次颜色分配后都会有效更新饱和度，以保持顶点优先级的准确性。

该方法提供了一种简单有效的方式来实现 DSatur 算法进行图着色，特别适用于邻接矩阵比邻接表更节省空间的稠密图。邻接矩阵提供了图连通性的紧凑表示，而优先队列则促进了高效的顶点管理，这种方法在解决图着色问题时平衡了简单性和性能。

程序

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// Structure to represent a vertex in the graph
struct Vertex {
    int id;
    int colour;
    int saturationDegree;
    Vertex(int id) : id(id), colour(-1), saturationDegree(0) {}
};
//Function to print the adjacency matrix representation of the graph
void printGraph(const vector<vector<int>>& adjacencyMatrix, int vertices) {
    cout << "Adjacency Matrix:" << endl;
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < vertices; ++j) {
            cout << adjacencyMatrix[i][j] << " ";
        }
        cout << endl;
    }
}
//Function to implement DSatur algorithm for graph colouring using adjacency matrix
void DSaturColouring(vector<vector<int>>& adjacencyMatrix, vector<Vertex>& graph, int vertices) {
    // Priority queue to manage vertices based on saturation degree
    auto cmp = [](const Vertex& v1, const Vertex& v2) {
        return v1.saturationDegree < v2.saturationDegree;
    };
    priority_queue<Vertex, vector<Vertex>, decltype(cmp)> pq(cmp);
    // Initialize the saturation degree of each vertex
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < vertices; ++j) {
            if (adjacencyMatrix[i][j] == 1) {
                graph[i].saturationDegree++;
            }
        }
        pq.push(graph[i]);
    }
    // Colouring process
    while (!pq.empty()) {
        Vertex current = pq.top();
        pq.pop();
        // Find the smallest available colour for the current vertex
        unordered_set<int> usedColours;
        for (int i = 0; i < vertices; ++i) {
            if (adjacencyMatrix[current.id][i] == 1 && graph[i].colour != -1) {
                usedColours.insert(graph[i].colour);
            }
        }
        int colour = 0;
        while (usedColours.find(colour) != usedColours.end()) {
            colour++;
        }
        // Assign colour to the current vertex
        graph[current.id].colour = colour;
        // Update saturation degrees of neighbors
        for (int i = 0; i < vertices; ++i) {
            if (adjacencyMatrix[current.id][i] == 1 && graph[i].colour == -1) {
                graph[i].saturationDegree--;
                pq.push(graph[i]); // Re-insert into priority queue
            }
        }
    }
}
int main() {
    // Sample graph 1
    int vertices1 = 5;
    vector<vector<int>> adjacencyMatrix1 = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 1, 1},
        {0, 1, 1, 0, 1},
        {0, 0, 1, 1, 0}
    };
    vector<Vertex> graph1;
    for (int i = 0; i < vertices1; ++i) {
        graph1.push_back(Vertex(i));
    }
    // Sample graph 2
    int vertices2 = 4;
    vector<vector<int>> adjacencyMatrix2 = {
        {0, 1, 1, 0},
        {1, 0, 1, 1},
        {1, 1, 0, 0},
        {0, 1, 0, 0}
    };
    vector<Vertex> graph2;
    for (int i = 0; i < vertices2; ++i) {
        graph2.push_back(Vertex(i));
    }
    // Print the adjacency matrix representations of the graphs
    cout << "Graph 1:" << endl;
    printGraph(adjacencyMatrix1, vertices1);
    cout << "Graph 2:" << endl;
    printGraph(adjacencyMatrix2, vertices2);
    // Colour the graphs using the DSatur algorithm
    DSaturColouring(adjacencyMatrix1, graph1, vertices1);
    DSaturColouring(adjacencyMatrix2, graph2, vertices2);
    // Print the colours assigned to vertices
    cout << "\nColours for Graph 1:" << endl;
    for (const Vertex& v : graph1) {
        cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
    }
    cout << "\nColours for Graph 2:" << endl;
    for (const Vertex& v : graph2) {
        cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
    }
    return 0;
}

输出

Graph 1:
Adjacency Matrix:
0 1 1 0 0 
1 0 1 1 0 
1 1 0 1 1 
0 1 1 0 1 
0 0 1 1 0 
Graph 2:
Adjacency Matrix:
0 1 1 0 
1 0 1 1 
1 1 0 0 
0 1 0 0 
Colours for Graph 1:
Vertex 0: Colour 2
Vertex 1: Colour 1
Vertex 2: Colour 0
Vertex 3: Colour 2
Vertex 4: Colour 1
Colours for Graph 2:
Vertex 0: Colour 2
Vertex 1: Colour 0
Vertex 2: Colour 1
Vertex 3: Colour 1

说明

图的表示

代码定义了一个 Vertex 结构来表示图中的每个顶点。每个顶点包含一个 ID、一个颜色（初始化为 -1）和一个饱和度。

使用邻接矩阵创建了两个示例图，其中矩阵中的每个单元格指示两个顶点之间是否存在边。

打印邻接矩阵

定义了printGraph 函数来打印图的邻接矩阵表示。它遍历邻接矩阵的元素并逐行打印。

DSatur 算法实现

DSatur 算法实现在DSaturColouring 函数中。它将邻接矩阵、表示图的 Vertex 对象向量以及顶点数作为输入参数。

该函数初始化一个优先队列来根据饱和度管理顶点。最初，顶点及其计算出的饱和度被推入优先队列。主要的 DSatur 算法循环开始，其中顶点根据其饱和度从优先队列中出队。

对于每个出队的顶点，算法会找到一个未被其邻接顶点使用的最小可用颜色。然后，将该顶点分配此颜色，并更新其饱和度。相应地更新邻接顶点的饱和度，并将受影响的顶点重新插入优先队列。该过程一直持续到优先队列为空，这表示所有顶点都已着色。

输出

使用 DSatur 算法着色图后，代码会打印出分配给两个图中每个顶点的颜色。颜色以“顶点 ID：颜色”的格式显示。

复杂度分析

时间复杂度

初始化（图创建）

创建邻接矩阵涉及遍历所有顶点及其潜在边，导致时间复杂度为O(V^2)，其中 V 是顶点数。

饱和度计算

计算饱和度涉及遍历邻接矩阵以计数邻接顶点，需要 O(V^2) 操作。

优先队列操作

DSatur 算法循环期间对优先队列的操作，如插入、删除和查找最大元素，通常需要 O(log V) 的时间。由于有 V 个顶点，优先队列操作的总时间复杂度为O (V * log V)。

颜色分配和饱和度

在 DSatur 算法循环内，颜色分配和饱和度更新涉及遍历邻接顶点，在最坏情况下可能需要 O(V) 时间。此操作对图中的每个顶点执行一次，总时间复杂度为O(V^2)。

总时间复杂度

对时间复杂度贡献最大的因素是初始化 (O(V^2)) 和 DSatur 算法循环(O(V^2))。

因此，使用邻接矩阵表示和优先队列的 DSatur 算法实现的总体时间复杂度为O(V^2)。

空间复杂度

邻接矩阵

邻接矩阵表示需要O(V^2)的空间来存储顶点之间的连通性，其中 V 是顶点数。

优先队列

优先队列根据饱和度存储顶点，需要与顶点数成比例的额外空间，即O(V)。

其他数据结构

支持数据结构，如用于已用颜色的集合和用于饱和度的变量，需要额外的空间，这也与顶点数成比例，即O(V)。

总空间复杂度

邻接矩阵表示 (O(V^2)) 是主要因素，它影响空间复杂度。因此，DSatur 算法实现的总体空间复杂度为O(V^2)。

下一主题如何使用 C++ 中的栈找到直方图中的最大矩形面积

C++ DSatur 图着色算法

图着色

饱和度

方法 1：使用优先队列的邻接表表示

程序

方法 2：使用优先队列的邻接矩阵表示

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ DSatur 图着色算法

图着色

饱和度

方法 1：使用优先队列的邻接表表示

程序

方法 2：使用优先队列的邻接矩阵表示

程序

相关帖子

C++ 分形排序

C++ 中的迪洛尔数

C++ CLI 和 C++/CX 之间的区别

C++ std::strided_slice 函数

C++ 中的最优文件合并模式

C++ 中的 std::uninitialized_value_construct

如何使用 Win32 和 COM API 在 C++ 中编写桌面程序

基于数组的队列与基于链表的队列的区别

C++ 中的 std::piecewise_construct_t

C++ 中的员工空闲时间问题

订阅 Tpoint Tech

联系信息

关注我们

教程