Grafos II

tags: conteudo ps2020 grafo dijkstra MST DSU

Dijkstra

• Algorítmo guloso
• Cálculo de menor distância partindo de 1 nó

 [{1, 1}, {3, 2}, {4, 10}]
  
  1 -> dist = 1
  
 [{3, 2}, {2, 5}, {4, 10}]
 
  3 -> dist = 2
  
  adicionar -> {2, 5}, {4, 9}
  
  [{2, 5}, {2, 5}, {4, 9}, {4, 10}]
  

const int INF = 0x3f3f3f3f;
vector<pii> adj;
priority_queue<pair<int, int>> pq;
int dist[N];

int main() {
  
  memset(dist, 0x3f, sizeof(dist));
  
  pq.push({0, 1});
  
  while(!pq.empty()) {
    int u = pq.top().nd, -d = pq.top().st;
    pq.pop();
    
    if(dist[u] != INF) continue;
    
    dist[u] = d;
    for(auto p: adj[u]) {
      int v = p.st, w = p.nd;
      pq.push({-(w + d), v});
    }
  }
}

DSU (Union find)

par[0] = 0
par[1] = 1
par[2] = 1
par[3] = 3
par[9] = 3
par[4] = 3
par[8] = 4

find(8):
  find(4):
    find(3):
      return 3
    par[4] = 3
    return 3
  par[8] = 3
  return 3

int par[N], sz[N];

int find(int a) {
  if(par[a] == a) return a;
  return par[a] = find(par[a]);
}

void unite(int a, int b) {
  a = find(a);
  b = find(b);
  if(a == b) return;
  
  if(sz[a] < sz[b]) swap(a, b);
  
  par[b] = a;
  sz[a] += sz[b];
}

int main() {
  for(int i = 0; i < n; i++) par[i] = i, sz[i] = 1;
}

Complexidade: O(alpha(n))

MST (Minimum Spanning Tree)

Kruskal

 5 -> C - E
 6 -> D - F
 7 -> A - B
 7 -> B - E
 
 8 -> B - C -> não conecta

int n, m;
priority_queue<pair<int, pii>> pq;

int sum;

int main{
  for(int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    pq.push({-c, {a, b}});
  

  
  while(!pq.empty()) {
    int c = -pq.top().first,
        b = pq.top().nd.st,
        a = pq.top().nd.nd;
        
    pq.pop();
    
    if(find(a) == find(b)) continue;
    //adj[a].pb(b);
    //adj[b].pb(a);
    
    sum += c;
    
    int pa = find(a);
    int pb = find(b);
    
    unite(pa, pb);
   
 

Prim

const int INF = 0x3f3f3f3f;
vector<pii> adj;
priority_queue<pair<int, pii>> pq;
int dist[N];

int pa[N];

int main() {
  
  memset(dist, 0x3f, sizeof(dist));
  
  pq.push({0, 1});
  pa[0] = 0;
  
  while(!pq.empty()) {
    int c = -pq.top().first,
        a = pq.top().nd.st,
        b = pq.top().nd.nd;
    pq.pop();
    
    if(pa[a] != a) continue;
    pa[a] = b;
    
    for(auto p: adj[a]) {
      int v = p.st, w = p.nd;
      pq.push({-(w), {v, a});
      int v = p.st, w = p.nd;
    }
  }
}