近似算法求解顶点覆盖问题c语言代码

以下是使用贪心算法求解顶点覆盖问题的C语言代码：

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

#define MAX_N 100

int graph[MAX_N][MAX_N]; // 邻接矩阵表示图
int cover[MAX_N]; // 顶点覆盖集合
int visited[MAX_N]; // 标记每个顶点是否已经被覆盖

int vertex_cover(int n)
{
    int i, j, max_deg, max_deg_idx;

    // 初始化顶点覆盖集合为空
    for (i = 0; i < n; i++) {
        cover[i] = 0;
    }

    // 迭代选择未被覆盖的边中所涉及的顶点数量最多的顶点
    while (1) {
        // 找出度数最大的未被覆盖的顶点
        max_deg = -1;
        for (i = 0; i < n; i++) {
            if (!visited[i]) {
                int deg = 0;
                for (j = 0; j < n; j++) {
                    if (graph[i][j] && !visited[j]) {
                        deg++;
                    }
                }
                if (deg > max_deg) {
                    max_deg = deg;
                    max_deg_idx = i;
                }
            }
        }

        // 如果没有未被覆盖的顶点，则退出循环
        if (max_deg == -1) {
            break;
        }

        // 将该顶点加入顶点覆盖集合中，并将与之相邻的边全部标记为已经覆盖
        cover[max_deg_idx] = 1;
        visited[max_deg_idx] = 1;
        for (j = 0; j < n; j++) {
            if (graph[max_deg_idx][j]) {
                visited[j] = 1;
            }
        }
    }

    // 返回顶点覆盖集合的大小
    int size = 0;
    for (i = 0; i < n; i++) {
        if (cover[i]) {
            size++;
        }
    }
    return size;
}

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

    // 读入图的边
    int i, j;
    for (i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u][v] = graph[v][u] = 1;
    }

    // 求解顶点覆盖问题
    int size = vertex_cover(n);
    printf("Minimum vertex cover: %d\n", size);

    return 0;
}

该代码通过邻接矩阵表示图，使用 visited 数组标记每个顶点是否已经被覆盖，使用 cover 数组表示当前顶点覆盖集合。迭代选择未被覆盖的边中所涉及的顶点数量最多的顶点，并将其加入到顶点覆盖集合中，并将与之相邻的边全部标记为已经覆盖。最后统计顶点覆盖集合的大小即可。