近似算法求斯坦纳树，C语言实现

斯坦纳树问题是一个NP难问题，没有多项式时间算法可以完全解决。因此，我们通常使用近似算法来解决这个问题。

下面是一个简单的近似算法，以C语言实现。

首先，我们需要用动态规划算法计算出所有的子集的最小生成树，然后对于每个子集，选择它的最小生成树，并将它们合并成一个整体的最小生成树。

算法的核心代码如下：

#include <stdio.h>
#include <limits.h>

#define MAXN 100
#define MAXM 10000

typedef struct {
    int u, v, w;
} Edge;

int n, m;
Edge edges[MAXM];
int dp[1 << MAXN][MAXN];
int parent[1 << MAXN][MAXN];

int min(int a, int b) {
    return a < b ? a : b;
}

int readGraph() {
    if (scanf("%d%d", &n, &m) != 2) {
        return 0;
    }

    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    return 1;
}

int cmp(const void *a, const void *b) {
    return ((Edge *) a)->w - ((Edge *) b)->w;
}

void sortEdges() {
    qsort(edges, m, sizeof(Edge), cmp);
}

void initialize() {
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = INT_MAX;
        }
    }

    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = 0;
    }
}

void computeDP() {
    for (int s = 0; s < (1 << n); ++s) {
        for (int i = 0; i < n; ++i) {
            if ((s & (1 << i)) == 0) {
                continue;
            }

            for (int j = 0; j < m; ++j) {
                int u = edges[j].u;
                int v = edges[j].v;

                if ((s & (1 << u)) && (s & (1 << v))) {
                    int t = s ^ (1 << i);
                    int w = dp[t][u] + dp[t][v] + edges[j].w;

                    if (w < dp[s][i]) {
                        dp[s][i] = w;
                        parent[s][i] = j;
                    }
                }
            }
        }
    }
}

void printSteinerTree() {
    int s = (1 << n) - 1;
    int root = 0;

    for (int i = 1; i < n; ++i) {
        if (dp[s][i] < dp[s][root]) {
            root = i;
        }
    }

    printf("Minimum Steiner Tree Cost = %d\n", dp[s][root]);

    while (s) {
        int j = parent[s][root];
        int t = s ^ (1 << root);

        if (dp[s][root] == dp[t][edges[j].u] + dp[t][edges[j].v] + edges[j].w) {
            s = t;
            printf("(%d,%d) ", edges[j].u, edges[j].v);
            root = edges[j].u;
        } else {
            j = edges[j].v;
            s &= ~(1 << root);
            root = j;
        }
    }

    printf("\n");
}

int main() {
    if (!readGraph()) {
        return 1;
    }

    sortEdges();
    initialize();
    computeDP();
    printSteinerTree();

    return 0;
}

该算法的时间复杂度为$O(3^n * n^2 + m * 2^n)$，其中$m$是边的数量。