好资源导航 » 文章资讯 » 在二部图上执行图着色的 C++ 程序

在二部图上执行图着色的 C++ 程序

2023-06-20 12:07:02 78

二部图是这样一种图，其中如果可以使用两种颜色对图进行着色，即；集合中的顶点用相同的颜色着色。在这个程序中，我们将一个二部图作为输入，并在对顶点着色后输出每个顶点的颜色。

算法

Begin
   BFS algorithm is used to traverse all the vertices.
   Take a vertex and colour it yellow.
   Colour all its neighbour vertices as blue.
   Colour the next level vertices as yellow and so, until all vertices are coloured.
End.

示例代码

#include
using namespace std;
int n, e, i, j;
vector > g;
vector color;
bool v[11101];
void c(int node,int n) {
   queue q;
   if(v[node])
      return;
   color[node]=n;
   v[node]=1;
   for(i=0;i>n>>e;
   cout<<"'Y' is for Yellow Colour and 'B' is for Blue Colour.";
   cout<<"\n";
   g.resize(n);
   color.resize(n);
   memset(v,0,sizeof(v));
   for(i=0;i>a>>b;
      a--; b--;
      g[a].push_back(b);
      g[b].push_back(a);
   }
   c(0,1);
   for(i=0;i输出结果分别输入顶点数和边数：4 3
'Y' is for Yellow Colour and 'B' is for Blue Colour.

Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :3 2
Enter edge vertices of edge 3 :4 2
1 Y
2 B
3 B
4 B

返回顶部
514930285
czq8825@qq.com

在二部图上执行图着色的 C++ 程序

算法

示例代码

热门推荐

随机推荐