Minimum spanning tree#981

Minimum spanning tree (Editorial)

The task is to find the weight of the minimum spanning tree using Kruskal's algorithm.

Example The graph given in the example has the following form:

Exercise 1

Find the minimum spanning tree and its weight for the following graph.

Exercise 2

Find the minimum spanning tree and its weight for the following graph.

Algorithm implementation

Declare a structure for the graph edge (a pair of vertices and the edge weight). Declare a vector of edges $e$ .

struct Edge
{
  int u, v, dist;
};

vector<Edge> e;

Declare an array $p a r e n t$ , that will be used in the disjoint-set data structure.

vector<int> parent;

The function Repr finds the representative of the set that contains vertex $n$ .

int Repr(int n)
{
  while (n != parent[n]) n = parent[n];
  return n;
}

The function Union unites the sets containing elements $x$ and $y$ .

int Union(int x, int y)
{
  x = Repr(x); y = Repr(y);
  if (x == y) return 0;
  parent[y] = x;
  return 1;
}

C++

The function lt is a comparator for sorting the edges.

int lt(Edge a, Edge b)
{
  return (a.dist < b.dist);
}

The main part of the program. Initialize the $p a r e n t$ array.

scanf("%d %d",&n,&m);
parent.resize(n + 1);
for (i = 1; i <= n; i++) parent[i] = i;

Read the edges of the graph.

e.resize(m);
for (i = 0; i < m; i++)
  scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);

Sort the edges of the graph in increasing order of weights.

sort(e.begin(), e.end(), lt);

Run Kruskal's algorithm to construct the minimum spanning tree.

res = 0;
for(i = 0; i < m; i++)
  if (Union(e[i].u,e[i].v)) res += e[i].dist;

Print the weight of the minimum spanning tree.

printf("%d\n",res);

Algorithm implementation — heuristics

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge
{
  int u, v, dist;
};

vector<Edge> e;
vector<int> parent, depth;
int i, n, m, res;

int Repr(int n)
{
  if (n == parent[n]) return n;
  return parent[n] = Repr(parent[n]);
}

int Union(int x, int y)
{
  x = Repr(x); y = Repr(y);
  if (x == y) return 0;
  if (depth[x] < depth[y]) swap(x, y);
  parent[y] = x;
  if (depth[x] == depth[y]) depth[x]++;
  return 1;
}

int lt(Edge a, Edge b)
{
  return a.dist < b.dist;
}

int main(void)
{
  scanf("%d %d", &n, &m);

  parent.resize(n + 1);
  depth.resize(n + 1);
  for (i = 1; i <= n; i++)
  {
    parent[i] = i;
    depth[i] = 0;
  }

  e.resize(m);
  for (i = 0; i < m; i++)
    scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);

  sort(e.begin(), e.end(), lt);

  res = 0;
  for (i = 0; i < m; i++)
    if (Union(e[i].u, e[i].v)) res += e[i].dist;

  printf("%d\n", res);
  return 0;
}

C++

Algorithm implementation — Prim

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define MAX 101
#define INF 0x3F3F3F3F
using namespace std;

int i, n, m, a, b, c, res;
vector<vector<pair<int, int> > > g; // (to, dist)
int used[MAX], dist[MAX];

int Prim(int start)
{
  memset(dist, 0x3F, sizeof(dist));
  memset(used, 0, sizeof(used));

  int cur = start, res = 0;
  dist[cur] = 0;
  used[cur] = 1;
  for (int i = 1; i < n; i++)
  {
    for (auto e : g[cur]) // cur -> to
    {
      int to = e.first;
      int d = e.second;
      if (!used[to] && (d < dist[to]))
        dist[to] = d;
    }

    int min = INF;
    for (int j = 1; j <= n; j++)
      if (!used[j] && (dist[j] < min))
      {
        min = dist[j];
        cur = j;
      }

    used[cur] = 1;
    res += dist[cur];
  }
  return res;
}

int main(void)
{
  scanf("%d %d", &n, &m);
  g.resize(n + 1);
  for (i = 0; i < m; i++)
  {
    scanf("%d %d %d", &a, &b, &c);
    g[a].push_back({ b, c });
    g[b].push_back({ a, c });
  }

  res = Prim(1);
  printf("%d\n", res);
  return 0;
}

C++

Java implementation

import java.util.*;

class Edge
{
  int u, v, dist;
  Edge (int u, int v, int dist)
  {
    this.u = u;
    this.v = v;
    this.dist = dist;
  }
};

public class Main
{
  static int mas[];
  static int size[];
	
  static int Repr(int n)
  {
    if (n == mas[n]) return n;
    return mas[n] = Repr(mas[n]);
  }
	
  static int Union(int x, int y)
  {
    x = Repr(x); y = Repr(y);
    if(x == y) return 0;

    if (size[x] < size[y])
    {
      int temp = x; x = y; y = temp;
    }
    mas[y] = x;
    size[x] += size[y];
    return 1;
  }
  
  public static class MyFun implements Comparator<Edge>
  {
    public int compare(Edge a, Edge b)
    {
      return a.dist - b.dist;
    }
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    mas = new int[n+1];
    size = new int[n+1];
    
    for(int i = 1; i <= n; i++)
    {
      mas[i] = i;
      size[i] = 1;
    }

    Vector<Edge> v = new Vector<Edge>();
    for(int i = 0; i < m; i++)
    {
      int x = con.nextInt();
      int y = con.nextInt();
      int dist = con.nextInt();
      v.add(new Edge(x, y, dist));
    }

    Collections.sort(v, new MyFun());
    
    int res = 0;
    for(int i = 0; i < m; i++)
      if (Union(v.get(i).u, v.get(i).v) == 1) res += v.get(i).dist;
    
    System.out.println(res);
    con.close();
  }
}

Java