C++程序-无向图

此题于POJ1419类似，以下是我以前写得总结，用DFS（回溯）实现的，供你参考。

POJ 1419 Graph Coloring

给出一个图，图中的每个点只能填黑色或白色，且相邻的两个点不能同为黑色。要你给出一种方案，是图中填的黑色的点最多。输出黑色的点的数量和其标号。

从1开始依序号依次搜索，对于每个要填色的点，先判断其周围有没有黑色的点，没有的话就分为填黑色和填白色两种情况讨论，有的话就只能填白色了。

调用：search(1)

void search(int i)

{

int flag=0

int k

if(i==n)

{

if(now>maxx)

{

for(k=1k<=nk++) best[k]=color[k]

maxx=now

}

return

}

for(k=1k<=nk++) //判断i的周围是否存在黑点

{

if(g[i][k]==1)

{

if(color[k]==1)

{

flag=1

break

}

}

}

if(!flag)//i的周围不存在黑点的话则i可以放黑点

{

color[i]=1

now++

search(i+1) //不是DSF，是按点的序号依次搜索 。在i放黑点的情况下继续搜索。

color[i]=0

now--

}

if(now+(n-i)/2>maxx) //剪枝，当i不能放黑点但可能存在比当前最优解更好的解时才继续计算

search(i+1) //一定要有这句，这是在i不放黑点的情况下继续搜索。可以不要if，即不剪枝，能通过。

}

另外,虚机团上产品团购,超级便宜

#include<stdio.h>

#include<stdlib.h>

#define infinity 100 //权最大值定为100，相当于正无穷

#define max 3//最大顶点数3个

typedef struct ArcCell{

int weight //权值

}ArcCell,AdjMatrix[max][max]

typedef struct{ //图

char vexs[max]

AdjMatrix arcx

int vexnum,arcnum

}MGrap

void CreateUDN(MGrap &G)

int main(){

MGrap G

CreateUDN(G)

return 0

}

void CreateUDN(MGrap &G)

{

int i,j,k

printf("Input the number of vex and arc:") //分别输入顶点和弧的个数

scanf("%d %d",&G.vexnum,&G.arcnum)

for(i=0i<G.vexnumi++) //依次输入每个顶点

{

printf("请输入第%d个顶点",i+1)

scanf("%c",&G.vexs[i])

}

for(i=0i<G.vexnumi++)

for(j=0j<G.vexnumj++)

G.arcx[i][j].weight = infinity

for(i=0i<G.arcnumi++)

{

printf("请输入弧的两端点:(NO.%d)",i+1) //输入第i+1条弧的两端点，确定弧

scanf("%d %d ",&k,&j )

scanf("%d",&G.arcx[k][j].weight)

G.arcx[j][k]=G.arcx[k][j] //无向图弧关于对角线对称

}

}

---