Please enable JavaScript.

Coggle requires JavaScript to display documents.

Principal - Coggle Diagram

- - - - Grafo Não Direcionado
        
        As arestas são pares não ordenados de vértices. Uma aresta (u, v) é a mesma que (v, u)
        
        Os vértices u e v são ditos adjacentes e a aresta (u, v) é incidente a eles
      - Grafo Direcionado
        
        As arestas são pares ordenados. Uma aresta (u, v) é direcionada de u para v
        
        u é chamado de cauda (tail) da aresta, e v é a cabeça (head)
      - Grafo Completo
        
        Um grafo onde cada par de vértices distintos está conectado por uma aresta
      - Grafo Denso
        
        Um grafo com um número de arestas próximo ao máximo possível
      - Grafo Esparso
        
        Um grafo com poucas arestas em relação ao número de seus vértices
  - - - É uma matriz booleana n x n (onde n é o número de vértices)
      - O elemento na linha i e coluna j é 1 se houver uma aresta do vértice i para o j, e 0 caso contrário
      - Para um grafo não direcionado, a matriz de adjacência é sempre simétrica (A[i, j] = A[j, i])
    - - É uma coleção de listas ligadas, uma para cada vértice
      - A lista de um vértice contém todos os vértices que lhe são adjacentes.
      - Esta representação costuma ser mais eficiente em termos de espaço para grafos esparsos
  - - - É uma sequência de vértices adjacentes. Um caminho simples é aquele em que todos os vértices são distintos
    - - Um grafo é dito conectado se houver um caminho entre cada par de seus vértices. Um grafo não conectado consiste em vários componentes conectados
    - - É um caminho de comprimento positivo que começa e termina no mesmo vértice e não atravessa a mesma aresta mais de uma vez
    - - Um grafo sem ciclos. Este tipo especial de grafo, quando conectado, é chamado de árvore
- - - - Como funciona:
        
        Início: O algoritmo começa em um vértice arbitrário, marcando-o como visitado.
        
        Exploração: A cada iteração, ele avança para um vértice adjacente ainda não visitado. Esse processo continua até que se atinja um "beco sem saída" (um vértice sem vizinhos não visitados).
        
        Retrocesso (Backtrack): Ao atingir um beco sem saída, o algoritmo retrocede para o vértice anterior e tenta explorar outros caminhos a partir dele.
        
        Estrutura de Dados: A DFS utiliza uma pilha (stack), implícita ou explicitamente, para gerir o processo de travessia e retrocesso.
    - - Arestas de Árvore (Tree Edges): São as arestas usadas para chegar a um vértice não visitado pela primeira vez. Elas formam a estrutura da floresta.
        Arestas de Retorno (Back Edges): Conectam um vértice a um de seus ancestrais (que não seja seu pai imediato) na floresta DFS.
  - - - Como Funciona
        
        Início: Começa em um vértice arbitrário, que é marcado como visitado e colocado em uma fila.
        
        Exploração Nível a Nível: A cada iteração, o algoritmo remove o vértice da frente da fila e visita todos os seus vizinhos não visitados. Estes vizinhos são marcados e adicionados à fila.
        
        Estrutura de Dados: A BFS utiliza uma fila (queue) para garantir a exploração nível a nível.
    - - Arestas de Árvore (Tree Edges): Usadas para alcançar vértices não visitados.
        Arestas de Cruzamento (Cross Edges): Conectam vértices no mesmo nível ou em níveis adjacentes da árvore BFS.
- - - - Se um grafo possui um ciclo (ex: A é pré-requisito de B, e B é pré-requisito de A), é impossível encontrar uma ordem linear que satisfaça as dependências.
      - Portanto, ser um DAG é uma condição necessária e suficiente para que a ordenação topológica tenha uma solução.