[Versão antiga]

 

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 tem como dado um grafo (e às vezes algumas informações adicionais) e tem por meta encontrar algum tipo de objeto dentro do grafo. (Por exemplo, dado um grafo e dois de seus vértices, encontrar um caminho de comprimento mínimo do primeiro vértice ao segundo.)  Os objetivos destas notas são, portanto,

  1. conhecer 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 (Mas grande parte do material do livro não é sequer mencionada. As notas também omitem as excelentes figuras e exemplos do livro, bem como a discussão da complexidade prática dos algoritmos.) 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…

Tal como no livro de Sedgewick, todos os programas são escritos em linguagem C.

 

Conceitos básicos

Busca em profundidade

Ciclos e circuitos

Busca em largura

Biconexão

Conexão forte

Coloração

Emparelhamento

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


 

Busca neste sítio

Validated by HTML Validator (based on Tidy) Valid HTML 4.01 Strict Valid CSS!

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