Please enable JavaScript.

Coggle requires JavaScript to display documents.

Graphs, Depth-First Search and Breadth-First Search, Topological Sorting -…

- - - - Dizemos que u e v são pontos finais da aresta (u,v).
      - U grafo G pode ser chamada de unidirecional para toda aresta unidirecional.
      - Caso par de vert. (u,v) não for o mesmo que (v,u) nós dizemos que a aresta (u,v) é direcional do vert. u, chamada de tail (RABO / CAUDA) para o vert. v que é chamada de head (CABEÇA).
        
        Grafos direcionais também podem ser chamados de digrafos.
- - - - Uma matriz é adjacente se ela reflete o conceito de adjacencia (a e b são adjacente se a se conecta em b) no que tange a informação que ela carrega.
      - Estrutura
        
        A matriz adj. de um grafo de n vertíces é uma matriz booleana n x n com linha e coluna para cada vert.
      - Em um elemento na ith e jth coluna é igual a 1 se existir uma aresta que saia do vert. ith para o vert. jth vert.. O elemento vai ser igual a 0 quando essa aresta não existir.
    - - É uma coleção de lista ligada.
        
        Um para cada vert. que contêm todos os vert. adjacentes ao verti. da lista.
        
        Usualmente, cada lista começa com um header para identificar o vert. em que a lista é compilada.
  - - - Ambas representações principais podem ser adaptadas para acomodar pedos e medidas nas arestas.
        
        Se um grafo ponderado for representado por uma matriz adj. então os elementos presentes na matriz são os pesos das arestas.
        
        O símbolo de infinito representará que não há peso nessa aresta.
  - - - Ambos são baseados no conceito de CAMINHOS.
        
        CAMINHO do vert. u para o vert. v pode de um grafo G pode ser definido como uma série de vert. adj. que começa com o vert. u e termina no vert. v.
      - Se todos os vert. do caminho são distintos, então dizemos que é caminho simples.
        
        O tamanho do caminho é o núm. total de vert. pertencentes ao caminho - 1. É igual ao núm. de arestas do caminho.
        
        No caso o grafo for um grafo direcionado, dizemos que é Caminho direcionado.
        
        É uma seq. de vert. em que todos os os pares consecutivos são conectados por arestas do primeiro vert. listado ao próx. vert..
        
        Grafo concectado
        
        Caso todos os pares de vert. u e v exist ir um parte de u a v
        
        Formalmente, um componente conectado é um maximal (Não é expansível pela inclusão de outro vert. na aresta) conectado a um subgrafo de um grafo.
- - - - Uma pratica importante é que o canditado adja. não visitado é escolhido por uma estrutura de dados que representa o grafo.
        
        Esse precoeso continua até a achar o vert. que não um adj. não visitado.
        
        No fim, o algoritmo retorna uma aresta para tentar continuar visitando vert. não visitados de lá.
    - - É útil tambémpara acompanhar uma travessia de DFS pela construção de uma DFS forest.
        
        Começa no vert. da travessia servir como raiz da primeira tree de cada uma floresta.
        
        Quando um novo vert. não visitado é pesquisado pela primeira vez, ele é anexado como filho para o vert. de que começou a pesquisa.
        
        Tal aresta é chamada de aresta de árvores pois o conjunto dessas arestas forma uma floresta.
        
        O algoritmo também pode encontrar uma aresta que leva previamente a um vert. visitado diferente do antecessor.
        
        Cada uma dessas arestas pode ser chamadas de back edge por que são conectadas a um vert. antecessor de outro parente
        
        PSEUDOCODIGO
        
        1 more item...
  - - - O tempo de travessia vai ser medido por BIG THETA( |V|^2) de uma matriz adj, já de uma lista adj, a representação será de BIG THETA(|V| + |E|), no qual V o núm. de vert. e E o núm de arestas.
- - - - Usa-se Queue.
        
        A queue é inicializada pelo vert. que iniciará a pesquisa. Em cada operação, o algoritmo identifica todos os vert. não visitados que são adj, ao vert. front, feita todas as visitas, esses vert. são add na fila depois que o front vert. é removido.
        
        Há também a versão breadth-first search forest
        
        A travessia começa no vert. que funciona como raiz da primeira tree de cada uma forest.
        
        Sempre que um novo vértice não visitado
        é alcançado pela primeira vez, o vértice é anexado como um filho ao vértice que está sendo
        alcançado por uma borda chamada borda de árvore
        
        Caso uma aresta conduzir para um vert. previamente visitado, então outro antecessor é encontrado e a aresta será chamada de cross edge
  - - - A estrutura de um BFS forest de um grafo unidirecional pode ser feito por dois tipos de arestas: tree edges e cross edges.
        
        tree edges
        
        Usado uma vez para chamada prévia de um vert. não visitado
        
        cross edge
        
        Conecta vert. para aqueles visitados anteriormente, mas infelizmente volta arestas em DFS tree.
- - - - Duas direções
        
        Pontos articulados,conectividades, acíclica
  - - - Uma direção
        
        tree e cross edges, conectividades, acíclica, minino pares de arestas
- - - - Se encontrarmos uma back edge, não é DAG.
        
        Por que DFS?
        
        Quando algum vert. v é retirado na pilha, nenhum vert. u com aresta que dê para o vert. que foi retirado poderá ser retirado antes de v
    - - A implicação de uma busca por um vert. que não tem arestas em comuns, e ele é deletado junto com todas as arestas que saem dele.
- - - - A matriz adj. de um digrafo não tem simetria.
      - A aresta de um digrafo tem apenas uma correspondência nós no digrafo na lista adj.