Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS, ORDENAÇÃO TOPOLÓGICA, BUSCA EM PROFUNDIDADE E BUSCA EM LARGURA -…
GRAFOS
Um grafo é definido como um par de 2 conjuntos: V e E, tais que V é um conjunto com os vértices do grafo, e E é um conjunto com as arestas (pares de vértices).
-
Aciclicidade
Um grafo é dito acíclico quando possui ciclos, isto é, caminhos que começam e terminam no mesmo vértice sem atravessar um mesmo vértice mais de uma vez.
Representação:
Matriz de adjacência
É uma matriz booleana que possui uma linha e uma coluna para cada vértice do grafo. Nessa representação, os números 1's indicam uma aresta entre o par analisado.
Vantagem: Para grafos densos, a representação utilizando matriz de adjacência utiliza menos espaço de memória.
Desvantagem: Para grafos escassos, ocorre o oposto, por causa do tamanho fixo da array.
Lista de adjacência
É uma coleção de listas ligadas, uma para cada vértice. Geralmente é utilizado um header para implementação.
Vantagem: Para grafos escassos, a representação usando lista de adjacência utiliza menos espaço de memória.
Desvantagem: Para grafos densos, ocorre o oposto, por causa do espaço extra ocupado pelos ponteiros.
Ponderados
São grafos ou digrafos que possuem números (pesos) associados às suas arestas. As representações para grafos são válidas para os grafos ponderados.
As matrizes de adjacência nos grafos ponderados são chamadas de matrizes de pesos (ou de custos), e em vez de 0's e 1's, são preenchidas com os pesos das arestas ou com um símbolo aleatório caso não existam.
Já as listas de adjacência funcionam da mesma forma, excetuando-se o fato de que precisam incluir o peso da aresta além do nome do vértice.
-
-
-
-
-
-
ORDENAÇÃO TOPOLÓGICA
Implementações
Aplicação simples de uma busca em profundidade, reparando na ordem que os vértices se tornam pontas mortas. Depois, basta reverter a ordem.
Implementação direta da técnica decrease-and-conquer (por 1): encontrando continuamente um vértice sem arestas de entrada (chamado source), e o deletar junto com todas as arestas que saem dele. Assim, a ordem com a qual ocorrem essas remoções é a solução para o problema de ordenação topológica.
Possui como objetivo listar os vértices de um digrafo numa ordem em que para cada aresta, o vértice no qual ela se inicia é listado antes daquele no qual ela termina.
-
-
