Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - Nesse tipo de grafo, um par qualquer (u,v) é o mesmo que (v,u). Assim, todas as arestas são de "duas vias"
    - - Nesse tipo de grafo, um par qualquer (u,v) não é o mesmo que (v,u). Assim, cada aresta é de "mão única"
  - - - Cada Aij da matriz tem "1" ou "0". Caso Aij seja "1", a aresta entre i e j existe, caso seja "0", ela não existe
    - - Consiste em uma linked list para cada vertice do grafo. Caso exista algum vertice nessa lista, existe uma aresta entre esses dois vertices, caso não, essa aresta não existe
- - - - Adiciona o vértice na ordem (normalmente um stack) e verifica se o vertice atual tem vertices adjacentes não visitados
        
        Se não houver: Verificar se é o ultimo elemento da ordem
        
        Não é: retira o nó atual da ordem e vai para o nó anterior.
        
        É: Verificar se todos os vértices foram visitados
        
        Caso sim: Encerrar o código
        
        Caso não: Reiniciar o código nesse vértice
        
        Se houver: vai para o próximo nó adjacente e faz o passo anterior novamente
  - - - Big-theta (V²), sendo V= quantidade de vertices
    - - Big-theta (V + E), sendo V= quantidade de vertices e E= quantidade de arestas
  - - - Tree edge
        
        Usados pelo DFS para chegar até vértices não visitados
      - Back Edge
        
        Conectam vertices com seus predecessores
- - - - Adiciona o vértice na ordem (normalmente uma fila) e verifica se o vertice atual tem vertices adjacentes não visitados
        
        Se não houver: Verificar se é o ultimo elemento da ordem
        
        É: Verificar se todos os vértices foram visitados
        
        Caso não: Reiniciar o código nesse vértice
        
        Caso sim: Encerrar o código
        
        Não é: retira o nó atual da ordem e vai para o nó posterior.
        
        Se houver: adiciona os vertices adjacente a fila, deleta o vertice atual e faz o passo anterior novamente
  - - - Big-theta (V²), sendo V= quantidade de vertices
    - - Big-theta (V + E), sendo V= quantidade de vertices e E= quantidade de arestas
  - - - Tree edge
        
        Usados pelo DFS para chegar até vértices não visitados
      - Cross Edge
        
        Conectam vertices com seus predecessores, mas essas conexões só ocorrem entre vértices no mesmo nivel ou em niveis adjacentes
- - - - Foward Edge
        
        Conectam vertices com seus sucessores
      - Cross Edge
        
        Nenhum dos anteriores
      - Back Edge
        
        Conectam vertices com seus predecessores
      - Tree edge
        
        Usados para construir a árvore
    - - DFS
        
        Caso tenha Back Edge, é insatisfativel
        
        Consiste em rodar o algoritmo do DFS e o resultado do Topological Sorting é o oposto do DFS. Exemplo: DFS-> a,c,d; Topological->d,c,a
      - Baseado em Decrease to Conquer
        
        Verificar se existem vértices no grafo
        
        Se sim, verificar se existe um vertice sem arestas que vão até ele
        
        Se sim, remover esse vértice e sálva-lo na ordem
        
        Se não, o problema é insatisfativel
        
        Se não, a resposta do Topological Sorting é a ordem que os vertices foram retirados do grafo