Skip to content

Maximum Weight General Graph Matching

This page covers from maximum weight perfect matching in general graphs to maximum weight matching in general graphs (maximum weight matching can be transformed into maximum weight perfect matching by adding zero-weight edges).

Prerequisites

Blossom

The difference between matching in general graphs and bipartite graphs is that general graphs may contain odd cycles. Even cycles can be treated as bipartite graphs.

The Blossom Algorithm handles odd cycles by contracting them into a blossom and setting all vertices in the blossom as even vertices. Since all vertices in the blossom can become even vertices, the entire blossom can be contracted into a single even vertex. Note that a blossom may contain other blossoms.

This can also be transformed into a linear programming and dual problem, but some processing of blossoms is required.

Vertex Labeling and Equality Edge

Define \(z_u\) as the vertex labeling of vertex \(u\), with the same meaning as in the KM algorithm. Define an edge \(e(u,v)\) as an "equality edge" if and only if the sum of the labels of vertices \(u\) and \(v\) equals the weight of edge \(e\) (\(z_u + z_v = w(e)\)). In this case, the edge label \(z_e = z_u + z_v − w(e) = 0\).

Linear Programming for Maximum Weight Perfect Matching in General Graphs

Definitions

Since a blossom has at least three vertices, it contracts into a single point. Let \(O\) be the set of all odd-sized sets (including all blossoms) with size \(\geq 3\), and \(\gamma(S)\) denote the edges within set \(S\).

\[ \begin{aligned} & \text{Let } S\subseteq V \\ & \gamma(S)=\{(u,v)\in E:u\in S,v\in S\} \\ & O=\{B\subseteq V:|B|\text{ is odd and }|B|\geq3\} \\ \end{aligned} \]

Dual Problem

Primal Problem
\[ \begin{aligned} & \max\sum_{e\in E}w(e)x_e \\ & \text{Constraints:} \\ & x(\delta(u))=1:\forall u\in V \\ & x(\gamma(B))\leq\lfloor\frac{|B|}{2}\rfloor:\forall B\in O \\ & x_e\geq0:\forall e\in E \\ \end{aligned} \]

Then, the problem is transformed into the dual problem via Primal-Dual.

Dual Problem
\[ \begin{aligned} & \min\sum_{u\in V}z_u+\sum_{B\in O}\left\lfloor\frac{|B|}{2}\right\rfloor z_B \\ & \text{Constraints:} \\ & z_B\geq0:\forall B\in O \\ & z_e\geq0:\forall e\in E \\ & \text{Let } e=(u,v), \text{ here} \\ & \begin{array}{lll} z_e & = & z_u + z_v - w(e) + \sum_{\substack{B \in O \\ u,v \in \gamma(B)}} z_B \end{array} \end{aligned} \]

Edges with \(x_e=1\) are matching edges, and edges with \(x_e=0\) are non-matching edges. As in bipartite graphs, we must satisfy \(x_e\in\{0,1\}:\forall e\in E\). Therefore, in maximum weight perfect matching, all matching edges must be equality edges.

Unlike bipartite graphs, general graphs have the additional \(z_B\) to handle. Below, we consider when \(z_B > 0\).

It can be seen that it is best to keep \(z_B=0\) whenever possible, but sometimes \(z_B>0\) is necessary. \(z_B>0\) is meaningful only when \(x(\gamma(B)) = \left\lfloor \dfrac{|B|}2 \right\rfloor \text{and} x(\delta(B)) = 1\). In other cases, \(z_B>0\) is meaningless.

According to complementary slackness, we have the following correspondences:

  • For selected edges \(e\), we must have \(z_e=0\).

    \[ x_e>0 \longrightarrow z_e=0,\quad \forall e\in E \]

  • For selected sets \(B\), \(z_B>0 \longrightarrow x(\gamma(B))= \left\lfloor \dfrac{|B|}2 \right\rfloor\), i.e., all sets \(B\) with \(z_B>0\) have exactly half of their edges selected, meaning \(B\) is a blossom, and an edge within the blossom is selected for augmentation. Additionally, we add a condition: \(x(\delta(B))=1\), i.e., \(z_B>0\) is meaningful only when blossom \(B\) has exactly one outgoing edge.

    \[ z_B>0 \longrightarrow x(\gamma(B))=\left\lfloor\frac{|B|}2\right\rfloor, x(\delta(B))=1\quad \forall B\in O \]

Using the concept of equality edges, combined with the previous Blossom Algorithm: augmenting paths composed of "equality edges" are continuously expanded. Since all edges used for expansion are "equality edges," the resulting maximum weight perfect matching will still consist entirely of "equality edges."

Handling Blossoms

When a blossom is encountered, it is contracted into an even vertex. All vertices in the blossom are set as even vertices, and its \(z_B\) is set to \(0\).

Since blossoms are stored after contraction and are only expanded under certain conditions, they cannot be recorded using previous methods.

Unless otherwise specified, all mentioned vertices include even vertices formed by contracted blossoms.

Since blossoms may also be contracted into points and added to the queue, and the number of blossoms is not fixed, we cannot enumerate each point to check for augmenting paths as before. Therefore, during Breadth-First Search (BFS), all unmatched vertices must be placed in the queue.

This will generate multiple alternating trees simultaneously.

The Four Steps of the Algorithm

This algorithm can be divided into four steps.

  1. GROW (Equality Edge): Form alternating trees using "equality edges."
  2. AUGMENT (Augment): Find augmenting paths and expand the matching.
  3. SHRINK (Shrink): Contract a blossom into a single point.
  4. EXPAND (Expand): Expand a blossom.

general-weight-match-1

During the AUGMENT phase, since all unmatched vertices are in different alternating trees, when an even vertex from one alternating tree connects to an even vertex from another, it indicates an augmenting path has been found.

No Equality Edge for Expansion

As in bipartite graphs, there may be situations where no "equality edge" can be found for expansion. In such cases, vertex labeling needs to be adjusted.

Adjusting VERTEX LABELING

Vertex labeling must still maintain the greater-than-or-equal property, existing "equality edges" must not be changed, and \(z_B\) should be minimized as much as possible.

Definition of Odd/Even Vertices

Let \(u^−\) denote that \(u\) is an odd vertex in the alternating tree.
Let \(u^+\) denote that \(u\) is an even vertex in the alternating tree.
Let \(u^\varnothing\) denote that \(u\) is not in any alternating tree.
All subsequent mentions of \(B\) assume it is a blossom and also represent the contracted point.
Blossoms can also be odd or even, so symbols like \(B^+\), \(B^−\), \(B^\varnothing\) are also applicable.

Suppose there are currently r alternating trees \(T_i=(U_{t_i},V_{t_i}):1\leq i\leq r\), and let

\[ \begin{aligned} d1 &= \min(\{z_e : e = (u^+,v^\varnothing)\}) \\ d2 &= \min(\{z_e : e = (u^+,v^+), ~ u^+ \in T_i, ~ v^+ \in T_j, ~ i \neq j\}) / 2 \\ d3 &= \min(\{z_{B^-} : B^- \in O\}) / 2 \end{aligned} \]

Note that here \(B\) is a contracted point, so it can have odd/even parity.

Let \(d=min(d1,d2,d3)\), and adjust:

\[ \begin{aligned} z_{u^+} - &= d \\ z_{v^-} + &= d \\ z_{B^+} + &= 2d \\ z_{B^-} - &= 2d \\ \end{aligned} \]

If \(z_B=0\) (i.e., \(d=d3\)), to prevent \(z_B<0\), the blossom must be expanded (EXPAND). After expansion, only the alternating path within the blossom is retained, and vertices in the blossom not on the alternating path are set as unvisited (\(\varnothing\)).

This creates one (or more) equality edges, keeps existing equality edges unchanged, maintains the property \(z_e\geq0:\forall e\in E\), minimally increases \(z_B\), and allows the search for augmenting paths to continue.

Maximum Weight Matching in General Graphs

The above solves maximum weight perfect matching. To solve maximum weight matching, an additional constraint must be added to vertex labeling: for all matched vertices \(u\), \(z_u>0\).

Initially, set all \(z_u=max(\{w(e):e\in E\})/2\).

Vertices with vertex labeling \(0\) will eventually become unmatched vertices.

Reference Code

For ease of implementation, edge weights are multiplied by \(2\) to compute \(z_e\), avoiding floating-point errors.

Storage 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
constexpr int INF = INT_MAX;
constexpr int MAXN = 400;

struct edge {
  int u, v, w;

  // Represents an edge (u,v) with weight w
  edge() {}

  edge(int u, int v, int w) : u(u), v(v), w(w) {}
};

int n, n_x;
// There are n vertices, numbered 1 ~ n
// n_x represents the current number of vertices plus blossoms, numbered from n+1 to n_x as blossom nodes
edge g[MAXN * 2 + 1][MAXN * 2 + 1];
// The graph is stored as an adjacency matrix. Since there are at most n-1 blossoms, the size is MAXN*
vector<int> flower[MAXN * 2 + 1];
// flower[b] records which vertices are in blossom b
// We record vertices in a blossom by only recording the outermost blossom

Below is an example of nested blossoms.

general-weight-match-2

Where \(\{ 6, 5, 8\} \in b1,\{ b1, 4, 3, 2, 11, 10, 9\} \in b2\). Stored as:

1
2
flower[b2] = {b1, 4, 3, 2, 11, 10, 9} 
flower[b1] = {6, 5, 8}

general-weight-match-3

1
2
flower[b2] = {9, b1, 4, 3, 2, 11, 10} 
flower[b1] = {5, 8, 6}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int lab[MAXN * 2 + 1];
// lab[u] records z_u, lab[b] records z_B
int match[MAXN * 2 + 1], slack[MAXN * 2 + 1], st[MAXN * 2 + 1],
    pa[MAXN * 2 + 1];
// match[x]=y indicates (x,y) is a matching edge, where x and y may be blossoms
// slack[x]=u indicates z(x,u) is the smallest edge among all edges adjacent to x
// Indicates the blossom containing node x is b. If x=b and b<=n, then x
// is an ordinary node (not part of any blossom) Indicates in the alternating tree, the parent node of v is u
int flower_from[MAXN * 2 + 1][MAXN + 1], S[MAXN * 2 + 1], vis[MAXN * 2 + 1];
/*
flower_from[b][x]=xs indicates the largest sub-blossom of b containing x is xs
x is a point in b, xs is a blossom or a point in b, and x=xs or x is one of the points in xs
*/
// S[u]={-1:unvisited 0:even vertex 1:odd vertex}
// vis is only used during LCA search to check if a node has been visited
queue<int> q;
// Queue used for BFS to find augmenting paths

general-weight-match-4

1
2
3
4
5
flower_from[b2][6] = b1 
flower_from[b2][5] = b1 
flower_from[b2][9] = 9 
flower_from[b1][6] = 6 
And so on...


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int e_delta(const edge &e) {
  // Compute ze. For convenience, all edge weights are multiplied by two.
  // Directly computing e_delta inside a blossom may cause errors.
  return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;
}

void update_slack(int u, int x) {
  // Update slack[x] using u
  if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) {
    slack[x] = u;
  }
}

void set_slack(int x) {
  // Compute slack[x]. slack[x]=0 indicates x is a node in the alternating tree.
  slack[x] = 0;
  for (int u = 1; u <= n; ++u) {
    if (g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) {
      update_slack(u, x);
    }
  }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void q_push(int x) {
  // Push x into the queue. We assume the queue cannot directly push a blossom.
  if (x <= n)
    q.push(x);
  else {
    // To push a blossom, all original vertices in the blossom must be added to the queue.
    for (size_t i = 0; i < flower[x].size(); i++) {
      q_push(flower[x][i]);
    }
  }
}

void set_st(int x, int b) {
  // Set the blossom containing x to b
  st[x] = b;
  if (x > n) {
    // If x is also a blossom, all vertices inside x must have their containing blossom set to b.
    for (size_t i = 0; i < flower[x].size(); ++i) {
      set_st(flower[x][i], b);
    }
  }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int get_pr(int b, int xr) {
  // xr is a point in flower[b]. The return value pr is its position.
  // For convenience, we ensure flower[b][0]~flower[b][pr] is the alternating path in the blossom.
  int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin();
  if (pr % 2 == 1) {
    // Check its position in the blossom. If flower[b][0]~flower[b][pr] is not an alternating path,
    // reverse the entire blossom and recompute pr.
    // Ensure flower[b][0]~flower[b][pr] is the alternating path in the blossom.
    reverse(flower[b].begin() + 1, flower[b].end());
    return (int)flower[b].size() - pr;
  } else
    return pr;
}

general-weight-match-5

If get_pr(b2,11) is used, flower[b2] becomes {9,10,11,2,3,4,b1}, and returns 2.

If get_pr(b2,2) is used, flower[b2] becomes {9,b1,4,3,2,11,10}, and returns 4.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void set_match(int u, int v) {
  // Set u and v as a matching edge. u and v may be blossoms.
  match[u] = g[u][v].v;
  if (u > n) {
    // If u is a blossom
    edge e = g[u][v];
    int xr = flower_from[u][e.u];  // Find which sub-blossom in flower[u] contains e.u
    int pr = get_pr(u, xr);  // Find the position of xr and ensure 0~pr is the alternating path in the blossom
    for (int i = 0; i < pr; ++i) {  // Flip matching and non-matching edges along the alternating path in the blossom
      set_match(flower[u][i], flower[u][i ^ 1]);
    }
    set_match(xr, v);  // Set (xr,v) as a matching edge
    rotate(flower[u].begin(), flower[u].begin() + pr, flower[u].end());
    // Finally, set pr as the base of the blossom. Since the blossom is stored with flower[u][0] as the base,
    // rotate flower[u][pr] to the front.
  }
}

void augment(int u, int v) {
  // Augment u and all its ancestors, and set (u,v) as a matching edge.
  for (;;) {
    int xnv = st[match[u]];
    set_match(u, v);
    if (!xnv) return;
    set_match(xnv, st[pa[xnv]]);
    u = st[pa[xnv]];
    v = xnv;
  }
}

int get_lca(int u, int v) {
  // Find the LCA of u and v in the alternating tree.
  static int t = 0;
  for (++t; u || v; swap(u, v)) {
    if (u == 0) continue;
    if (vis[u] == t) return u;
    vis[u] = t;  // This method avoids clearing the vis array.
    u = st[match[u]];
    if (u) u = st[pa[u]];
  }
  return 0;
}

Add an Odd Blossom 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void add_blossom(int u, int lca, int v) {
  // Contract the blossom formed by u, v, and lca into a single point b.
  // The LCA of u and v in the alternating tree becomes the base of the blossom.
  int b = n + 1;
  while (b <= n_x && st[b]) ++b;
  if (b > n_x) ++n_x;
  // Find the currently unused blossom ID.
  lab[b] = 0;             // Set zB=0
  S[b] = 0;               // The entire blossom is an even vertex.
  match[b] = match[lca];  // Set the matching edge of the blossom to the matching edge of the base.
  flower[b].clear();
  flower[b].push_back(lca);
  for (int x = u, y; x != lca; x = st[pa[y]]) {
    flower[b].push_back(x);
    y = st[match[x]];
    flower[b].push_back(y);
    q_push(y);
  }
  reverse(flower[b].begin() + 1, flower[b].end());
  for (int x = v, y; x != lca; x = st[pa[y]]) {
    flower[b].push_back(x);
    y = st[match[x]];
    flower[b].push_back(y);
    q_push(y);
  }
  // All points in b are added to flower[b] in a circular manner, with the base as the first element.
  set_st(b, b);  // Set the containing blossom of all elements in the blossom to b.
  for (int x = 1; x <= n_x; ++x) {
    g[b][x].w = 0;
    g[x][b].w = 0;
  }
  for (int x = 1; x <= n; ++x) {
    flower_from[b][x] = 0;
  }
  for (size_t i = 0; i < flower[b].size(); ++i) {
    int xs = flower[b][i];
    for (int x = 1; x <= n_x; ++x) {
      // Set the edge between b and x as the edge with the smallest e_delta among all edges adjacent to xs.
      if (g[b][x].w == 0 || e_delta(g[xs][x]) < e_delta(g[b][x])) {
        g[b][x] = g[xs][x];
        g[x][b] = g[x][xs];
      }
    }
    for (int x = 1; x <= n; ++x) {
      if (flower_from[xs][x]) {
        // If point xs in b contains x,
        // then flower_from[b][x] will be xs.
        flower_from[b][x] = xs;
      }
    }
  }
  set_slack(b);
  // Finally, the slack value for b must be set.
}
Expand Blossom 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void expand_blossom(int b) {
  // When b is an odd blossom and zB=0, it must be expanded.
  // Since only b is expanded, if b contains other blossoms,
  // they do not need to be expanded.
  for (size_t i = 0; i < flower[b].size(); ++i) {
    set_st(flower[b][i], flower[b][i]);
    // First, set the containing blossom of each element in flower[b] to itself.
  }
  int xr = flower_from[b][g[b][pa[b]].u];
  // xr indicates which sub-blossom in flower[b] contains the parent node of b in the alternating tree.
  int pr = get_pr(b, xr);  // Find the position of xr and ensure 0~pr is the alternating path in the blossom.
  for (int i = 0; i < pr; i += 2) {
    // Expand the alternating path into the alternating tree.
    // Add even vertices in the alternating path to the queue.
    int xs = flower[b][i];
    int xns = flower[b][i + 1];
    pa[xs] = g[xns][xs].u;
    S[xs] = 1;
    S[xns] = 0;
    slack[xs] = 0;
    set_slack(xns);
    q_push(xns);
  }
  S[xr] = 1;  // At this point, xr will be an odd vertex or odd blossom.
  pa[xr] = pa[b];
  for (size_t i = pr + 1; i < flower[b].size(); ++i) {
    // Set all vertices in the blossom not on the alternating path as unvisited.
    int xs = flower[b][i];
    S[xs] = -1;
    set_slack(xs);
  }
  st[b] = 0;
}
Try to Augment an Equality Edge 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool on_found_edge(const edge &e) {
  // When an equality edge e is found during BFS,
  // the following processing must be performed.
  // Here u must be an even vertex.
  int u = st[e.u], v = st[e.v];
  if (S[v] == -1) {
    // v is an unvisited vertex.
    pa[v] = e.u;
    S[v] = 1;
    int nu = st[match[v]];
    slack[v] = 0;
    slack[nu] = 0;
    S[nu] = 0;
    q_push(nu);
  } else if (S[v] == 0) {
    // v is an even vertex.
    int lca = get_lca(u, v);
    if (!lca) {  // lca=0 indicates u and v are in different alternating trees, an augmenting path exists.
      augment(u, v);
      augment(v, u);
      return true;  // Augmenting path found.
    } else
      add_blossom(u, lca, v);
    // Otherwise, u and v are in the same tree and form a blossom, which must be contracted.
  }
  return false;
}
Augmentation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
bool matching() {
  memset(S + 1, -1, sizeof(int) * n_x);
  memset(slack + 1, 0, sizeof(int) * n_x);
  q = queue<int>();  // Clear the queue.
  for (int x = 1; x <= n_x; ++x) {
    if (st[x] == x && !match[x]) {
      // Add all unmatched vertices to the queue and set them as even vertices.
      pa[x] = 0;
      S[x] = 0;
      q_push(x);
    }
  }
  if (q.empty()) return false;  // All vertices are matched.
  for (;;) {
    while (q.size()) {
      // BFS
      int u = q.front();
      q.pop();
      if (S[st[u]] == 1) continue;
      for (int v = 1; v <= n; ++v) {
        if (g[u][v].w > 0 && st[u] != st[v]) {
          if (e_delta(g[u][v]) == 0) {
            if (on_found_edge(g[u][v])) return true;
          } else
            update_slack(u, st[v]);
        }
      }
    }
    // Adjust lab values.
    int d = INF;
    for (int u = 1; u <= n; ++u) {
      // This prevents lab<0.
      // If any lab[u]=0, terminate.
      if (S[st[u]] == 0) d = min(d, lab[u]);
    }
    for (int b = n + 1; b <= n_x; ++b) {
      if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
    }
    for (int x = 1; x <= n_x; ++x)
      if (st[x] == x && slack[x]) {
        if (S[x] == -1)
          d = min(d, e_delta(g[slack[x]][x]));
        else if (S[x] == 0)
          d = min(d, e_delta(g[slack[x]][x]) / 2);
      }
    for (int u = 1; u <= n; ++u) {
      if (S[st[u]] == 0) {
        if (lab[u] == d) return false;
        // If lab[u]=0, terminate immediately.
        lab[u] -= d;
      } else if (S[st[u]] == 1)
        lab[u] += d;
    }
    for (int b = n + 1; b <= n_x; ++b) {
      if (st[b] == b) {
        if (S[st[b]] == 0)
          lab[b] += d * 2;
        else if (S[st[b]] == 1)
          lab[b] -= d * 2;
      }
    }
    q = queue<int>();  // Clear the queue.
    for (int x = 1; x <= n_x; ++x) {
      // Check if any augmenting paths have been created.
      if (st[x] == x && slack[x] && st[slack[x]] != x &&
          e_delta(g[slack[x]][x]) == 0)
        if (on_found_edge(g[slack[x]][x])) return true;
    }
    for (int b = n + 1; b <= n_x; ++b) {
      // EXPAND operation: expand all odd blossoms with lab[b]=0.
      if (st[b] == b && S[b] == 1 && lab[b] == 0) expand_blossom(b);
    }
  }
  return false;
}
Main Function 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pair<long long, int> weight_blossom() {
  // Main function. Initialize first.
  memset(match + 1, 0, sizeof(int) * n);
  n_x = n;  // Initially, there are no blossoms.
  int n_matches = 0;
  long long tot_weight = 0;
  for (int u = 0; u <= n; ++u) {
    // First, set the containing blossom of each vertex to itself.
    st[u] = u;
    flower[u].clear();
  }
  int w_max = 0;
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v) {
      // When u is a point, the only point it contains is itself.
      flower_from[u][v] = (u == v ? u : 0);
      w_max = max(w_max, g[u][v].w);
      // Find the maximum edge weight.
    }
  for (int u = 1; u <= n; ++u) lab[u] = w_max;
  // Set all lab to the maximum edge weight.
  // Since edge weights are multiplied by two to compute ze, no division by two is needed.
  while (matching()) ++n_matches;
  for (int u = 1; u <= n; ++u)
    if (match[u] && match[u] < u) tot_weight += g[u][match[u]].w;
  return make_pair(tot_weight, n_matches);
}
Initialization

Very important. Must be initialized before use.

1
2
3
4
5
6
void init_weight_graph() {
  // Must initialize before inputting edges into the graph.
  // Since it's maximum weight matching, non-existent edges are set to 0.
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v) g[u][v] = edge(u, v, 0);
}

Complexity Analysis

Each blossom is contracted or expanded at most once per BFS. Each contraction or expansion takes \(O(|V|)\) time. There are at most \(O(|V|)\) blossoms, so blossom processing takes \(O(|V|^2)\) time. BFS takes \(O(|V| + |E|)\) time. Therefore, finding an augmenting path takes \(O(|V| + |E|) + O(|V|^2) = O(|V|^2)\) time.

At most \(|V|\) BFS operations are performed. Thus, the total time complexity is \(O(|V|^3)\).

Exercises

References

  1. Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm"
  2. From Hungarian Algorithm to Weighted Blossom Algorithm—Detailed Explanation of Dual Problems in Graph Matching
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用