近似算法的顶点覆盖问题的近似算法

问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。

VertexSet approxVertexCover ( Graph g )

{ cset=NULL；

e1=g.e；

while (e1 !=NULL) {

从e1中任取一条边(u,v)；

cset=cset∪{u,v}；

从e1中删去与u和v相关联的所有边；

}

return c

}

Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。

图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。

因为计算机中的小数保存都是以近似值来表示的，譬如你这里的20.7就是以20.7000...001来表示的，当然有时候也会是以20.699....9来表示，这完全是你cpu决定的，如果要输出正常格式的话，就把程序改我这样，这样后面就没有无意义的小数位输出了，输出的是正确值

#include <stdio.h>

void main ()

{float *np,*nend,num[10],max,min

int i

np=nend=num

printf("Enter 10 number :\n")

for (np=numnp<num+10np++)

scanf ("%f",np)

max=min=*num

for (np=num+1np<num+10np++)

if (*np>max)

max=*np

else if (*np<min)

min=*np

printf("max=%g\tmin=%g\n",max,min)

}

---