Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - Quando um vértice v é retirado da pilha, nenhum vértice u com uma aresta de u para v pode estar entre os vértices retirado(POP) antes
    - - Procurar e remover o vértice que não tem pai
        
        E repetir até ão sobrar nenhum vértice que satisfaça essa condição
        
        Se tiver mais de uma escolher arbitrariamente
- - - - Visitar todos vértices que estão a 2 arestas de distância até visitar todos vértices conectados
    - - Adicionar primeiro vértice na fila e o marcar como visitado
        
        Adicionar todos vértices adjacentes que não foram visitados
        
        Remover o primeiro vértice
        
        Repetir até a fila ficar vazia
    - - O primeiro vértice visitado é considerado a raiz da primeira árvore
        
        Sempre que visita um vértice novo esse é conectado ao adjacente que já foi visitado tornando filho
        
        Se uma aresta levando a um vértice visitado diferente de seu pai a aresta é identificada como uma aresta cruzada.
    - - Θ(|V|²)
    - - Θ(|V|+|E|)
        
        V= numero de vértices
        
        E= número de arestas
  - - - Operação push quando o vértice é visitado pela primeira vez
        
        Operação pop quando um vértice se torna um dead end(não tem vértices adjacentes não visitados)
    - - Visitar vértice adjacente que não foi visitado
        
        Repetir até encontrar um vértice cujos adjacentes não foram visitados
        
        Voltar procurando vértices adjacentes que não foram visitados
        
        "Ir e voltar " até que todos vértices adjacentes serem visitados
        
        Se tiver mais de um visitar primeiro o vértice quem em primeiro em ordem alfabética
    - - O primeiro vértice visitado é considerado a raiz da primeira árvore
        
        Sempre que visita um vértice novo esse é conectado ao adjacente que já foi visitado tornando filho
        
        back edge são arestas que conectam um vértice ao vértice pai e mais um outro que já foi visitado
    - - Θ(|V|²)
    - - Θ(|V|+|E|)
        
        V= numero de vértices
        
        E= número de arestas
- - - - Tamanho de um caminho é a quantidade de vértices em que o caminho passa
      - Um grafo é conexo se todos os vértices estão em um caminho entre dois vértices u e V
    - - Caminho em que é possível começar e terminar no mesmo vértice e e não passa pela mesma aresta mais de uma vez