C ++程序执行图形的边缘着色
在此程序中，我们将执行图的边缘着色，其中我们必须为图的边缘着色，以使两个相邻的边缘都不具有相同的颜色。示例中的步骤。
算法
Begin Take the input of the number of vertices, n, and then number of edges, e, in the graph. The graph is stored as adjacency list. BFS is implemented using queue and colors are assigned to each edge. End
示例
#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<<"分别输入顶点和边的数量：";
cin>>n>>e;
cout<<"\n";
g.resize(n); //number of vertices
color.resize(e,-1); //number of edges
memset(v,0,sizeof(v));
for(i = 0;i<e;i++) {
cout<<"\nEnter edge vertices of edge "<<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<<"Edge "<<i+1<<" is coloured with colour "<<color[i]+1
<< "\n";
}
}输出结果
分别输入顶点和边的数量：4 5 Enter edge vertices of edge 1 :1 2 Enter edge vertices of edge 2 :2 3 Enter edge vertices of edge 3 :1 1 Enter edge vertices of edge 4 :3 4 Enter edge vertices of edge 5 :1 4 Edge 1 is coloured with colour 1 Edge 2 is coloured with colour 2 Edge 3 is coloured with colour 2 Edge 4 is coloured with colour 1 Edge 5 is coloured with colour 3