資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究雙分圖圖著色的 C++ 程式
雙分圖是如果可以透過兩種顏色對圖進行著色時的一種圖，即用同一種顏色對一個集合中的頂點進行著色。本程式以雙分圖作為輸入，並在對頂點進行著色後輸出每個頂點的顏色。
演算法
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<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<int> > g;
vector<int> color;
bool v[11101];
void c(int node,int n) {
queue<int> q;
if(v[node])
return;
color[node]=n;
v[node]=1;
for(i=0;i<n;i++) {
if(!v[g[node][i]]) {
q.push(g[node][i]);
}
}
while(!q.empty()) {
c(q.front(),(n+1)%2);
q.pop();
}
return;
}
int main() {
int a,b;
cout<<"Enter number of vertices and edges respectively:";
cin>>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<e;i++) {
cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
cin>>a>>b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
c(0,1);
for(i=0;i<n;i++) {
if(color[i])
cout<<i+1<<" "<<'Y'<<"\n";
else
cout<<i+1<<" "<<'B'<<"\n";
}
}輸出
Enter number of vertices and edges respectively: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
更新於： 2019 年 7 月 30 日
367 次檢視
廣告