Estrutura de dados (grafos)

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2461 palavras )
  • Download(s) : 0
  • Publicado : 28 de fevereiro de 2013
Ler documento completo
Amostra do texto
TRABALHO DE
ESTRUTURA DE DADOS

Grafos


Definição para Grafo:

Um Grafo é uma forma de representar relacionamentos que existem entre pares de objetos. Isto é um conjunto de objetos, chamados vértices, juntamente com uma coleção entre pares de vértices. A propósito, esta noção de “grafos” não deve ser confundida com diagrama de barras de funções plots.
Visto de forma abstrata, um grafo(G) é simplesmente um conjunto (V) de vértices e uma coleção (E) de pares de vértices de (V), chamados de arestas. Assim um grafo é uma forma de representar conexões ou relações entre pares de objetos de algum conjunto (V). Alguns livros usam uma terminologia diferente para grafos e referem-se ao que se chama de vértices, como nodos; e ao que se chama de arestas, como arcos. Serão utilizados aquio termo “vértices” e “arestas”.
As arestas em um grafo podem ser dirigidas ou não- dirigidas. Uma aresta (u,v) é dita dirigida de (u) para (v) se o par (u,v)for ordenado,com (u) precedendo (v).Uma aresta (u,v) é dita não-dirigida se o par (u,v) não for ordenado.

Os grafos são visualizados tipicamente desenhando-se os vértices como ovais ou retângulos e as arestas como segmentos ou curvasconectando pares de ovais ou retângulos. A seguir são apresentados alguns exemplos de grafos dirigidos e não-dirigidos.

Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho maiseconômico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.

Outro exemplo é o casodas redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade.

Grafos têm sido utilizados para representar o formalismo das redes complexas,onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido.

Tipos de Grafos:

Grafo Não-Dirigido:


São grafos onde as arestas E(G) não são ordenadas (direcionadas), ou seja, a
ARESTA (V1, V2) é a mesma ARESTA (V2, V1).

Grafo o (Dígrafo):


São grafos onde as arestas E(G) são ordenadas (direcionadas), ou seja, a
ARESTA (V1, V2) é diferente daARESTA (V2, V1).

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. A busca em grafo consiste em explorar um grafo, de forma que obtenha um processo sistemático de como caminhar por seus vértices e arestas. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices.Se o grafo é uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível.

Estrutura de dados para grafos:

Existem tre alternativas conhecidas,geralmente referidas como lista de arestas,lista de adjacencia e matriz de adjacencia.Nas tres apresentaçoes,usa-se um container (um lista ou vetor por exemplo) para armazenar os vertices do grafo.

Lista deArestas
É uma representação de um grafo na qual é dado um vetor ou lista com pares de vértices representando as arestas desse grafo.
Exemplo: Seja um grafo G de exemplo, definido por:
V (G) = f1; 2; 3; 4; 5g
E(G) = ff1; 2g; f2; 5g; f5; 4g; f4; 3g; f4; 2gg

Sua representação por lista de arestas é dada por:
f1; 2g; f2; 5g; f5; 4g; f4; 3g; f4; 2g

Para representar os vértices nessa...
tracking img