Projeto em grafos

Universidade Federal da Bahia
Instituto de Matemática
Departamento de Ciência da Computação

Projeto em Grafos
MAT156 - Teoria dos Grafos
Profa. Fabíola Gonçalves Pereira Greve
Classe GRAFO
Métodos Públicos
Construtor();
Destrutor();
Display();
Display_Ordem();
Busca_Profundidade();
Busca_Largura();
Ordem_Topológica();
Arvore_Geradora_Min();
Componentes_Conexas();
Encontre_Ciclo();
Coloração_Mínima();
Caminho_Minimo (vértice);
Fim Classe
Classe GRAFO
Estado
Constantes
N = |V|

M = |E|

(valores máximos para |V| e |E|)

Classe VÉRTICE (informações que caracterizam um vértice) ident: inteiro;
(identificação)
info: string;
(nome associado ao vértice) visita: inteiro;
(guarda ordem de visita do vértice na realização de uma busca) cor: inteiro;
(cor do vértice na realização da coloração) label: inteiro;
(guarda rótulo do vértice na realização do caminho mínimo) topo: inteiro;
(ordem de visita topológica do vértice) indegree: inteiro;
(grau de entrada do vértice) component: inteiro; (número da componente que o vértice faz parte) on_path: boolean; (auxiliar para determinar se vértice está em caminho) adj: Lista;
(lista de vértices adjacentes)
Fim Classe

Objetos m: n: vert: qtde real de arestas do grafo; qtde real de vértices do grafo; vetor [1..n] de vertices; (vetor que representa os vértices)

Métodos Públicos
Construtor ()
Leitura (n, m);

(leitura do qtde de vértices e arestas do grafo)

Para

i = 1 até n faça (fornecimento das informações de cada vértice) leitura (vert[i].info);
(inicializa todos os campos dos vértices);;
FimPara

% Pedir para usuário determinar se grafo é orientado (S) ou não (N)
% Leitura das arestas
Para i = 1 até m faça leitura (v,w);
(leitura da aresta com extremos v e w)
(gerar djacência para v) vert[v].adj = w;
(gerar adjacência para w) % caso grafo não seja orientado vert[w].adj = v;
FimPara
Display ()
(Exibição do grafo na tela do computador na forma :