Trabalho de Formatura Supervisionado

No problema da conectividade dinâmica estamos interessados em manter um grafo sujeito a atualizações e consultas de conectividade. Uma atualização é uma adição ou remoçãode aresta. Uma consulta de conectividade deseja saber se existe um caminho entre dois vértices. A solução apresentada mantém diversas florestas geradoras do grafo. Cada árvore dasflorestas geradoras é representada por uma árvore de busca binária balanceada. O consumo de tempo amortizado das operações é polilogarítmico. A solução foi implementada em C++. Seu desempenho foi testado na prática.

Palavras-chave: grafo, conectividade dinâmica, HDT, árvore de trilha euleriana.

O estudo do problema se mostrou mais desafiador do que o esperado. O principal artigo que serviu como referência para a elaboração do trabalho deixa muitos detalhes de lado e foram necessárias várias sessões com meu orientador para um entendimento completo. Houve um amadurecimento muito grande em relação a compreensão da literatura acadêmica de alto nível.

Implementar toda estrutura também foi um grande desafio. Depois de muitos segmentation faults e milhares de linhas de código, o programa funciona, é rápido e está bem testado. Estou orgulhoso do resultado obtido na implementação. As incontáveis horas treinando para maratona de programação ajudaram muito no processo de codificação.

O desenvolvimento deste trabalho evidenciou algo que eu já desconfiava: escrever bem é muito difícil. Perdi as contas de quantas vezes reescrevi uma frase ou abri um livro para ver como outros autores organizam seus textos. Passei a dar muito mais valor para um texto bem escrito. As dicas do meu orientador foram muito boas, mas ainda preciso ler e escrever muito para garantir a excelência dos meus futuros textos.