有向生成树

一、定义

有向生成树是一个有向图的生成树，是指从一个有向图中选择一些边的子集，这些边构成一棵生成树，且生成树的根节点只有入度而无出度，除根节点外任意一个节点的入度都为1。该生成树一定包含图中所有的节点。

二、应用

有向生成树在很多算法中都有着重要的应用，例如有向图的最小树形图问题、有向无环图（DAG）的拓扑排序、网络最大流问题的求解等等。

三、求解方法

有向生成树的求解有两种常用的方法，分别是Kruskal算法和Prim算法。下面分别介绍这两种算法的实现过程。

四、Kruskal算法

Kruskal算法是一种基于贪心的算法，它的基本思想是从小到大按权值来选择边，且边不能构成环。以下是Kruskal算法的示例代码：

#include 

using namespace std;

const int maxn = 1005;
const int maxm = 100005;

int n, m, cnt;
int fa[maxn], head[maxn];
struct Edge {
    int from, to, w, nxt;
} e[maxm];

bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}

int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void add_edge(int from, int to, int w) {
    e[cnt].from = from;
    e[cnt].to = to;
    e[cnt].w = w;
    e[cnt].nxt = head[from];
    head[from] = cnt++;
}

void kruskal() {
    sort(e, e+m, cmp);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 0; i < m; i++) {
        int u = e[i].from, v = e[i].to, w = e[i].w;
        int pu = find(u), pv = find(v);
        if(pu == pv) continue;
        fa[pu] = pv;
        add_edge(u, v, w);
        add_edge(v, u, 0);
    }
}

五、Prim算法

Prim算法也是一种基于贪心的算法，它的基本思想是从一个点开始，每次选取一个未被选择的最小边权的点，并将其加入生成树中。以下是Prim算法的示例代码：

#include 

using namespace std;

const int maxn = 1005;
const int maxm = 100005;

int n, m, cnt, ans;
int head[maxn], dis[maxn];
bool vis[maxn];
struct Edge {
    int to, w, nxt;
} e[maxm];

void add_edge(int from, int to, int w) {
    e[cnt].to = to;
    e[cnt].w = w;
    e[cnt].nxt = head[from];
    head[from] = cnt++;
}

void prim(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<pair, vector<pair >, greater<pair > > q;
    q.push(make_pair(0, s));
    while(!q.empty()) {
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        ans += dis[x];
        for(int i = head[x]; i != -1; i = e[i].nxt) {
            int y = e[i].to, w = e[i].w;
            if(w < dis[y] && !vis[y]) {
                dis[y] = w;
                q.push(make_pair(dis[y], y));
            }
        }
    }
}

六、小结

有向生成树是图论中的重要问题，其应用广泛，求解方法也有多种。通过本文的介绍，读者可以了解到有向生成树的定义、应用、Kruskal算法和Prim算法的实现过程，从而更好地理解有向生成树这一问题。