经典ACM算法合集经典ACM算法合集(14)

经典ACM算法合集经典ACM算法合集

，
要计算最小权顶点覆盖的顶点权之和，可用回溯法搜索子集树的算法进行求解。

3、算法设计：
a. 给定的图G 有n 个顶点和m条边，用w[i]存储顶点i的权值，用e[i][j]标记两顶
点为i和j的边是否存在，用c[i]标记顶点i是否在顶点覆盖集中；
b. 用函数cover()判断图G 是否被顶点覆盖（用t标记）：
① 初始t=0；
② 采用while循环对每个顶点i（1≤i≤n）进行讨论：
1> 若顶点i不在顶点覆盖集中（即c[i]==0），则查找与之有边连接的顶点j（即e[i][j]==1），判断所有顶点j：
若存在顶点j在顶点覆盖集中（即c[j]==0），则t=1；
若所有顶点j都不在顶点覆盖集中（即t==0），则图G 未被顶点
覆盖（return 0）；

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(14)全文阅读和word下载服务。