Implementações de Algoritmos de Grafos em C++

Este artigo apresenta diferentes implementações de algoritmos de grafos, incluindo Djikstra, SPFA, Floyd-Warshall e Kruskal. As soluções estão em C++ e exploram diversas técnicas de programação competitiva.

Algoritmo de Dijkstra com Fila de Prioridade


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll distancia[MAXN], aresta[MAXN], proximo[MAXN], peso[MAXN], cabeca[MAXN], idx;
bool visitado[MAXN];
typedef pair<ll, ll> par;

void adiciona_aresta(int origem, int destino, ll custo) {
    aresta[idx] = destino;
    proximo[idx] = cabeca[origem];
    peso[idx] = custo;
    cabeca[origem] = idx++;
}

void dijkstra(int inicio) {
    memset(distancia, 0x3f, sizeof distancia);
    distancia[inicio] = 0;
    priority_queue<par, vector<par>, greater<par>> fila;
    fila.push({0, inicio});
    while (!fila.empty()) {
        auto [custo, no] = fila.top(); fila.pop();
        if (visitado[no]) continue;
        visitado[no] = true;
        for (int i = cabeca[no]; i != -1; i = proximo[i]) {
            int vizinho = aresta[i];
            if (distancia[vizinho] > custo + peso[i]) {
                distancia[vizinho] = custo + peso[i];
                fila.push({distancia[vizinho], vizinho});
            }
        }
    }
}

int main() {
    int n, m, inicio;
    cin >> n >> m >> inicio;
    memset(cabeca, -1, sizeof cabeca);
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        adiciona_aresta(a, b, c);
    }
    dijkstra(inicio);
    for (int i = 1; i <= n; i++) cout << distancia[i] << ' ';
    return 0;
}

Detecção de Ciclo Negativo com SPFA


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e4+10;
struct Aresta { int destino; ll custo; };
vector<Aresta> grafo[MAXN];
ll dist[MAXN];
int cont[MAXN];
bool na_fila[MAXN];

bool spfa(int vertices) {
    memset(dist, 0x3f, sizeof dist);
    memset(cont, 0, sizeof cont);
    memset(na_fila, false, sizeof na_fila);
    queue<int> fila;
    fila.push(1); dist[1] = 0; na_fila[1] = true; cont[1] = 0;
    while (!fila.empty()) {
        int no = fila.front(); fila.pop();
        na_fila[no] = false;
        for (auto &aresta : grafo[no]) {
            if (dist[aresta.destino] > dist[no] + aresta.custo) {
                dist[aresta.destino] = dist[no] + aresta.custo;
                cont[aresta.destino] = cont[no] + 1;
                if (cont[aresta.destino] >= vertices) return true;
                if (!na_fila[aresta.destino]) {
                    na_fila[aresta.destino] = true;
                    fila.push(aresta.destino);
                }
            }
        }
    }
    return false;
}

int main() {
    int testes;
    cin >> testes;
    while (testes--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) grafo[i].clear();
        for (int i = 0; i < m; i++) {
            int a, b; ll c;
            cin >> a >> b >> c;
            grafo[a].push_back({b, c});
            if (c >= 0) grafo[b].push_back({a, c});
        }
        cout << (spfa(n) ? "SIM" : "NAO") << endl;
    }
    return 0;
}

SPFA para Distâncias com Restrições


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+10;
ll distancia[MAXN];
int aresta[MAXN], proximo[MAXN], cabeca[MAXN], peso[MAXN], idx;
bool visitado[MAXN];
int contador[MAXN];

void adiciona_aresta(int origem, int destino, ll custo) {
    aresta[idx] = destino;
    proximo[idx] = cabeca[origem];
    peso[idx] = custo;
    cabeca[origem] = idx++;
}

bool spfa(int total_nos) {
    memset(distancia, 0x3f, sizeof distancia);
    memset(visitado, false, sizeof visitado);
    memset(contador, 0, sizeof contador);
    queue<int> fila;
    fila.push(0); distancia[0] = 0; visitado[0] = true;
    while (!fila.empty()) {
        int no = fila.front(); fila.pop();
        visitado[no] = false;
        for (int i = cabeca[no]; i != -1; i = proximo[i]) {
            int viz = aresta[i];
            if (distancia[viz] > distancia[no] + peso[i]) {
                distancia[viz] = distancia[no] + peso[i];
                contador[viz] = contador[no] + 1;
                if (contador[viz] > total_nos + 1) return false;
                if (!visitado[viz]) {
                    visitado[viz] = true;
                    fila.push(viz);
                }
            }
        }
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    memset(cabeca, -1, sizeof cabeca);
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        adiciona_aresta(b, a, c);
    }
    for (int i = n; i >= 1; i--) adiciona_aresta(0, i, 1);
    if (!spfa(n)) cout << "NAO" << endl;
    else for (int i = 1; i <= n; i++) cout << distancia[i] << " ";
    return 0;
}

Floyd-Warshall com Caminhos Intermediários


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 200;
const int MAXM = 1e5+10;
int caminho[MAXM];
ll dist[MAXN][MAXN];

void floyd(int n) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> caminho[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> dist[i][j];
    floyd(n);
    ll total = 0;
    int atual = 1;
    for (int i = 0; i < m; i++) {
        total += dist[atual][caminho[i]];
        atual = caminho[i];
    }
    total += dist[atual][n];
    cout << total << endl;
    return 0;
}

Floyd-Warshall para Maximização de Larguras de Banda


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200;
int largura[MAXN][MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> largura[i][j];
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                largura[i][j] = max(largura[i][j], min(largura[i][k], largura[k][j]));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << largura[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Problema de Otimização com Floyd-Warshall


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e3+10;
const ll INF = 0x3f3f3f3f;
ll grafo[MAXN][MAXN];
int n, m;

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                grafo[i][j] = min(grafo[i][j], grafo[i][k] + grafo[k][j]);
}

int main() {
    cin >> n >> m;
    memset(grafo, 0x3f, sizeof grafo);
    for (int i = 1; i <= n; i++) grafo[i][i] = 0;
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        grafo[a][b] = grafo[b][a] = c;
    }
    floyd();
    ll resultado = INF;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            ll soma = 0;
            for (int e = 1; e < n; e++)
                for (int k = e + 1; k <= n; k++)
                    soma += min(grafo[e][k], min(grafo[e][i] + grafo[j][k], grafo[e][j] + grafo[i][k]));
            resultado = min(resultado, soma);
        }
    }
    cout << resultado << endl;
    return 0;
}

Nós com Alcance Total no Grafo


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e3;
const ll INF = 2e9;
int alcance[MAXN][MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            alcance[i][j] = INF;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        alcance[a][b] = 1;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                alcance[i][j] = min(alcance[i][j], alcance[i][k] + alcance[k][j]);
    int contador = 0;
    for (int i = 1; i <= n; i++) {
        int alcancavel = 0;
        for (int j = 1; j <= n; j++)
            if (i != j && (alcance[j][i] < INF/2 || alcance[i][j] < INF/2)) alcancavel++;
        if (alcancavel >= n - 1) contador++;
    }
    cout << contador;
    return 0;
}

Árvore Geradora Mínima com Kruskal


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6;
int pai[MAXN], tamanho[MAXN];
struct Aresta { int origem, destino; ll custo; } arestas[MAXN];

int find(int x) {
    if (pai[x] != x) pai[x] = find(pai[x]);
    return pai[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> arestas[i].origem >> arestas[i].destino >> arestas[i].custo;
    }
    sort(arestas, arestas + m, [](const Aresta &a, const Aresta &b) { return a.custo < b.custo; });
    for (int i = 1; i <= n; i++) pai[i] = i;
    ll total = 0;
    int arestas_usadas = 0;
    for (int i = 0; i < m; i++) {
        int raiz_a = find(arestas[i].origem);
        int raiz_b = find(arestas[i].destino);
        if (raiz_a != raiz_b) {
            pai[raiz_a] = raiz_b;
            total += arestas[i].custo;
            arestas_usadas++;
        }
    }
    if (arestas_usadas < n - 1) cout << "impossivel" << endl;
    else cout << total << endl;
    return 0;
}

Peso Máximo na Conexão entre Dois Nós


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6+10;
int pai[MAXN];
struct Aresta { int origem, destino; ll custo; } arestas[MAXN];

int find(int x) {
    if (pai[x] != x) pai[x] = find(pai[x]);
    return pai[x];
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        cin >> arestas[i].origem >> arestas[i].destino >> arestas[i].custo;
    }
    sort(arestas, arestas + m, [](const Aresta &a, const Aresta &b) { return a.custo < b.custo; });
    for (int i = 1; i <= n; i++) pai[i] = i;
    ll max_custo = 0;
    for (int i = 0; i < m; i++) {
        int raiz_a = find(arestas[i].origem);
        int raiz_b = find(arestas[i].destino);
        if (raiz_a != raiz_b) {
            pai[raiz_a] = raiz_b;
            max_custo = max(max_custo, arestas[i].custo);
            if (find(s) == find(t)) {
                cout << max_custo << endl;
                return 0;
            }
        }
    }
    return 0;
}

Redução de Custo com Nós Especiais


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e7+10;
int pai[MAXN];
bool especial[MAXN];
struct Aresta { int origem, destino; ll custo; } arestas[MAXN];

int find(int x) {
    if (pai[x] != x) pai[x] = find(pai[x]);
    return pai[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int no;
        cin >> no;
        especial[no] = true;
    }
    ll custo_total = 0;
    for (int i = 1; i < n; i++) {
        cin >> arestas[i].origem >> arestas[i].destino >> arestas[i].custo;
        custo_total += arestas[i].custo;
    }
    sort(arestas + 1, arestas + n, [](const Aresta &a, const Aresta &b) { return a.custo > b.custo; });
    for (int i = 1; i <= n; i++) pai[i] = i;
    for (int i = 1; i < n; i++) {
        int raiz_a = find(arestas[i].origem);
        int raiz_b = find(arestas[i].destino);
        if (especial[raiz_a] && especial[raiz_b]) continue;
        pai[raiz_a] = raiz_b;
        custo_total -= arestas[i].custo;
        especial[raiz_a] = especial[raiz_b] = especial[raiz_a] | especial[raiz_b];
    }
    cout << custo_total;
    return 0;
}

Árvore Geradora Mínima com Restrição de Componentes


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6+10;
int pai[MAXN];
struct Aresta { int origem, destino; ll custo; } arestas[MAXN];

int find(int x) {
    if (pai[x] != x) pai[x] = find(pai[x]);
    return pai[x];
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> arestas[i].origem >> arestas[i].destino >> arestas[i].custo;
    }
    sort(arestas, arestas + m, [](const Aresta &a, const Aresta &b) { return a.custo < b.custo; });
    for (int i = 1; i <= n; i++) pai[i] = i;
    ll custo_total = 0;
    int arestas_usadas = 0;
    for (int i = 0; i < m; i++) {
        int raiz_a = find(arestas[i].origem);
        int raiz_b = find(arestas[i].destino);
        if (raiz_a != raiz_b) {
            pai[raiz_a] = raiz_b;
            custo_total += arestas[i].custo;
            arestas_usadas++;
            if (arestas_usadas >= n - k) break;
        }
    }
    if (arestas_usadas < n - k) cout << "Sem Solucao" << endl;
    else cout << custo_total << endl;
    return 0;
}

Tags: dijkstra spfa floyd-warshall kruskal Grafos

Publicado em 6-25 04:40

Doido Dev