Aplicação: Ordenação Topológica. -------------------------------- Queremos escrever os elementos de um conjunto parcialmente ordenado de forma que um elemento nunca apareça antes de outro que é menor que ele. Exemplo: 1. a b é definida em função de a) - disciplinas (a a é pré-requisito para b) - funções de um programa (a a função a é chamada dentro de b) Método: - começar com elemento que seja minimal (i.e. não existe nenhum menor que ele). - retirá-lo do conjunto. - repetir até acabarem os elementos. Só é possível se não houver ciclos. Estrutura de dados: vamos implementar o grafo (diagrama) através de uma lista ligada de nós, onde cada nó possui uma lista de sucessores. - Cada nó tem quatro campos: info, o número de predecessores, um ponteiro para o próximo nó da lista, um ponteiro para a lista dos sucessores. struct elemento: +------+ | -------> info +------+ | -------> cont (num. de predecessores) +------+ | -------> prox: ponteiro para elemento +------+ | -------> suc (lista de sucessores): ponteiro para sucessor +------+ - Cada nó da lista de sucessores tem dois campos: um ponteiro para o próximo e um para o nó que ele representa. struct sucessor: +------+ | -------> no: ponteiro para elemento +------+ | -------> prox: ponteiro para sucessor +------+ Montagem da estrutura: Para cada par a, b lido, fazemos: - se a ou b não estiverem na lista, inserimos. - colocamos b na lista de sucessores de a. - aumentamos a contagem dos predecessores de b.