Algoritmos para Grafos
em C
via Sedgewick

Paulo Feofiloff

A teoria dos grafos estuda problemas computacionais que envolvem objetos conhecidos como grafos. Os problemas tornaram-se célebres porque ocorrem em diversas áreas da computação, da engenharia, e em muitas aplicações industriais. O material abaixo é um curso de algoritmos para grafos baseado no livro Algorithms in C: Graph Algorithms de R. Sedgewick.  Tomei a liberdade de mudar a ordem em que os tópicos são apresentados no livro, de melhorar (!) a notação e a terminologia, e de corrigir alguns erros do livro.  É claro que aproveitei a oportunidade para introduzir novos erros.  Tal como no livro de Sedgewick, todos os algoritmos são descritos na linguagem C. (É preciso deixar claro, entretanto, que grande parte do material de Sedgewick não é sequer mencionada neste curso. Minhas notas omitem, por exemplo, as excelentes figuras e exemplos do livro, bem como a discussão da complexidade prática dos algoritmos.)     Conceitos básicos Digrafos Grafos Estruturas de dados Matriz de adjacência Vetor de listas de adjacência Grafos aleatórios Digrafos conexos Busca em profundidade Busca em profundidade: introdução Caminhos Arborescências (árvores enraizadas) Componentes de grafos Arborescência de busca em profundidade Aplicações Ciclos em grafos e digrafos Florestas e árvores Grafos bipartidos e ciclos ímpares Pontes em grafos Articulações em grafos Busca em largura Busca em largura Caminhos mínimos Grafos e digrafos com custos Custos nos arcos e arestas Árvores geradoras de custo mínimo Árvores geradoras de grafos Árvores geradora de custo mínimo (MST) Algoritmo de Prim Algoritmo de Kruskal Algoritmo de Boruvka Caminhos de custo mínimo Caminhos de custo mínimo Algoritmo de Dijkstra Digrafos acíclicos Digrafos acíclicos (DAGs) Algoritmos de ordenação topológica Problemas em DAGs Fluxo em redes Fluxo em redes Algoritmo de fluxo máximo Fluxo máximo e corte mínimo Estruturas de dados para redes de fluxo Shortest augmenting paths Maximum capacity augmenting paths   Índice Remissivo Links para conceitos e definições

Material de apoio Transparências do professor José Coelho de Pina Jr. Livros e material na teia WWW

Busca no sítio "Algoritmos para Grafos"