24

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.201

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Ordenação topológica é um método de ordenação linear dos vértices de um grafo dirigido, de tal modo que se existe uma aresta dirigida do vértice para o vértice , então vem antes de .

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

No grafo acíclico direcionado dado, começamos a travessia a partir do nó , que é a origem. Por ser a origem, ser tempo de descoberta é 1. O próximo nó a ser percorrido é o nó , então seu tempo de descoberta é 2. Depois, o nó , com tempo de descoberta 3. Após , não existe caminho ou aresta dirigia a nenhum outro nó. Com isso, a travessia ou busca não pode prosseguir e deve retroceder. Com isso, retorna para a origem e procede dessa maneira, incrementando o tempo de descoberta de cada nó de acordo com sua ordem de travessia.

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Durante o processo, o tempo de término de cada nó é considerado o tempo total no qual todos os vértices adjacentes a um vértice particular são completamente percorridos no processo. O tempo de término para o vértice , nesse caso, é 4, porque a travessia é feita de até passando por e depois novamente por . Desse modo, a ordenação topológica é obtida de acordo com o tempo de término dos vértices do grafo. O maior tempo de término aparece primeiro.

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Segue abaixo a ordenação ao fim do processo, com os tempos de descoberta e término:

Imagem 1

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.