二分图--染色问题

图的表示方法：

（1）邻接矩阵（2）邻接表

邻接矩阵：用V*V的二维数组来表示图，g[i][j]表示顶点i和顶点j的关系，比如无向图中，可以用g[i][j]=1表示i和j有边相连，=0表示无边相连。无向图的邻接矩阵是对称矩阵，因为g[i][j]=g[j][i]。有向图可以用g[i][j]=1表示i有指向j的边，故不是对称矩阵。带权图则可以用g[i][j]表示i到j的权，若无边相连则可以将其设置为无穷大。若一条边上有多种不同权值则可以用结构体数组的方式来表示。邻接矩阵十分方便，缺点是空间浪费过多。

邻接表：保存的信息是“从顶点0出发有到顶点123的边”，这样的形式可以用链表来储存。下面是两种实现方式

vector<int> G[MAX_V];//图的表示
/*
若边上带权，可以用
struct edge{int to,cost;};
vector<edge> G[MAX_V];//图的表示
*/

struct vertex
{
vector<vertex*> edge;
/*
顶点属性
*/
};

例题：简单的图dfs，二分图判定




简单图的应用，dfs代码如下

//二分图判定
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int MAX_V=10000;
vector<int> G[MAX_V];//图的表示
int V;//顶点数
int color[MAX_V];//顶点i的颜色1或-1
//把顶点染成1或-1
bool dfs(int v,int c)
{
color[v]=c;//顶点v染成c
for (int i = 0; i < G[v].size(); ++i)
{
//相邻点同色，返回false
if(color[G[v][i]]==c)
return false;
//相邻点没有染色，就将其染色为-c，继续dfs，若最终仍为false，则返回false
if(color[G[v][i]]==0 && !dfs(G[v][i],-c))
return false;
}
//所有顶点染过色返回true
return true;
}
void solve()
{
//如果是连通图，则一次dfs即可访问所有位置
//但题目没有说明，故要依次检查各个顶点的情况
for (int i = 0; i < V; ++i)
{
if (color[i]==0)
{
//如果顶点还没有染色，染成1
if (!dfs(i,1))
{
cout<<"No"<<endl;
return;
}
}
}
cout<<"Yes"<<endl;
}
int main(int argc, char const *argv[])
{
solve();
return 0;
}

附一道二分图判定的题，NYOJ的1015


可以看出就是用染色法判断是否为二分图的一道题，而且已经知道是连通图，只需要从0开始dfs，AC代码如下，注意无向图要连两次！！可能由于初学在这里卡了好久。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdlib>
#define MAX_V 210
using namespace std;
vector<int>G[MAX_V];//这里用不定长数组，来存图。
int V,E,color[MAX_V];
bool dfs(int v,int c){
color[v] = c;
for(int i=0;i<G[v].size();i++){//连接这个节点的所有节点
if(color[G[v][i]] == c) return false;
if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false;
/*注意这一步，不能分解，因为当该层的下一层，返回false时，到递归回到这一层仍要返回false。*/
}
return true;
}
void solve()
{
if(!dfs(0,1)){//本题是从0这个节点来搜索就可，但有些题目，图可能不是联通的，故要从头到尾遍历一遍。
printf("NOT BICOLORABLE.n");
return;
}
printf("BICOLORABLE.n");
return;
}
int main(void)
{
while(~scanf("%d",&V)){
scanf("%d",&E);
memset(color,0,sizeof(color));
memset(G,0,sizeof(G));
int a,b;
for(int i=0;i<E;i++)
{
scanf("%d %d",&a,&b);//这里是无向图，要存存两次，本人就在这里WA了好多次，惭愧，一定细心。
G[a].push_back(b);
G[b].push_back(a);
}
solve();
}
return 0;
}

最后有个十分不解的地方，就是此处的图已经确定是连通图了，所以solve函数不需要for循环一个一个判断是否染过色，但按道理说按照上面考虑非连通图的方法，写个for循环一个一个判断也是没问题的，但此处无法AC，所以十分不理解。希望可能有大神指教。

最后

以上就是温暖镜子为你收集整理的二分图--染色问题的全部内容，希望文章能够帮你解决二分图--染色问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。