Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - quando a ordem dos vértices não importa(simétrico)
    - - quando a ordem dos vértices importa
    - - Matriz adjacente
        
        Temos uma matriz booleana NxN para um grafo com N vértices, no qual cada linha e cada coluna representa cada vértice do grafo, assim para cada elemento na linha i e coluna j se o seu valor for 1 quer dizer que existe um arco entre eles, quando o valor for 0 o contrário.
      - Lista adjacente
        
        Coleção de listas ligadas, uma para cada vértice, no qual contem todos os vértices adjacentes ao vértice da lista, essas listas utilizam um header para identificar o vértice que a lista representa.
      - Grafos não ponderados
      - Matriz adjacente
        
        A única diferença dos gráficos não ponderados é que na posições onde o valor era 1, se torna agora o valor do arco que liga os vértices e onde era 0 determinamos com o símbolo ∞.
      - Lista adjacente
        
        Para grafos ponderados temos que apenas adicionar o valor do arco junto com vértice adjacente .
      - Grafos Ponderados
        
        Os arcos possuem pesos em forma de números.
      - Buscas
        
        Busca em profundidade ou DFS.
        
        Começamos com um vértice arbitrário e o marcamos como visitado, a cada interação o algoritmo segue para um vértice não visitado adjacente ao que estamos atualmente, isso se estende até chegarmos em um beco sem saída, voltando então um vértice e continuando a busca, se voltarmos pro vértice inicial, concluímos a busca, é essencial usamos uma pilha para traçar as operações.
        
        Busca em largura ou BFS.
        
        Começamos com um vértice arbitrário, visitamos primeiro todos os vértices adjacentes ao inicial, depois os vértices não visitados a 2 arcos de distância e assim por diante, até que todos os vértices conectados ao vértice inicial sejam visitados, é essencial usarmos uma fila para rastrear as operações.
        
        Topological Sort
        
        Decrease-and-conquer technique
        
        Para um grafo G temos um vértice fonte, vértice que não tem arcos incidente nele, esse vértice será excluído e então seguimos para o próximo vértice até chegarmos num grafo vazio. A ordem dor vértices deletados é justamente a solução do topological sort
    - - todo par ordenado de vértices distintos é um arco.
    - - o seu número de arcos é da mesma ordem que o quadrado do número de vértices.
    - - o seu número de arcos são poucos em relação aos vértices.