Algoritmos para Grafos | Índice
O tema destas notas de aula é o mesmo de boa parte da Ciência e Engenharia da Computação: a construção de algoritmos eficientes, algoritmos capazes de resolver grandes instâncias de problemas em pouco tempo.
Os problemas de que trataremos aqui são formulados sobre grafos. Um problema desse tipo recebe um grafo (e às vezes algumas informações adicionais) e tem por meta encontrar um certo objeto dentro do grafo. (Por exemplo, dado um grafo e dois de seus vértices, encontrar um caminho mínimo do primeiro vértice ao segundo.) Estas notas têm, portanto, dois objetivos:
Os problemas que consideramos são importantes porque fazem parte de muitas questões fundamentais na ciência, na engenharia, e na indústria.
O material destas notas foi inspirado no volume Graph Algorithms do livro Algorithms in C (3rd. edition) de R. Sedgewick. Tal como no livro de Sedgewick, todos os algoritmos são implementados como programas em linguagem C. Mas seria fácil traduzir os programas para outra linguagem qualquer. Muitas das figuras foram copiadas (sem permissão… ) do livro Algorithms (4th. edition) de R. Sedgewick e K. Wayne.