Como é que o coletor de lixo detecta que um objeto já não é utilizado e pode ser removido?

O coletor de lixo (Garbage Collector) no Android (baseado em JVM ou ART) determina que um objeto não está mais em uso se não houver referências ativas a ele a partir de objetos raiz, como pilhas de threads, campos estáticos, etc.

O processo é aproximadamente assim:

• O coletor começa com os objetos raiz e marca todos os objetos acessíveis por referências.
• Todos os objetos não marcados são considerados inacessíveis e podem ser removidos.

Assim, se um objeto não for acessível a partir do código ativo, ele é considerado lixo e sujeito à coleta.

Isso é chamado de algoritmo de busca em profundidade ou marcação e varredura (mark-and-sweep).