An algorithm is given for computing the transitive closure of a directed graph in a time no greater thana1N1n+a2n2 for largen wherea1 anda2 are constants depending on the computer used to execute the algorithm,n is the number of nodes in the graph andN1 is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probabilityp, the average time to compute the transitive closure is no greater than min{a1pn3+a2n2, 1/2a1n2p−2+a2n2} for largen. The algorithm will compute the transitive closure of an undirected graph in a time no greater thana2n2 for largen. The method uses aboutn2+n bits and 5n words of storage (where each word can holdn+2 values).