INF1010 3WB – T5: Implementação de grafos com busca em largura e busca em profundidade.

Enunciado:

Implemente uma classe Grafo para armazenar uma estrutura de grafo baseada em lista de adjacências, em C++, respeitando o seguinte:

Utilize a interface mostrada no arquivo t5_grafo.h abaixo para sua classe.
Os métodos de busca bfs() e dfs() devem imprimir os índices dos vértices visitados, na ordem em que o fazem, separando os índices somente por espaço.
Por exemplo, para o grafo a seguir: a saída de uma execução de bfs() e de dfs() são dadas por:

Saída BFS a partir do vértice 0:
```
0 1 5 2 6 4 3
```
Saída DFS a partir do vértice 0:
```
0 1 2 6 3 4 5
```

Para o mesmo exemplo de grafo, a saída do método mostra() deve ser igual à seguinte:

0: 1(28), 5(10)
1: 0(28), 2(16), 6(14)
2: 1(16)
3: 6(18)
4: 5(25), 6(24)
5: 0(10), 4(25)
6: 1(14), 3(18), 4(24)

Observe que os resultados das funções de busca e da função de exibir o grafo dependem de como estão armazenadas as adjacências, que por sua vez dependem da ordem de inserção das arestas no grafo.
Para o grafo da figura e as saídas exibidas nos itens 2 e 3, a ordem de inserção foi:
```
Grafo G(7);
G.insereAresta(0,1,28);
G.insereAresta(0,5,10);
G.insereAresta(1,2,16);
G.insereAresta(1,6,14);
G.insereAresta(3,6,18);
G.insereAresta(4,5,25);
G.insereAresta(4,6,24);
```
Casos de teste.
É permitido criar funções ou variáveis membro privadas, para facilitar a implementação.

t5_grafo.h

#ifndef T5_GRAFO_H
#define T5_GRAFO_H

#include <vector>

class Grafo
{
public:
    //Construtor. N = numero de vertices.
    Grafo( int N );

    //Insere uma aresta no grafo, do nó @de para o nó @para, com peso @peso.
    //Caso @direcionado esteja marcado como false, insere a aresta tambem no sentido para->de
    void insereAresta( int de, int para, int peso = 1, bool direcionado = false );

    //Imprime os vertices e seus vizinhos
    void mostra();

    //Imprime os nos do grafo na ordem de uma busca em largura
    void bfs( int s );

    //Imprime os nos do grafo na ordem de uma busca em profundidade
    void dfs(int s);

private:
    struct Aresta
    {
        int v; //Vertice destino
        int p; //Peso da aresta
    };

    enum Cor
    {
        BRANCO,
        CINZA,
        PRETO
    };

    //Lista de adjacencias
    std::vector< std::vector< Aresta > > G;

    /* Funcoes e membros privados que julgar necessarios */
};

#endif // T5_GRAFO_H