Algoritmos para Grafos
em C
via Sedgewick

Paulo Feofiloff

com figuras de José Coelho de Pina

 

O tema destas notas é 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:

  1. apresentar certos problemas básicos que envolvem grafos e
  2. estudar algoritmos eficientes para esses problemas.

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 programas são escritos em linguagem C.  Muitas das figuras foram descaradamente copiadas do livro Algorithms (4th. edition) de R. Sedgewick e K. Wayne.

Tomei a liberdade de melhorar (!) a notação e a terminologia do livro de Sedgewick, e de corrigir alguns erros.  É claro que aproveitei a oportunidade para introduzir novos erros…

 

Conceitos básicos

Busca em profundidade

Busca em largura e distâncias

Florestas, árvores, conexão

Conexão forte

Coloração

Emparelhamentos

Grafos com custos

Árvores geradoras de custo mínimo

Caminhos de custo mínimo

Caminhos de custo máximo

Fluxo em redes

 

Índice remissivo

Material de apoio


Esse material foi originalmente preparado para a disciplina MAC0328 (Algoritmos em Grafos), do curso de Ciência da Computação do IME-USP.

Outros assuntos:   Algoritmos em Grafos com Stanford GraphBase  |  Literate Programming & CWEB  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Graph Theory Exercises  |  Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Projeto de Algoritmos em C  |  Estruturas de Dados  |  Otimização Combinatória  |  Fluxo em Redes  |  Digrafos  |  Algoritmos de Programação Linear  |  O que é uma prova?  |  Uma Introdução Sucinta a Algoritmos de Aproximação  |  Opiniões e notícias