Neste trabalho, descrevemos e apresentamos os resultados da implementação de um algoritmo BSP/CGM para o fecho transitivo proposto por Cáceres et al. Além disso, apresentamos algumas aplicações deste algoritmo na resoluçãode problemas relacionados em teoria dos grafos, tais como caminhos mais curtos, busca em profundidade e árvore geradora mínima. Estes algoritmos foram implementados em C, usando a interface LAM/MPI e executados no Beowulf do IC-UNICAMP, contendo 66 processadores. Os resultados obtidos são melhores que os descritos na literatura. Para os problemasrelacionados, as implementação que usam a estrutura do algoritmo de Warshall para o fecho transitivo apresentam melhores tempos, quando comparadas a algumas implementações paralelas para os mesmos problemas.