A constante nil tem o mesmo sabor que o NULL da linguagem C. O CLRS está imaginando uma implementação sofisticada em que cada vértice é um endereço na memória, apontado por um ponteiro.
Estamos supondo, é claro, que nil é diferente de todos os vértices do digrafo.
Quando os vértices do digrafo são 1, 2, … , n, pode-se usar 0 no lugar de nil.