威爾斯-鮑威爾圖著色演算法

圖形著色是資訊科技中的關鍵問題，在調度、暫存器分配和地圖著色等領域有廣泛的應用。威爾斯鮑威爾演算法是一種有效的對圖進行著色的方法，可以確保附近的頂點具有各種陰影，同時使用較少的顏色。在這篇文章中，我們將研究使用 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

最大第一個頂點排序

與方式一類似，第二種方式包括依照頂點的度數以降序排列頂點。這種方法首先對最高程度的頂點進行著色，然後遞歸地為其未著色的鄰居著色，而不是順序分配顏色。

演算法

• 決定每個圖頂點的度數。

• 決定頂點的度數並依降序對它們進行排序。

• 為陣列中每個頂點的位置設定指派的顏色。

• 從最大度數的頂點開始著色。

• 選擇目前未著色頂點的每個鄰居可用的最少顏色。

範例

#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 演算法建立威爾斯鮑威爾圖著色技術的兩種不同方法。每種方法在對頂點進行排序和分配顏色時都採取了不同的策略，從而產生了有效且最佳化的圖形著色方法。透過使用這些技術，我們可以有效地減少所需的顏色數量，同時確保附近的頂點包含不同的顏色。憑藉其適應性和簡單性，威爾斯鮑威爾演算法仍然是各種圖形著色應用中的有用工具。

以上是威爾斯-鮑威爾圖著色演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！