Aula 18 - Grafos VI: Ordenação Topológica

1 Flares Facebook 1 1 Flares ×

Aula por Lucca Siaudzionis

"Malter Warinho está ensinando seu filho a se vestir. Para isso, está dando instruções simples sobre a ordem em que seu filho deve se vestir, para não colocar a roupa em ordem contrária (tipo o Superman). As instruções são do tipo: as meias devem ser colocadas antes do sapatos; as calças devem ser vestidas antes do cinto; a camisa deve ser vestida antes do casaco; e por aí vai. Em alguns casos, não interessa a ordem em que deve ser colocada a roupa, por exemplo, o filho pode colocar as calças antes do chapéu e vice-versa. Dada a lista de instruções e o número de peças de roupas, ajude o filho de Malter a se vestir."

Bem, para formalizar um pouco o problema, vamos montar um grafo direcionado onde:

  • cada vértice é uma peça de roupa.
  • cada aresta partindo de um vértice X para um vértice Y significa que X tem que vir antes de Y.

Assim, pode se notar uma relação de transição: se X tem que vir antes de Y e Y tem que vir antes de Z, X tem que vir antes de Z.

Teremos então um grafo semelhante a este:

OT-2

Tendo uma noção do grafo, é fácil perceber alguns fatos simples:

  • se o grafo possui um ciclo, não há ordem em que se possa resolver o problema.
  • podemos executar um vértice (vestir uma roupa) se, e somente se, todos os vértices (roupas) que possuem algum caminho até ele já foram executados.

Com apenas isso, já se pode pensar em um algoritmo bem simples para resolver o problema:

  • Pegar um vértice de grau de entrada zero (nenhuma aresta chega a ele) e acrescentar o vértice a ordem de execução.
  • Remover todas as arestas que partem desse vértice e atualizar os graus dos vértices ligados a essas arestas.
  • Repetir o processo até não haver mais vértices de grau de entrada zero (ou acabarem todos os vértices).

Se, ao final do processo, ainda sobrarem vértices, há um ciclo e não há ordem para resolver o problema. Caso contrário, o problema está resolvido!

Vamos simular o algoritmo para o grafo anterior.

De início, existem quatro vértices de grau zero na lista: 1, 3, 4 e 8. Vamos começar pelo 1.

OT-3 Vértice Grau
1 0
2 2
3 0
4 0
5 1
6 1
7 1
8 0

Removendo o 1, atualizamos o grau do vértice 2. O próximo a ser selecionado que possui grau zero é o 3.

OT-5 Vértice Grau
1 -
2 1
3 0
4 0
5 1
6 1
7 1
8 0

Removendo o 3, faremos o vértice 2 passar a ter grau zero e o acrescentamos a nossa lista de vértices de grau zero. O próximo vértice na lista é o 4.

OT-6 Vértice Grau
1 -
2 0
3 -
4 0
5 1
6 1
7 1
8 0

Remover o vértice 4 não altera nada, pois não existem mais arestas partindo desse vértice. O próximo vértice na lista é o 8.

OT-7 Vértice Grau
1 -
2 0
3 -
4 -
5 1
6 1
7 1
8 0

Ao remover o 8, faremos o vértice 5 ter grau zero e, portanto, o acrescentamos a lista. O próximo vértice é o 2.

OT-9 Vértice Grau
1 -
2 0
3 -
4 -
5 0
6 1
7 1
8 -

Ao remover o 2, fazemos o vértice 6 ter grau zero e, portanto, o acrescentamos a lista. O próximo vértice é o 5.

OT-10 Vértice Grau
1 -
2 -
3 -
4 -
5 0
6 0
7 1
8 -

Ao remover o 5, faremos restar apenas vértices de grau zero no grafo, portanto, podemos removê-los em qualquer ordem.

Finalizando, temos as seguinte ordem de remoção de vértices (execução de tarefas): 1 \rightarrow 3\rightarrow 4\rightarrow 8\rightarrow 2\rightarrow 5\rightarrow 6\rightarrow 7.

Um código para resolver o problema do Filho de Malter, em C++, seria:

Agora, para praticar, resolva os seguintes problemas.

Problema 1 - A Base de um Gráfico

Problema 2 - Escalonamento Ótimo

Problema 3 - Ordering Tasks


As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.

 

1 Flares Facebook 1 1 Flares ×
1 Flares Facebook 1 1 Flares ×
%d bloggers like this: