Мінімальний каркас#981

Мінімальний каркас (Розбір)

У задачі необхідно знайти вагу мінімального остовного дерева за допомогою алгоритму Крускала.

Приклад Граф, наведений у прикладі, має такий вигляд:

Вправа 1

Знайдіть мінімальний остов і його вагу для наступного графа.

Вправа 2

Знайдіть мінімальний остов і його вагу для наступного графа.

Реалізація алгоритму

Оголосимо структуру для ребра графа (пара вершин і вага ребра). Оголосимо вектор ребер $e$ .

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

vector<Edge> e;

Оголосимо масив $p a r e n t$ , який буде використовуватися в системі непересічних множин.

vector<int> parent;

Функція Repr знаходить представника множини, в якій знаходиться вершина $n$ .

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

Функція Union об'єднує множини, що містять елементи $x$ і $y$ .

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

C++

Функція lt є компаратором для сортування ребер.

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

Основна частина програми. Ініціалізуємо масив $p a r e n t$ .

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

Читаємо ребра графа.

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);

Реалізація алгоритму — евристика

#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++

Реалізація алгоритму — Прим

#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 реалізація

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