用c语言实现近似算法求解顶点覆盖问题

下面是一个使用 C 语言实现的近似算法求解顶点覆盖问题的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100     // 顶点数的最大值
#define MAXM 10000   // 边数的最大值

int n, m;
int head[MAXN+1], ver[MAXM+1], nxt[MAXM+1], tot = 0;

void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }

    int cover[MAXN+1] = {0};
    for (int i = 1; i <= n; i++) {
        int max_degree = 0, max_v = 0;
        for (int j = head[i]; j; j = nxt[j]) {
            int v = ver[j];
            if (!cover[v]) {  // 如果 v 还没有被覆盖
                int degree = 0;
                for (int k = head[v]; k; k = nxt[k]) {
                    if (!cover[ver[k]]) {
                        degree++;
                    }
                }
                if (degree > max_degree) {
                    max_degree = degree;
                    max_v = v;
                }
            }
        }
        if (max_v) {
            cover[max_v] = 1;  // 将 max_v 加入到顶点覆盖集合中
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (cover[i]) {
            cnt++;
        }
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++) {
        if (cover[i]) {
            printf("%d ", i);
        }
    }

    return 0;
}

在这个代码中，我们使用一个邻接表来存储图。对于每个顶点，我们遍历它的所有邻居，并且计算它们的度数（即与它相邻的未被覆盖的顶点个数）。然后选择度数最大的顶点加入到顶点覆盖集合中。最后，我们统计顶点覆盖集合中的顶点数，并输出这些顶点的编号。

需要注意的是，这个算法并不保证每个顶点都被覆盖到，因此得到的解可能并不是最优解。但是，它比较简单，容易实现，并且在实际应用中通常能够得到较好的结果。