有向生成樹

一、定義

有向生成樹是一個有向圖的生成樹，是指從一個有向圖中選擇一些邊的子集，這些邊構成一棵生成樹，且生成樹的根節點只有入度而無出度，除根節點外任意一個節點的入度都為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算法的實現過程，從而更好地理解有向生成樹這一問題。