資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究DSatur 演算法用於圖著色
簡介
圖著色可能是圖論中的一個重要問題。DSatur 演算法提供了一種有效的方法來減少在執行圖著色時的顏色使用。透過有策略地選擇飽和度最高的頂點，DSatur 確保了最佳化的顏色分配，最大化顏色多樣性並最小化顏色使用。
在本文中，我們探討了用於圖著色的 DSatur 演算法及其在 C++ 中的應用。該演算法的名字源於它使用的兩個關鍵概念：度數和飽和度。它考慮了頂點的度數及其飽和度，後者表示其鄰居使用的不同顏色的數量。
DSatur 演算法用於圖著色
DSatur 演算法是一種圖著色策略，用於圖論，在計算機科學和最佳化中具有重要應用。它圍繞著將顏色分配給圖的頂點的任務，確保沒有兩個相鄰的頂點共享相同的顏色。透過使用巧妙的策略，DSatur 旨在減少成功著色圖所需的總顏色數。在每個步驟中，演算法選擇具有最高飽和度（即，到目前為止已著色的相鄰頂點的數量）的頂點，並將其分配給其鄰居尚未使用的顏色。這種方法導致最佳化的著色，最大化顏色多樣性，並最小化顏色使用。DSatur 演算法為圖著色問題提供了一種高效且實用的解決方案，使其成為不同計算機科學和最佳化領域中的基本工具。
該演算法首先選擇度數最高的頂點作為起始頂點，並將其分配給第一種顏色。然後迭代地選擇未著色頂點中飽和度最高的頂點。如果出現平局，則選擇度數最高的頂點。
方法 1：使用鄰接表
在這種方法中，圖使用鄰接表表示。該演算法將起始顏色分配給第一個頂點，並透過計算其相鄰頂點使用的不同顏色來計算每個頂點的飽和度。然後，它繼續迭代地對其餘頂點進行著色，選擇飽和度最高的頂點並分配最小的可用顏色。
演算法
步驟 1 − 建立一個鄰接表來表示圖，其中列表的每個元素表示一個頂點並存儲其相鄰頂點。
步驟 2 − 實現 DSaturGraphColoring 函式。
步驟 3 − 初始化三個向量 − colors 用於儲存每個頂點的分配顏色，saturation 用於儲存每個頂點的飽和度，以及 available 用於跟蹤可用顏色。最初，所有顏色都設定為 -1，飽和度設定為 0，並且所有顏色都可用。
步驟 4 − 將起始顏色（0）分配給第一個頂點，並在 colors 向量中將其標記為已著色。
步驟 5 − 透過遍歷鄰接表並檢查其相鄰頂點使用的不同顏色來計算每個頂點的飽和度。將飽和度儲存在 saturation 向量中。
步驟 6 − 從 colors 向量中列印頂點-顏色對。
示例
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
class MyNewGraph {
int numVertices;
list<int> *adjList;
public:
MyNewGraph(int vertices) {
numVertices = vertices;
adjList = new list<int>[vertices];
}
void addMyEdge(int vertexA, int vertexB) {
adjList[vertexA].push_back(vertexB);
adjList[vertexB].push_back(vertexA);
}
void performMyDSaturGraphColoring();
};
void MyNewGraph::performMyDSaturGraphColoring() {
vector<int> vertexColors(numVertices, -1);
vector<int> saturationDegree(numVertices, 0);
vector<bool> colorAvailability(numVertices, true);
vertexColors[0] = 0;
for (int myIndex = 1; myIndex < numVertices; myIndex++) {
for (int myVertex : adjList[myIndex]) {
if (vertexColors[myVertex] != -1)
saturationDegree[myIndex]++;
}
}
for (int k = 1; k < numVertices; k++) {
int myMaxSaturation = -1;
int myVertex = -1;
for (int myIndex = 0; myIndex < numVertices; myIndex++) {
if (vertexColors[myIndex] == -1 && saturationDegree[myIndex] > myMaxSaturation) {
myMaxSaturation = saturationDegree[myIndex];
myVertex = myIndex;
}
}
int availableColor = 0;
while (!colorAvailability[availableColor]) {
availableColor++;
}
vertexColors[myVertex] = availableColor;
colorAvailability[availableColor] = false;
for (int myVertex : adjList[myVertex]) {
saturationDegree[myVertex]++;
}
}
cout << "MyVertex\tMyColor" << endl;
for (int myIndex = 0; myIndex < numVertices; myIndex++) {
cout << myIndex << "\t" << vertexColors[myIndex] << endl;
}
}
int main() {
MyNewGraph myNewGraph(4);
myNewGraph.addMyEdge(0, 1);
myNewGraph.addMyEdge(0, 2);
myNewGraph.addMyEdge(0, 3);
myNewGraph.addMyEdge(2, 3);
myNewGraph.performMyDSaturGraphColoring();
return 0;
}
輸出
MyVertex MyColor 0 0 1 0 2 1 3 2
方法 2：使用矩陣表示
在這種方法中，圖使用矩陣表示。該演算法將起始顏色分配給第一個頂點，並透過檢查其相鄰頂點使用的不同顏色來計算每個頂點的飽和度。然後，它迭代地對其餘頂點進行著色，選擇飽和度最高的頂點並分配最小的可用顏色。
演算法
步驟 1 − 建立一個矩陣來表示圖，其中每個單元格表示兩個頂點之間的邊。
步驟 2 − 實現 DSatur 圖著色函式。
步驟 3 − 初始化三個向量 − colors 用於儲存每個頂點的分配顏色，saturation 用於儲存每個頂點的飽和度，以及 available 用於跟蹤可用顏色。最初，所有顏色都設定為 -1，飽和度設定為 0，並且所有顏色都可用。
步驟 4 − 將起始顏色（0）分配給第一個頂點，並在 colors 向量中將其標記為已著色。
步驟 5 − 透過迭代矩陣來計算每個頂點的飽和度，並
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MyNewGraph {
int myNumVertices;
vector<vector<int>> myAdjacencyMatrix;
public:
MyNewGraph(int vertices) {
myNumVertices = vertices;
myAdjacencyMatrix.resize(vertices, vector<int>(vertices, 0));
}
void addMyEdge(int myVertex1, int myVertex2) {
myAdjacencyMatrix[myVertex1][myVertex2] = 1;
myAdjacencyMatrix[myVertex2][myVertex1] = 1;
}
void performMyDSaturGraphColoring();
};
void MyNewGraph::performMyDSaturGraphColoring() {
vector<int> myVertexColors(myNumVertices, -1);
vector<int> mySaturationDegree(myNumVertices, 0);
vector<bool> myColorAvailability(myNumVertices, true);
myVertexColors[0] = 0;
for (int myIndex = 1; myIndex < myNumVertices; myIndex++) {
for (int myVertex : myAdjacencyMatrix[myIndex]) {
if (myVertexColors[myVertex] != -1)
mySaturationDegree[myIndex]++;
}
}
for (int k = 1; k < myNumVertices; k++) {
int myMaxSaturation = -1;
int myVertex = -1;
for (int myIndex = 0; myIndex < myNumVertices; myIndex++) {
if (myVertexColors[myIndex] == -1 && mySaturationDegree[myIndex] > myMaxSaturation) {
myMaxSaturation = mySaturationDegree[myIndex];
myVertex = myIndex;
}
}
int myAvailableColor = 0;
while (!myColorAvailability[myAvailableColor]) {
myAvailableColor++;
}
myVertexColors[myVertex] = myAvailableColor;
myColorAvailability[myAvailableColor] = false;
for (int myIndex = 0; myIndex < myNumVertices; myIndex++) {
if (myAdjacencyMatrix[myVertex][myIndex]) {
mySaturationDegree[myIndex]++;
}
}
}
cout << "MyVertex\tMyColor" << endl;
for (int myIndex = 0; myIndex < myNumVertices; myIndex++) {
cout << myIndex << "\t" << myVertexColors[myIndex] << endl;
}
}
int main() {
MyNewGraph myNewGraph(4);
myNewGraph.addMyEdge(0, 1);
myNewGraph.addMyEdge(0, 2);
myNewGraph.addMyEdge(0, 3);
myNewGraph.addMyEdge(2, 3);
myNewGraph.performMyDSaturGraphColoring();
return 0;
}
輸出
MyVertex MyColor 0 0 1 0 2 1 3 2
結論
DSatur 演算法為圖著色提供了一種有效且強大的策略，考慮了頂點的度數和飽和度水平。透過智慧地將顏色分配給圖的頂點，它旨在減少使用的顏色數量。透過本文，我們探討了 DSatur 演算法，並提供了其三種方法的分步說明。我們使用 C++ 中的鄰接列表表示法實現了方法 1，確保了一致的著色結果。程式程式碼說明了 DSatur 演算法在各種圖著色場景中的實際應用，展示了它產生最優著色解決方案的能力。總的來說，DSatur 演算法是圖論中一個重要的工具，有助於最佳化顏色分配，同時減少顏色使用。
676 次瀏覽
