Grafos e kruskal

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1716 palavras )
  • Download(s) : 0
  • Publicado : 21 de novembro de 2012
Ler documento completo
Amostra do texto
UNIVERSIDADE ESTADUAL DO NORTE DO PARANÁ
UENP – CAMPUS LUIZ MENEGHEL
CURSO SISTEMAS DE INFORMAÇÃO

CAIO VINICIUS BENEDITO – 797
MARIO SHIGUEO ISHIKAWA – 811
ROBSON ALVES NOGUEIRA – 789

GRAFOS – CAMINOS MINIMOS
ALGORITMO DE KRUSKAL

BANDEIRANTES-PR
NOVEMBRO / 2012
1. GRAFOS

1.1 Definição
Em matemática e ciência da computação, grafo é o objeto básicode estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".
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 dosgrafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico. Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado à 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 oprotocolo IP que torna possível a Internet ser uma realidade.

Figura: Um grafo com 6 vértices e 7 arestas.

1.2 Spanning Tree
Uma árvore é um grafo conexo e acíclico (não possui ciclos). Toda arvore é um grafo, todo grafo conexo possui pelo menos uma árvore de extensão associada, composta de todos os seus vértices e algumas de suas arestas.
Suponha-se que G é um grafo, então G é uma árvorese satisfazer as seguintes condições:
* G é conexo e apenas um caminho entre dois vértices quaisquer.
* G é acíclico, e simples ciclo é formado se qualquer aresta for adicionada a G.
* G é conexo, e deixará de ser conexo se qualquer aresta for removida de G.
* G é conexo, acíclico e tem n – 1 arestas.

Figura: Árvore
Um grafo G, conexo, admite varias Árvores, uma árvore comtodos os vértices do grafo G denomina-se Árvore Geradora ou de Suporte ou Máxima.

Figura: Grafos (Árvores)
A condição necessária e suficiente para que o grafo G admita uma Árvore Geradora é que G seja conexo. Um grafo G pode admitir mais do que uma Árvore Geradora.

1.3 Busca em Largura
Em uma busca em largura a partir de um vértice v, esperamos que todos os vizinhos de v sejam visitados antesde continuar a busca mais profundamente. Contrariamente à busca em profundidade, o algoritmo de busca em largura não é recursivo. Mas pode ser comparado à versão iterativa da busca em profundidade, que usa uma pilha P:.
Um exemplo de aplicação da busca em largura é a identificação do caminho mais curto entre dois vértices. Nesse caso, o desempenho do algoritmo é melhor que os algoritmos deDijkstra e Floyd. Outra situação onde a busca em largura pode ser usada é quando temos um grafo infinito. Nesse caso, a busca em profundidade pode entrar em um ramo sem saída.

procedimento Busca-Prof-Iter(v: vértice)
Inicializar P
Marcar v como visitado
Empilhar v em P
Enquanto P não vazio:
Enquanto existe um vértice w adjacente ao vértice no topo de P:
Marcar v como visitado
Empilhar w em PRetirar o primeiro elemento de P
O algoritmo de busca em largura é semelhante ao algoritmo de busca em profundida. A principal diferença é que usamos um fila F ao invés de uma filha:

1.4 Busca em Profundidade
Um algoritmo de busca em profundidade realiza uma busca não informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que oalvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos (nó folha). Então a busca retrocede (backtrack) e começa no próximo nó. Numa implementação não recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração.
A complexidade espacial de um algoritmo de busca em profundidade é muito menor que a de um algoritmo de busca...
tracking img