grafo

Universidade Federal de Uberlândia
FACOM - Estruturas e Bancos de Dados - GRM05

Trabalho Prático - Estruturas de dados em Linguagem C
Grafos Direcionados: Vértices e Arestas

1

Definição de Grafo em Linguagem C

Um grafo G = (V, E) é um conjunto não-vazio V de vértices, e um conjunto E de arestas. Cada aresta é um par (vi , v j ), sendo vi e v j elementos de V.
Como exemplo de um grafo direcionado, podemos considerar a malha aérea de uma região, de forma que os vértices do grafo representem os aeroportos, que são conectados por vôos. A figura a seguir mostra um grafo para uma região brasileira em que cada aresta reproduz um vôo entre dois aeroportos.

Um grafo em linguagem C pode ser definido utilizando-se listas encadeadas que registram para cada vértice do grafo uma Lista de Adjacências. Desta forma, para cada vértice, podemos registrar à quais outros ele está ligado. A definição de tipos abaixo é um exemplo de solução utilizando listas encadeadas:
#define Vertice int typedef struct no {
Vertice w; struct no *prox;
} No; typedef struct noGrafo {

1

Vertice v;
No *adj; struct noGrafo *prox;
} ListaAdj;

A partir da estrutura de dados definida, podemos visualizar o grafo para a malha aérea no formato de listas encadeadas, como ilustra a figura a seguir:

A lista principal mostra que para o aeroporto da cidade de Belo Horizonte existem dois vôos, armazenados em uma nova lista: um para São Paulo e outro para o Rio de Janeiro. Logo, a lista com as adjacências para Belo Horizonte possui dois nós, correspondentes às duas cidades para as quais existem vôos a partir de BH.

2

2

Descrição do Trabalho

Nesse trabalho, você deverá utilizar a estrutura de dados definida na seção 1 (listas encadeadas) para representar a malha aérea de uma região.
O programa em linguagem C deve permitir que o usuário escolha entre as operações:
1. cadastrar nome de cidade na lista.
2. cadastrar vôo entre duas cidades, checando se as