[Versão antiga deste sítio]

 

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 programas eficientes, programas capazes de resolver grandes 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. entender 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 nestas notas. 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.  Ao contrário do livro, entretanto, estas notas tratam desde o início de objetos mais gerais que grafos: os digrafos, ou grafos dirigidos

 

Conceitos básicos

Busca em profundidade

Digrafos acíclicos e componentes fortes

Busca em largura

Árvores e grafos bipartidos

Caminhos de custo mínimo

Árvores geradoras de custo mínimo

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