Minimum Directed Spanning Tree

Definition

The Minimum Spanning Tree on a directed graph is called the Directed Minimum Spanning Tree (DMST).

A commonly used algorithm is the Chu–Liu/Edmonds algorithm (also known as Edmonds' algorithm), which can solve the DMST problem in \(O(nm)\) time.

Process

1. For each vertex, select the incoming edge with the smallest weight.
2. If no cycle exists, the algorithm terminates; otherwise, contract the cycle and update the distances from other vertices to the cycle.

Implementation

bool solve() {
  ans = 0;
  int u, v, root = 0;
  for (;;) {
    f(i, 0, n) in[i] = 1e100;
    f(i, 0, m) {
      u = e[i].s;
      v = e[i].t;
      if (u != v && e[i].w < in[v]) {
        in[v] = e[i].w;
        pre[v] = u;
      }
    }
    f(i, 0, m) if (i != root && in[i] > 1e50) return 0;
    int tn = 0;
    memset(id, -1, sizeof id);
    memset(vis, -1, sizeof vis);
    in[root] = 0;
    f(i, 0, n) {
      ans += in[i];
      v = i;
      while (vis[v] != i && id[v] == -1 && v != root) {
        vis[v] = i;
        v = pre[v];
      }
      if (v != root && id[v] == -1) {
        for (int u = pre[v]; u != v; u = pre[u]) id[u] = tn;
        id[v] = tn++;
      }
    }
    if (tn == 0) break;
    f(i, 0, n) if (id[i] == -1) id[i] = tn++;
    f(i, 0, m) {
      u = e[i].s;
      v = e[i].t;
      e[i].s = id[u];
      e[i].t = id[v];
      if (e[i].s != e[i].t) e[i].w -= in[v];
    }
    n = tn;
    root = id[root];
  }
  return ans;
}

Tarjan's DMST Algorithm

Tarjan proposed an algorithm that can solve the DMST problem in \(O(m+n\log n)\) time.

The algorithm description and reference code here are based on Professor Uri Zwick's lecture notes. More details can be found in the original text.

Process

Tarjan's algorithm consists of two phases: contraction and expansion. We first describe the contraction phase.

We assume the input graph is strongly connected. If not, add \(O(n)\) edges with infinite weight to make it strongly connected.

We need a heap to store information such as the index of incoming edges, their weights, and the total cost of vertices. Since heap merging operations will occur later, we implement it using Leftist Tree and Union-Find. In each step, the algorithm selects an arbitrary vertex \(v\), ensuring \(v\) is not the root and has no incoming edge in the heap. Then, add \(v\)'s minimum incoming edge to the heap. If this newly added edge forms a cycle in the heap, contract the vertices in the cycle into a super-vertex. Continue this process until all vertices are contracted into a single super-vertex, at which point the contraction phase ends. After contraction, a contraction tree is obtained, which will then be expanded.

The edges in the heap always form a path \(v_0\leftarrow v_1\leftarrow \dots\leftarrow v_k\). Since the graph is strongly connected, this path must exist, and each \(v_i\) may be an original vertex or a contracted super-vertex.

Initially, let \(v_0=a\), where \(a\) is an arbitrary vertex in the graph. Each time, select a minimum incoming edge \(v_k\leftarrow u\). If \(u\) is not among \(v_0,v_1,\dots,v_k\), extend the path to \(v_{k+1}=u\). If \(u\) is one of them, say \(v_i\), then a cycle \(v_i\leftarrow\dots\leftarrow v_k\leftarrow v_i\) is found. Contract these vertices into a super-vertex \(c\).

Place all vertices or super-vertices into a queue \(P\), and initially select an arbitrary vertex \(a\). While the queue is not empty, perform the following steps:

1. Select \(a\)'s minimum incoming edge, ensuring no self-loop, and find the other endpoint \(b\). If \(b\) has not been recorded, no cycle is formed. Set \(a\leftarrow b\) and continue searching for a cycle.
2. If \(b\) has been recorded, a cycle is detected. Increase the total vertex count, renumber all vertices in the cycle, merge heaps, and update the total weights of vertices/super-vertices. The weight update involves collecting all incoming edges on the cycle and subtracting the weight of the cycle's incoming edge.

As shown in the figure, the strongly connected graph on the left contracts into the contraction tree on the right. Here, \(a\) is the super-vertex formed by contracting vertices 1 and 2; \(b\) is the super-vertex formed by contracting vertices 3, 4, and 5; and \(A\) is formed by contracting super-vertices \(a\) and \(b\).

The expansion phase is relatively straightforward. Starting from the required root \(r\), expand every cycle on the path from \(r\) to the root of the contraction tree. Then, starting from \(r\)'s ancestor \(f_r\), expand the cycle from \(f_r\) to the root, until all vertices are processed.

Implementation

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

using ll = long long;
constexpr int MAXN = 102;
constexpr int INF = 0x3f3f3f3f;

struct UnionFind {
  int fa[MAXN << 1];

  UnionFind() { memset(fa, 0, sizeof(fa)); }

  void clear(int n) { memset(fa + 1, 0, sizeof(int) * n); }

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

  int operator[](int x) { return find(x); }
};

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

struct Heap {
  Edge *e;
  int rk, constant;
  Heap *lch, *rch;

  Heap(Edge *_e) : e(_e), rk(1), constant(0), lch(NULL), rch(NULL) {}

  void push() {
    if (lch) lch->constant += constant;
    if (rch) rch->constant += constant;
    e->w += constant;
    constant = 0;
  }
};

Heap *merge(Heap *x, Heap *y) {
  if (!x) return y;
  if (!y) return x;
  if (x->e->w + x->constant > y->e->w + y->constant) swap(x, y);
  x->push();
  x->rch = merge(x->rch, y);
  if (!x->lch || x->lch->rk < x->rch->rk) swap(x->lch, x->rch);
  if (x->rch)
    x->rk = x->rch->rk + 1;
  else
    x->rk = 1;
  return x;
}

Edge *extract(Heap *&x) {
  Edge *r = x->e;
  x->push();
  x = merge(x->lch, x->rch);
  return r;
}

vector<Edge> in[MAXN];
int n, m, fa[MAXN << 1], nxt[MAXN << 1];
Edge *ed[MAXN << 1];
Heap *Q[MAXN << 1];
UnionFind id;

void contract() {
  bool mark[MAXN << 1];
  // Record each vertex and its connected vertices on the graph.
  for (int i = 1; i <= n; i++) {
    queue<Heap *> q;
    for (int j = 0; j < in[i].size(); j++) q.push(new Heap(&in[i][j]));
    while (q.size() > 1) {
      Heap *u = q.front();
      q.pop();
      Heap *v = q.front();
      q.pop();
      q.push(merge(u, v));
    }
    Q[i] = q.front();
  }
  mark[1] = true;
  for (int a = 1, b = 1, p; Q[a]; b = a, mark[b] = true) {
    // Find the minimum incoming edge and its endpoint, ensuring no cycle.
    do {
      ed[a] = extract(Q[a]);
      a = id[ed[a]->u];
    } while (a == b && Q[a]);
    if (a == b) break;
    if (!mark[a]) continue;
    // Contract the discovered cycle, renumber vertices within the cycle, and update total weights.
    for (a = b, n++; a != n; a = p) {
      id.fa[a] = fa[a] = n;
      if (Q[a]) Q[a]->constant -= ed[a]->w;
      Q[n] = merge(Q[n], Q[a]);
      p = id[ed[a]->u];
      nxt[p == n ? b : p] = a;
    }
  }
}

ll expand(int x, int r);

ll expand_iter(int x) {
  ll r = 0;
  for (int u = nxt[x]; u != x; u = nxt[u]) {
    if (ed[u]->w0 >= INF)
      return INF;
    else
      r += expand(ed[u]->v, u) + ed[u]->w0;
  }
  return r;
}

ll expand(int x, int t) {
  ll r = 0;
  for (; x != t; x = fa[x]) {
    r += expand_iter(x);
    if (r >= INF) return INF;
  }
  return r;
}

void link(int u, int v, int w) { in[v].push_back({u, v, w, w}); }

int main() {
  int rt;
  scanf("%d %d %d", &n, &m, &rt);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    link(u, v, w);
  }
  // Ensure strong connectivity
  for (int i = 1; i <= n; i++) link(i > 1 ? i - 1 : n, i, INF);
  contract();
  ll ans = expand(rt, n);
  if (ans >= INF)
    puts("-1");
  else
    printf("%lld\n", ans);
  return 0;
}

References

Uri Zwick. (2013), Directed Minimum Spanning Trees, Lecture notes on "Analysis of Algorithms"

https://riteme.site/blog/2018-6-18/mdst.html#_3

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用