Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - Grafos que tem todas os seus vértices repleto de arestas é chamado de grafo completo. enquanto o que possui apenas poucos espaços para arestas sobrando é chamado de denso e o que tem poucas arestas, de esparso.
        
        A representação de grafos para algoritmos podem ocorrer de duas maneiras: matriz de adjacência e lista de adjacência.
        
        Para grafos pouco denso, a lista de adjacência utiliza menos memória, enquanto para grafos denso, ocorre o oposto.
        
        Um grafo é conectado, quando existe um caminho para qualquer vertíce para outro.
- - - - Assim como na DFS, na BFS também existe uma árvore de travessia. O Nó inicial serve como raiz da árvore, quando chega em um novo vértice, é criado uma aresta também chamada de aresta de árvore, que torna o novo nó em filho do antecessor. Se uma aresta chega a um nó que já foi visitado anteriormente, cria-se uma cross-edge
        
        A BFS tem a mesma eficiência temporal do DFS
        
        BFS não é capaz de encontrar pontos de articulação.
        Porém, pode ser utilizado para encontrar um caminho com a menor quantidade de arestas entre dois vértices.
- - - - além disso, também é conveniente utilizar uma floresta de busca profunda, sendo o vértice inicial da busca a raiz, e enquanto vai visitando novos nós, vai adicionando como filho do antecessor, a aresta que faz a ligação desses nós é chamada de aresta da árvore, pois esses vértices acabam por formar uma árvore. Existem arestas que ligam a antepassados não diretos, e tal aresta e chamada de aresta de volta ou back edge
        
        Big O notation para as implementações de grafos
        Para a travessia em matriz de adjacência é O(|V^2|) enquanto para a lista é O(|V|+|E|) sendo V e E o número de vértices e arestas, respectivamente.
        
        O DFS é bom para verificar a conectividade e ciclismo do grafo. para verificar a existência de ciclos, podemos utilizar da vantagem da representação em forma de árvore