图着色所需的最少颜色数

图着色所需的最少颜色数是一个基本的图论问题，它包括对顶点进行着色，使得没有两个相邻的顶点具有相同的颜色。确定有效着色所需的最小颜色数量。贪婪着色是一种简单且常用的技术，它根据顶点的邻居逐个对顶点进行着色。回溯法也会仔细分析所有颜色分配。基于DSatur的图着色优先考虑具有最高度和饱和度的顶点。

使用的方法

  • 贪婪着色

  • 回溯法

  • 图着色

贪婪着色方法

贪婪着色技术使图着色变得容易。它对第一个顶点进行着色，然后迭代其余的顶点。它通过检查其相邻顶点来为每个顶点分配最小的颜色。这种“贪婪”技术会做出局部最优的判断，而不会考虑颜色消耗。贪婪着色易于应用，通常效果很好，尽管它可能无法提供最少的颜色数量。

算法

  • 将大小为“numVertices”的数组“colours”的所有成员初始化为-1。

  • 对第一个图顶点0着色。

  • 对于从1到numVertices-1的每个顶点“v”，执行以下操作

    • 将相邻顶点的颜色存储在一个空集合“usedColors”中。

      迭代“v”的相邻顶点

    • 将相邻顶点的非零颜色添加到“usedColors”中。

    • 从0开始递增，直到“usedColors”不包含最小的颜色。

    • 在“colours”数组中为“v”赋予最小的颜色。

  • 找到“colours”数组中使用的最大颜色，并返回+1作为“minColors”。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest;
};

// Function to add an edge to the graph
void addEdge(std::vector<std::vector<int>>& graph, int src, int dest) {
    graph[src].push_back(dest);
    graph[dest].push_back(src);
}

// Greedy Coloring Algorithm
int greedyColoring(const std::vector<std::vector<int>>& graph, int numVertices) {
    std::vector<int> colors(numVertices, -1);
    colors[0] = 0;

    for (int vertex = 1; vertex < numVertices; ++vertex) {
        std::unordered_set<int> usedColors;
        for (int neighbor : graph[vertex]) {
            if (colors[neighbor] != -1) {
                usedColors.insert(colors[neighbor]);
            }
        }

        int availableColor = 0;
        while (usedColors.count(availableColor) != 0) {
            ++availableColor;
        }

        colors[vertex] = availableColor;
    }

    return *std::max_element(colors.begin(), colors.end()) + 1;
}

int main() {
    // Example usage
    int numVertices = 6;
    std::vector<Edge> edges = {
        {0, 1},
        {0, 2},
        {1, 2},
        {1, 3},
        {2, 3},
        {3, 4},
        {4, 5}
    };
    int numEdges = edges.size();

    std::vector<std::vector<int>> graph(numVertices);
    for (const auto& edge : edges) {
        addEdge(graph, edge.src, edge.dest);
    }

    int minColorsGreedy = greedyColoring(graph, numVertices);
   
    std::cout << "Minimum number of colors (Greedy Coloring): " << minColorsGreedy << std::endl;
   
    return 0;
}

输出

Minimum number of colors (Greedy Coloring): 3

回溯法

回溯法是一种查找所有可行解的方法。在图着色中，回溯法递归地为顶点分配颜色。当出现问题时，它会撤消颜色分配并考虑替代方案。回溯法可以确保对图着色所需的最小颜色数量，尽管由于其彻底的搜索，对于大型图来说，它的计算成本很高。

算法

  • 将大小为“numVertices”的数组“colours”的所有成员初始化为-1。

  • 对于从1到numVertices的“numColors”

  • 如果graphColoringUtil(graph, numColors, colours, 0)返回true，则返回“numColors”作为“minColors”。

  • 如果没有找到可接受的着色，则返回“numVertices”作为“minColors”。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest;
};

// Function to add an edge to the graph
void addEdge(std::vector<std::vector<int>>& graph, int src, int dest) {
    graph[src].push_back(dest);
    graph[dest].push_back(src);
}


// Backtracking Algorithm
bool isSafe(int vertex, const std::vector<std::vector<int>>& graph, const std::vector<int>& colors, int color) {
    for (int neighbor : graph[vertex]) {
        if (colors[neighbor] == color) {
            return false;
        }
    }
    return true;
}

bool graphColoringUtil(const std::vector<std::vector<int>>& graph, int numColors, std::vector<int>& colors, int vertex) {
    if (vertex == colors.size()) {
        return true;
    }

    for (int color = 0; color < numColors; ++color) {
        if (isSafe(vertex, graph, colors, color)) {
            colors[vertex] = color;
            if (graphColoringUtil(graph, numColors, colors, vertex + 1)) {
                return true;
            }
            colors[vertex] = -1;
        }
    }

    return false;
}

int backtrackingColoring(const std::vector<std::vector<int>>& graph, int numVertices) {
    std::vector<int> colors(numVertices, -1);

    for (int numColors = 1; numColors <= numVertices; ++numColors) {
        if (graphColoringUtil(graph, numColors, colors, 0)) {
            return numColors;
        }
    }

    return numVertices;
}

int main() {
    // Example usage
    int numVertices = 6;
    std::vector<Edge> edges = {
        {0, 1},
        {0, 2},
        {1, 2},
        {1, 3},
        {2, 3},
        {3, 4},
        {4, 5}
    };
    int numEdges = edges.size();

    std::vector<std::vector<int>> graph(numVertices);
    for (const auto& edge : edges) {
        addEdge(graph, edge.src, edge.dest);
    }

    int minColorsBacktracking = backtrackingColoring(graph, numVertices);
    std::cout << "Minimum number of colors (Backtracking): " << minColorsBacktracking << std::endl;

    return 0;
}

输出

Minimum number of colors (Backtracking): 3

图着色方法

复杂的图着色启发式算法DSatur（最大饱和度）减少了颜色使用。首先对度数最高的顶点着色。接下来检查饱和度，即每个顶点的邻居使用的颜色数量。为了打破平局，DSatur会对饱和度最高的顶点着色。

这种方法根据顶点的度数和饱和度来优化颜色组合。

算法

  • 将大小为“numVertices”的数组“colours”初始化为-1。

  • 将大小为“numVertices”的“saturation”数组初始化为0。

  • 使“saturationMap”为空。

  • 对图中度数最高的顶点0着色。

  • 更新所选顶点的相邻顶点的饱和度和saturationMap。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest;
};

// Function to add an edge to the graph
void addEdge(std::vector<std::vector<int>>& graph, int src, int dest) {
    graph[src].push_back(dest);
    graph[dest].push_back(src);
}

// Graph Coloring using DSatur Algorithm
int getMaxDegreeVertex(const std::vector<std::vector<int>>& graph, const std::vector<int>& saturation) {
    int maxDegree = -1;
    int maxDegreeVertex = -1;

    for (int vertex = 0; vertex < graph.size(); ++vertex) {
        if (saturation[vertex] == -1 && graph[vertex].size() > maxDegree) {
            maxDegree = graph[vertex].size();
            maxDegreeVertex = vertex;
        }
    }

    return maxDegreeVertex;
}

int dsaturColoring(const std::vector<std::vector<int>>& graph, int numVertices) {
    std::vector<int> colors(numVertices, -1);
    std::vector<int> saturation(numVertices, -1);
    std::unordered_map<int, int> saturationMap;

    colors[0] = 0;

    for (int vertex = 1; vertex < numVertices; ++vertex) {
        for (int neighbor : graph[vertex]) {
            if (colors[neighbor] != -1) {
                saturation[vertex]++;
                saturationMap[colors[neighbor]]++;
            }
        }
    }

    while (*std::max_element(colors.begin(), colors.end()) == -1) {
        int maxDegreeVertex = getMaxDegreeVertex(graph, saturation);

        std::unordered_set<int> usedColors;
        for (int neighbor : graph[maxDegreeVertex]) {
            if (colors[neighbor] != -1) {
                usedColors.insert(colors[neighbor]);
            }
        }

        int availableColor = 0;
        while (usedColors.count(availableColor) != 0) {
            ++availableColor;
        }

        colors[maxDegreeVertex] = availableColor;

        for (int neighbor : graph[maxDegreeVertex]) {
            if (colors[neighbor] == -1) {
                saturation[neighbor]++;
            }
        }

        saturationMap.clear();
        for (int vertex = 0; vertex < numVertices; ++vertex) {
            if (colors[vertex] == -1) {
                saturationMap[saturation[vertex]]++;
            }
        }

        int maxSaturation = -1;
        for (auto& entry : saturationMap) {
            if (entry.second > maxSaturation) {
                maxSaturation = entry.second;
            }
        }

        std::vector<int> maxSaturationVertices;
        for (int vertex = 0; vertex < numVertices; ++vertex) {
            if (colors[vertex] == -1 && saturation[vertex] == maxSaturation) {
                maxSaturationVertices.push_back(vertex);
            }
        }

        if (maxSaturationVertices.size() > 1) {
            int maxDegree = -1;
            for (int vertex : maxSaturationVertices) {
                if (graph[vertex].size() > maxDegree) {
                    maxDegree = graph[vertex].size();
                    maxDegreeVertex = vertex;
                }
            }
        }
        else {
            maxDegreeVertex = maxSaturationVertices[0];
        }
    }

    return *std::max_element(colors.begin(), colors.end()) + 1;
}

int main() {
    // Example usage
    int numVertices = 6;
    std::vector<Edge> edges = {
        {0, 1},
        {0, 2},
        {1, 2},
        {1, 3},
        {2, 3},
        {3, 4},
        {4, 5}
    };
    int numEdges = edges.size();

    std::vector<std::vector<int>> graph(numVertices);
    for (const auto& edge : edges) {
        addEdge(graph, edge.src, edge.dest);
    }


    int minColorsDSatur = dsaturColoring(graph, numVertices);

    std::cout << "Minimum number of colors (DSatur): " << minColorsDSatur << std::endl;

    return 0;
}

输出

Minimum number of colors (DSatur): 1

结论

总而言之，图论中的最小颜色问题有很多应用。我们讨论了贪婪着色、回溯法和DSatur图着色来解决这个问题。贪婪着色很简单，但它并不总是使用最少的颜色。回溯法可以确保最佳答案，但对于更大的网络来说，计算成本很高。DSatur的复杂启发式算法考虑顶点的度数和饱和度来优化图着色。

更新于：2023年7月17日

693 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告
© . All rights reserved.