Primeiro Trabalho de Algoritmos e Estrutura de Dados II

Assunto: grafos

Objetivo: implementar o TAD Grafos e algumas aplicações
          importantes

Descrição: Fazer um programa que carregue grafos no formato
           txt e execute os algoritmos de a) Dijkstra, b) Bellman-Ford,
           c) Árvore geradora Mínima (Prim), d) Árvore Geradora 
           Mínima (Kruskal) e e) Ordenação Topológica em profundidade
                      
Entrada:   executável v g1.txt v g2.txt v g3.txt g4.txt g5.txt
 
           onde "executavel" é o nome do seu programa
           g1 é um digrafo com pesos para o algoritmo de Dijkstra
           g2 é um digrafo com pesos para o algoritmo de Bellman-Ford
           g3 é um grafo com pesos para a AGM Prim    
           g4 é um grafo com pesos para a AGM Kruskal
           g5 é um DAG para o algoritmo de ordenação topológica
           v é o vértice inicial a partir do qual se fará o caminho
             e se calculará o custo para os alg. de Dijkstra e Ford.
             Note que v não precisa ser o mesmo para ambos os casos.


ATENÇÃO: os arquivos de grafos .txt devem obedecer "estritamente" o
         formato passados na descrição do projeto. Lembre-se que 
         em todos eles existe uma linha em branco ao final do arquivo.


SAÍDA ESPERADA:


Algoritmo de Dijkstra par o vértice v:
   
      -----------------------
Custo |0 |1 |2 |3 | ...|n-1 |    
      -----------------------
      |c0|c1|c2|c3| ...|cn-1|   ci ->  o custo para cada vértice 
      ----------------------- 


        -----------------------
Caminho |0 |1 |2 |3 | ...|n-1 |
        -----------------------
        |p0|p1|p2|p3| ...|pn-1| pi: vértice predecessor.
        ----------------------- 

****************************************************************

Algoritmo de Bellman-Ford para o vértice v:

      -----------------------
Custo |0 |1 |2 |3 | ...|n-1 |    
      -----------------------
      |c0|c1|c2|c3| ...|cn-1|   ci ->  o custo para cada vértice 
      ----------------------- 


        -----------------------
Caminho |0 |1 |2 |3 | ...|n-1 |
        -----------------------
        |p0|p1|p2|p3| ...|pn-1| pi: vértice predecessor.
        ----------------------- 

*************************************************************

Árvore Geradora Mínima - Prim:

(a,b),(c,d),...(t,u)            -> (i,j) são pares de vértices repre
                                   sentando as arestas, impressos na
                                   ordem em que as arestas são
				   selecionadas

*************************************************************

Árvore Geradora Mínima - Kruskal:

(a,b),(c,d),...(t,u)            -> (i,j) são pares de vértices repre
                                   sentando as arestas, impressos na
                                   ordem em que as arestas são
				   selecionadas

*************************************************************

Ordenação Topológica - em Profundidade

a,b,c,d,e,....,t               -> sequencia de vértices ordenados
 		                   topologicamente

**************************   Fim da execução *****************


OBSERVAÇÕES IMPORTANTES

a) faça um programa estruturado
	-> .h para o tad e .c para as implementações das rotinas
            do grafo, incluindo as rotinas de carregar do
            disco e os algoritmos pedidos.

        -> o programa principal (com a função main) deve estar
           em um arquivo separado, de nome main.c

        -> qq outro TAD que voce usar (fila, lista, etc) deve
           estar em um conjunto .h e .c respectivo e, obviamente,
           separados dos demais.

b) Comentários: faça internamente apenas. Bom comentário é aquele
                que serve pra você mesmo entender o seu código
                daqui a um an !