Teoria dos Grafos BCC 204 UFOP - DECOM - Departamento de Computação Professor Haroldo Gambini Santos

Material e Exercícios - Aulas Práticas em Grafos

[Objetivo]   [Códigos]   [Receitas de Bolo]   [Exercícios]

Objetivo:

Apresentar recursos da linguagem C++ e da sua biblioteca padrão (STL) que facilitem o armazenamento, manipulação e consulta de grafos e exercitar a implementação de algoritmos em grafos.

Códigos de Exemplo:

Parte 1: Estrutura de conjuntos em C++

Conjunto de Vértices

Código 1 - utilização do set

Parte 2: Estrutura de relações em C++ - Grafo Direcionado

Código 2 - utilização do map para armazenar um grafo direcionado

Parte 3: Estrutura de relações em C++ - Grafo Direcionado com Pesos

Código 3 - utilização do map para armazenar um grafo direcionado com pesos

"Receitas de Bolo" para uso de grafos em C++ com a biblioteca padrão

Grafo direcionado:

Declaração:

map< int, set<int> > G;  

Preenchimento - adicionar arco 5 -> 3:

G[5].insert(3);

Consultar vizinhos do nó 33:

set<int>::iterator sIt;

for ( sIt=G[33].begin() ; sIt!=G[33].end() ; sIt++ )

    printf("vertice %d\n", *sIt);

Declaração de grafo direcionado com pesos:

map< int, map<int, set<int>> > G;

Exercícios:

1. Escreva um programa que sirva para determinar uma ordem de instalação de pacotes de software que não quebre dependências, ou seja, um software somente deve ser instalado depois que todas as suas dependências estiverem instaladas. O programa deve ler (do teclado ou de um arquivo) os dados no formato exemplificado a seguir, onde cada pacote é unicamente identificado por um número inteiro:

   3  2

   4  1

   ...

   nesse exemplo, o pacote 3 depende do pacote 2 para ser instalado e o pacote 4 depende do pacote 1.  Como saída o programa deve imprimir uma ordem válida de instalação para todos os pacotes informados.