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
热门推荐
1 训练狗狗搜寻
2 如何训练狗狗装死
3 狗狗训练书
6 怎么训练狗狗拜年
8 狗狗训练游戏
10 狗狗嗅觉训练
11 怎么训练狗狗在笼子里不叫
12 怎么训练狗狗站立走路
13 怎么训练狗狗在马桶上
14 狗狗尿尿怎么训练
15 训练狗狗用品
16 泰迪狗狗的训练方法大小便
17 训练狗狗可以打吗
18 王曼丽的狗狗训练