資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學威爾什-鮑威爾圖著色演算法
圖著色在資訊科技中是一個關鍵問題，它在排程、暫存器分配和地圖著色等領域都有廣泛的應用。威爾什-鮑威爾演算法是一種有效的圖著色方法，它確保相鄰頂點具有不同的顏色，同時使用最少的顏色。在這篇文章中，我們將探討兩種使用C++演算法實現威爾什-鮑威爾演算法的方法。
使用的方法
順序頂點排序
最大優先頂點排序
順序頂點排序
第一種方法是根據頂點的度數遞減順序排列頂點，然後依次為頂點分配顏色。這種方法確保高度數頂點（通常具有更多鄰居）優先著色。
演算法
確定每個圖頂點的度數。
確定頂點的度數，並按降序排序。
在一個數組中設定每個頂點位置的分配顏色。
按照步驟2確定的順序重複步驟2。
為每個頂點分配最小的顏色，該顏色不會被其相鄰頂點使用。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Graph structure
struct Graph {
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list
// Constructor
Graph(int v) : V(v), adj(v) {}
// Function to add an edge between two vertices
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
};
// Function to compare vertices based on weight
bool compareWeights(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
// Function to perform graph coloring using Welsh-Powell algorithm
void graphColoring(Graph& graph) {
int V = graph.V;
vector<pair<int, int>> vertexWeights;
// Assign weights to each vertex based on their degree
for (int v = 0; v < V; v++) {
int weight = graph.adj[v].size();
vertexWeights.push_back(make_pair(v, weight));
}
// Sort vertices in descending order of weights
sort(vertexWeights.begin(), vertexWeights.end(), compareWeights);
// Array to store colors assigned to vertices
vector<int> color(V, -1);
// Assign colors to vertices in the sorted order
for (int i = 0; i < V; i++) {
int v = vertexWeights[i].first;
// Find the smallest unused color for the current vertex
vector<bool> usedColors(V, false);
for (int adjVertex : graph.adj[v]) {
if (color[adjVertex] != -1)
usedColors[color[adjVertex]] = true;
}
// Assign the smallest unused color to the current vertex
for (int c = 0; c < V; c++) {
if (!usedColors[c]) {
color[v] = c;
break;
}
}
}
// Print the coloring result
for (int v = 0; v < V; v++) {
cout << "Vertex " << v << " is assigned color " << color[v] << endl;
}
}
int main() {
// Create a sample graph
Graph graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 5);
// Perform graph coloring
graphColoring(graph);
return 0;
}
輸出
Vertex 0 is assigned color 2 Vertex 1 is assigned color 0 Vertex 2 is assigned color 1 Vertex 3 is assigned color 2 Vertex 4 is assigned color 0 Vertex 5 is assigned color 1
最大優先頂點排序
與方法1類似，第二種方法也包括根據頂點的度數遞減順序排列頂點。這種方法首先對最高度數頂點著色，然後遞迴地對其未著色的鄰居著色，而不是順序分配顏色。
演算法
確定每個圖頂點的度數。
確定頂點的度數，並按降序排序。
在一個數組中設定每個頂點位置的分配顏色。
從最高度數頂點開始著色。
為當前頂點的每個未著色的鄰居選擇最小的可用顏色。
示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
class Graph {
private:
int numVertices;
vector<unordered_set<int>> adjacencyList;
public:
Graph(int vertices) {
numVertices = vertices;
adjacencyList.resize(numVertices);
}
void addEdge(int src, int dest) {
adjacencyList[src].insert(dest);
adjacencyList[dest].insert(src);
}
int getNumVertices() {
return numVertices;
}
unordered_set<int>& getNeighbors(int vertex) {
return adjacencyList[vertex];
}
};
void welshPowellLargestFirst(Graph graph) {
int numVertices = graph.getNumVertices();
vector<int> colors(numVertices, -1);
vector<pair<int, int>> largestFirst;
for (int i = 0; i < numVertices; i++) {
largestFirst.push_back(make_pair(graph.getNeighbors(i).size(), i));
}
sort(largestFirst.rbegin(), largestFirst.rend());
int numColors = 0;
for (const auto& vertexPair : largestFirst) {
int vertex = vertexPair.second;
if (colors[vertex] != -1) {
continue; // Vertex already colored
}
colors[vertex] = numColors;
for (int neighbor : graph.getNeighbors(vertex)) {
if (colors[neighbor] == -1) {
colors[neighbor] = numColors;
}
}
numColors++;
}
// Print assigned colors
for (int i = 0; i < numVertices; i++) {
cout << "Vertex " << i << " - Color: " << colors[i] << endl;
}
}
int main() {
Graph graph(7);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 4);
graph.addEdge(1, 5);
graph.addEdge(2, 6);
graph.addEdge(3, 6);
welshPowellLargestFirst(graph);
return 0;
}
輸出
Vertex 0 - Color: 0 Vertex 1 - Color: 0 Vertex 2 - Color: 1 Vertex 3 - Color: 1 Vertex 4 - Color: 0 Vertex 5 - Color: 0 Vertex 6 - Color: 1
結論
這篇博文分析了兩種使用C++演算法實現威爾什-鮑威爾圖著色演算法的不同方法。每種方法在頂點排序和顏色分配方面採用了不同的策略，從而產生了高效且最佳化的圖著色方法。透過使用這些方法，我們可以有效地減少所需的顏色數量，同時確保相鄰頂點具有不同的顏色。威爾什-鮑威爾演算法憑藉其靈活性和簡潔性，仍然是各種圖著色應用中的一個有價值的工具。
更新於：2023年7月14日
1K+ 閱讀量
廣告