用C++设计并实现算法，找到图G的最小色数k，并对图中的顶点进行着色，确保相邻顶点使用不同颜色，输出最小着色数k及各顶点的着色。

在C++中，你可以使用经典的深度优先搜索(DFS)结合贪心策略来解决找图G的最小色数K的问题。这里是一个简单的算法描述：

1. **图表示**:
- 可以使用邻接矩阵或邻接表来存储图。邻接矩阵适合稠密图，邻接列表则更适合稀疏图。

2. **Breadth First Search (BFS)**:
- 首先，遍历图并标记所有顶点的颜色为0（初始颜色）。这将作为基础层。
- 对于每个新访问到的顶点，如果它的邻居已经用过一种颜色，则尝试下一个未使用的颜色；否则就继续分配新的颜色。

3. **Coloring Function**:
- 使用递归或迭代的方式，对于每个节点，检查其相邻节点是否已经有相同的颜色。如果没有，给当前节点分配一个未使用的颜色；如果有，增加颜色计数并尝试下一个颜色。

4. **检测是否完成**:
- 当所有顶点都被着色，并且没有两个相邻顶点同色时，说明找到了最小颜色数K。

5. **输出结果**:
- 最后，输出最小颜色数K以及每个顶点的着色信息。

以下是伪代码示例：

#include <vector>
using namespace std;

int min_color = 0;
vector<int> color_nodes(graph.size(), 0);

void dfs(int node, vector<vector<int>>& adj_list, vector<int>& visited) {
    visited[node] = true;
    for (int neighbor : adj_list[node]) {
        if (!visited[neighbor] && color_nodes[neighbor] == color_nodes[node]) {
            min_color++;
            color_nodes[node]++;
        }
    }
    // 更新节点颜色，使其与最近的已着色邻居不同
    while (color_nodes[node] == min_color) {
        color_nodes[node]++;
    }
}

int find_min_color(vector<vector<int>>& adj_list) {
    int nodes_count = adj_list.size();
    queue<int> q;
    q.push(0);
    vector<bool> visited(nodes_count, false);
    color_nodes[0] = 1; // 标记起点颜色

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        dfs(node, adj_list, visited);
    }

    return min_color;
}

// 示例用法：
vector<vector<int>> graph = ...; // 输入的邻接列表表示
int k = find_min_color(graph);
cout << "最小颜色数k: " << k << endl;
for (int i = 0; i < graph.size(); i++) {
    cout << "顶点" << i << "的着色: " << color_nodes[i] << endl;
}