Estrutura de dados
Por: Jonathan Ulrich de Oliveira • 27/11/2015 • Trabalho acadêmico • 3.031 Palavras (13 Páginas) • 262 Visualizações
FACULDADE ANHANGUERA DE TAUBATÉ – UNIDADE II
ATIVIDADES PRÁTICAS SUPERVISIONADAS
Estrutura de Dados
Prof.:
2º Bimestre / 2014
Curso: Ciência da Computação
Semestre: 3º e 4º - Turma A – Ano: 2014
Taubaté
02 de Dezembro de 2014
ETAPA 4.
Aula-tema: Grafos.
Passo 2 (Equipe).
Fazer a discussão da leitura do capítulo do livro texto e do material de aula, que será utilizado como base para a implementação de rotas de voos por meio da estrutura grafo, com destaque para:
- Representação de Grafos em C.
Os vértices de um grafo serão representados por números inteiros no intervalo 0..v-1. O conjunto de vértices será, portanto, 0 1 2 3...v-1.Vértices são representados por objetos do tipo Vertex.
#define Vertex int
Os arcos dos grafos serão representados por structs do tipo Edge. Um objeto do tipo Edge representa um arco com ponta inicial v e ponta final w.
typedef struct{
Vertex v;
Vertex w;
} Edge;
Se e é um arco então e.v é a ponta inicial e e.w é a ponta final do arco. A construção de arcos ficará a cargo de uma função EDGE. A função EDGE recebe dois vértices v e w e devolve um arco com ponta inicial v e ponta final w.
Edge EDGE (Vertex v, Vertex w){
Edge e;Teoria dos Grafos – 3
e.v = v;
e.w = w;
return e;
}
- Algoritmo de Menor Caminho.
O algoritmo de Dijkstra identifica, a partir de um vértice do grafo, qual é o custo mínimo entre esse vértice e todos os outros do grafo. No início, o conjunto S contém somente esse vértice, chamado origem. A cada passo, selecionamos no conjunto de vértices sobrando, o que é o mais perto da origem. Depois atualizamos, para cada vértice sobrando, a sua distância em relação à origem. Se passando pelo novo vértice acrescentado, a distância fica menor, é essa nova distância que será memorizada.
Suponhamos que o grafo é representado por uma matriz de adjacência onde não existe aresta entre dois vértices. Suponhamos também que os vértices do grafo são enumerados de 1 até n, isto é, o conjunto de vértices é N = {1, 2, ..., n}. Utilizaremos também um vetor D[2..n] que conterá a distância que separa todo vértice do vértice 1 (o vertíce do grafo que é o vertice 1 é escolhido arbitrariamente). Eis o algoritmo:
função Dijkstra(L = [1..n, 1..n]: grafo): vetor[2..n]
C := {2,3,...,n} {Implicitamente S = N - C}
Para i := 2 até n:
D[i] := L[1,i]
Repetir n-2 vezes:
v := Elemento de C que minimiza D[v]
C := C - {v}
Para cada elemento w de C:
D[w] := min(D[w],D[v]+ L[v,w])
Retornar D
- Representação por meio de Matriz de Adjacência.
Seja G = (V, E) um grafo com n vértices, onde n 1. Supomos que os vértices são numerados 1, 2, ..., |V| de alguma maneira arbitrária. Então a representação de
matriz de adjacências de um grafo G consiste em uma matriz |V| |V| A = (aij) tal que A(i,j) = 1 se a borda
(vi, vj)({vi, vj} para um grafo dirigido1) fica em E(G).
A matriz de adjacências para um grafo não-dirigido2
é simétrica, pois a borda (vi, vj) está em E(G), se a borda (vi, vj) também está em E(G). A matriz de adjacências de
um grafo dirigido não necessita ser simétrica. É de n2 bits o espaço necessário para representar um grafo, usando a matriz de adjacências.
A representação de matriz de adjacências pode ser usada no caso de grafos ponderados3. Por exemplo, se G = (V, E) é um grafo ponderado com função peso de aresta w, o peso w(u, v) da aresta (u, v) E é simplesmente armazenado como a entrada na fila u e na coluna v da matriz de adjacências.
A simplicidade de uma matriz de adjacências pode torná-la preferível quando os grafos são razoavelmente pequenos. Em lugar de usar uma palavra de memória de
computador para cada entrada da matriz, a matriz de adjacências usa somente um bit por entrada.
- Caminhamento em Amplitude.
Em uma busca em largura a partir de um vértice v, esperamos que todos os vizinhos de v sejam visitados antes de continuar a busca mais profundamente. Contrariamente à busca em profundidade, o algoritmo de busca em largura não é recursivo.
O algoritmo de busca em largura é semelhante ao algoritmo de busca em profundidade. A principal diferença é que usamos um fila F ao invés de uma pilha:
procedimento Busca-Largura(v: vértice)
Inicializar F
Marcar v como visitado
Colocar v no final de F
Enquanto F não vazio:
u := primeiro elemento de F
Retirar u de F
Para cada vértice w adjacente a u:
Se w não foi visitado:
Marcar w como visitado
Colocar w no final de F
Neste caso é preciso um programa para lançar a busca:
procedimento Busca(G: Grafo)
Para cada vértice v de G:
Marcar v como não visitado
Para cada vértice v de G:
Se v não foi visitado:
{Busca-Largura ou Busca-Prof-iter}(v)
- Caminhamento em Profundidade.
Seja um grafo G = (V,E) que contém n vértices. Seja tambem uma representação que indica, para cada vértice, se ele foi visitado ou não. Eis uma versão recursiva do algoritmo de busca em profundidade que visita todos os vértices:
...