Imagine-se em um planeta distante, onde redes de computadores são frequentemente atingidas por tempestades de raios e eventos eletromagnéticos. Para enfrentar esse desafio, uma nova tecnologia revolucionária está prestes a ser implementada: os para-raios. Porém, há uma regra crucial: eles só podem ser instalados nos "links de borda" dos clusters de rede, nunca no interior.
O objetivo deste trabalho é desenvolver um algoritmo capaz de listar os "links de borda" da rede, identificar todos os clusters e construir a Floresta de clusters-bordas.
- Links de Borda: São os links que conectam diferentes clusters de rede. Ou seja, são aqueles que, se desconectados, resultam em isolamento entre dois ou mais clusters.
- Clusters: São conjuntos de links de rede onde, mesmo que um link seja removido, ainda é possível trocar mensagens entre todos os outros links do cluster.
- Floresta de Clusters-Bordas: É uma representação da rede onde cada cluster é representado por um vértice, e há uma aresta entre um vértice de cluster e um vértice de link de borda se o cluster correspondente compartilha esse link de borda.
Os links denotados por quadrados são os links de borda, no caso são os vértices: c, d, h.
Cada cluster é marcado por um círculo, sendo assim temos os clusters: {a, b, c, d}, {c, h}, {d, e, f, g}, {h, i}.
Floresta de clusters-bordas correspondente à rede da imagem anterior.
A implementação é feita em linguagem C++, foi utilizada uma abordagem eficiente baseada em busca em profundidade (DFS). Com estruturas de dados bem pensadas e algoritmos otimizados, garantindo que o programa seja rápido e robusto, mesmo para redes com milhões de vértices.
Para compilar o código, basta utilizar um compilador C++ como o g++, fornecendo o arquivo de origem "tp1.cpp":
g++ -o tp1 tp1.cppDepois de compilado, basta executar o programa e fornecer as entradas necessárias:
./tp1Este README fornece uma visão geral do trabalho e da implementação. Para mais detalhes sobre o funcionamento do algoritmo e sobre o código-fonte, consulte o enunciado no trabalho (enunciado.pdf) e o próprio código (tp1.cpp).
GeeksforGeeks: Biconnected Components - GeeksforGeeks
Wikipedia: Biconnected Component - Wikipedia