Trong chương trình này, thực hiện tô màu cạnh của đồ thị sao cho hai cạnh kề không cùng màu. Các bước trong ví dụ.
Thuật toán
Bắt đầu Nhập số đỉnh n, số cạnh e. Đồ thị lưu dưới dạng danh sách kề. BFS dùng hàng đợi (queue) và gán màu cho từng cạnh. Kết thúc
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
queue<int> q;
int c = 0;
set<int> vertex_colored;
if (v[n])
return;
v[n] = 1;
for (i = 0; i < g[n].size(); i++) {
if (color[g[n][i].second] != -1) {
vertex_colored.insert(color[g[n][i].second]);
}
}
for (i = 0; i < g[n].size(); i++) {
if (!v[g[n][i].first]) {
q.push(g[n][i].first);
}
if (color[g[n][i].second] == -1) {
while (vertex_colored.find(c) != vertex_colored.end())
c++;
color[g[n][i].second] = c;
vertex_colored.insert(c);
c++;
}
}
while (!q.empty()) {
int temp = q.front();
q.pop();
col(temp);
}
return;
}
int main() {
int u, w;
set<int> empty;
cout << "Nhập số đỉnh và cạnh tương ứng: ";
cin >> n >> e;
cout << "\n";
g.resize(n); // số đỉnh
color.resize(e, -1); // số cạnh
memset(v, 0, sizeof(v));
for (i = 0; i < e; i++) {
cout << "\nNhập đỉnh của cạnh " << i+1 << " :\n";
cin >> u >> w;
u--; w--;
g[u].push_back(make_pair(w, i));
g[w].push_back(make_pair(u, i));
}
col(0);
for (i = 0; i < e; i++) {
cout << "Cạnh " << i+1 << " được tô màu " << color[i]+1 << "\n";
}
}
Kết quả
Nhập số đỉnh và cạnh tương ứng: 4 5 Nhập đỉnh của cạnh 1 : 1 2 Nhập đỉnh của cạnh 2 : 2 3 Nhập đỉnh của cạnh 3 : 1 1 Nhập đỉnh của cạnh 4 : 3 4 Nhập đỉnh của cạnh 5 : 1 4 Cạnh 1 được tô màu 1 Cạnh 2 được tô màu 2 Cạnh 3 được tô màu 2 Cạnh 4 được tô màu 1 Cạnh 5 được tô màu 3