Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS, BUSCA EM PROFUNDIDADE, BUSCA EM LARGURA, ORDENAÇÃO TOPOLÓGICA -…
GRAFOS
-
-
-
Uma matriz de adjacência é um array 2D de vértices V x C. Cada linha e coluna representam um vértice.
Se o valor de qulaquer elemento a[i][j] for 1, isso representa que há uma aresta conectando o vértice i eo vértice j.
-
-
Cada índice da lista representa um vértice e os elementos em sua lista vinculada são os elementos que possuem uma aresta com o vértice índice.
Um grafo é uma estrutura de dados (V,E) que consiste em:
-
- Uma coleção de arestas E, representadas como pares ordenados do vértice (u,v)
Adjacência: um vértice é adjacente a outro quando houver uma aresta ligando-os. No exemplo acima, 3 e dois não são adjacentes pois não há nenhuma aresta conectando eles diretamente.
Caminho: um caminho é a sequência de arestas que permite ir de um vértice A a um vértice B. No exemplo, traçaremos o caminho para ir do vértice 0 ao vértice 2: 0-1, 1-2 e 0-2.
Gráfo Direcionado: Um gráfo é direcionado quando há um caminho (u, v) mas não há um caminho (v, u). É identificado quando na aresta houver uma seta indicando qual o sentido daquela coneção.
Grafo é uma coleção de nós que possuem dados e estão conectados a outros nós.
O Facebook é uma aplicação que utiliza grafos para armazenar seus dados. Pois, o cilo cde amizades de uma pessoa pode ser representada pro grafos, as informações que uma publicação dela vem adquirindo, etc.
BUSCA EM PROFUNDIDADE
Na teoria dos grafos, busca por profundidade é um algoritmos para realizar uma travessia numa árvore, estrutura de árvore ou gráfo. O algoritmos começa num nó raiz (no caso do grafo, ele escolhe um nó e o sleciona como raiz) e explora o possível de cada um dos seus ramos antes de retroceder.
-
O algoritmospercore a estrutura de árvore ou gráfo até encontrar o elemento, caso chegue a um vértice sem filhos, ele retrocede e recomeça a busca do próximo vértice.
-
A complexidade espacial de um um algoritmos de busca em profundidade é muito menor que a de um algoritmos de busca em largura. A complexidade temporal de ambos algoritmos são proporcionais ao número de vértice somados ao núimero de arestas.
BUSCA EM LARGURA
O algoritmos faz uma busca exaustiva no grafo, passando em todos seus vértices e arestas. Sendo assim, o algoritmos precisa garantir que não visitará um vértice ou aresta mais de uma vez, para isso, utiliza uma estrutura de dados fila para garantir a ordem de chegada dos vértice. Dessa forma, as visitas são em ordem de chegada na estrutura de fila e um vértice já inserido não pode entrar novamente na estrutura.
ORDENAÇÃO TOPOLÓGICA
Essa ordenação só funciona para gráfos ACÍCLICOS E DIRECIONADOS (DAG) objetivo da ordenação linear é pegar um gráfo e ordená-lo de forma linear em uma lista ligada.
-
Quando houverem precedências (exemplo, grade curricular do curso de ciência da computação)
Em informática, as aplicações deste tipo surgem em agendamentos de instruções, ordenação de fórmulas de avaliação de células quando recalculando os valores de fórmulas em planilhas, síntese lógica, determinação da ordem das tarefas de compilação para executar em arquivos "make", e resolução de dependências de símbolos em ligadores.