Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos, Depth-First Search, Breadth-First Search, Ordenação Topológica -…

- - - - Uma matriz quadrada booleana de ordem igual ao número de vértices, na qual cada linha e cada coluna representa um vértice
        
        Um elemento da matriz é igual a 1 quando os vértices que representam sua linha e coluna são ligados por uma linha e 0 quando não
        
        A matriz de um grafo não direcionado é simétrica, mas o mesmo não pode ser dito para os digrafos
    - - Um conjunto de listas ligadas em que cada lista do conjunto se relaciona a um vértice e as listas contém os vértices ligados a ele
        
        Os digrafos tem apenas um nódulo correspondente para cada linha nas listas
  - - - Eles podem ser representados como matrizes usando os pesos no lugar de 1 para as linhas que ligam vértices que caracteres especiais no lugar de 0
        
        Na representação com listas, os itens da lista precisam conter o nome do vértices ligado e o peso da linha
    - - O caminho de um vértice "u" a um "v" é a sequência de vértices adjacentes que começa em "u" e termina em "v"
        
        O número de vértices no caminho é o cumprimento do caminho
        
        Quando todos os vértices no caminho são diferentes, diz-se que o caminho é simples
        
        Para os grafos direcionados, existem os caminhos direcionados
        
        São como os caminho normais, mas os vértices são ligados por linhas direcionadas que saem do vértice anterior e entram no próximo
        
        Um grafo é dito conectado quando há um caminho entre quaisquer dois vértices do grafo
        
        Ele pode não ser conectado, então é formado por pedaços chamados componentes conectados
        
        1 more item...
        
        Grafos também podem ter ciclos, caminhos de cumprimento positivo que começam e terminam em um mesmo vértice
        
        1 more item...
- - - - Quando não indicam, diz-se que elas são não direcionadas e que os vértices membros do par são adjacentes e conectados pela linha
        
        Os vértices "u" e "v" dessa linha são chamados os limites (endpoints) da linha
        
        Também se diz que os vértices são incidentes à reta e que a reta é incidente aos limites
        
        Chama-se loop quando uma linha conecta um vértice a si mesmo
        
        Quando todo vértice do grafo está conectado a outro vértice, diz-se que o grafo está completo
        
        Um grafo com poucos vértices não ligados é chamado denso
        
        1 more item...
        
        Quando todas as linhas do grafo são não direcionadas, diz-se que o grafo é não direcionado
        
        Quando todas são direcionadas, diz-se que é um grafo direcionado ou digrafo
        
        A linha é direcionada quando um par (u, v) é igual ao par (v, u)
        
        Quando a linha é direcionada, assumindo um par (u, v), diz-se que ela é direcionada de u para v
        
        u é chamado a cauda da linha
        
        v é chamada a cabeça da linha
        
        Também pode-se dizer que a linha sai de u e entra para v
- - - - Os vértices adjacentes, quando visitados pela primeira vez, são ligados como filhos do anterior
        
        As linhas que ligam esses vértices pai e filhos são chamadas tree edges
        
        Essas linhas também podem ligar um vértice a um ancestral próprio que não seja seu ancestral direto. Nese caso, elas são chamadas back edges
        
        Podemos determinar se um grafo é cíclico checando a presença de uma back edge
- - - - Então, volta-se para o vértice anterior e visita-se outro vértice ajdacente até se encontrar outro beco-sem-saída
        
        O processo se repete até retornar ao vértice original, agora um beco-sem-saída
- - - - Há dois algoritmos utilizados para determinar se essa condição é verdadeira
        
        Um realiza uma travessia de Depth-First Search procurando por uma back edge. Se uma for encontrada, o digrafo tem um ciclo, e a ordenação não é possível
        
        Se for possível, a ordem reversa da de vértices visitados é a solução
        
        No outro, encontra-se uma fonte, um vértice sem linhas direcionadas entrando nele
        
        Depois, deleta-se o vértice e as linhas saindo dele
        
        Então, repete-se o processo
        
        A ordem na qual as fontes são deletadas oferece uma soluçao para a ordenação
        
        Se não houver nenhuma fonte, a ordenação não é possível
        
        Se houver múltiplas fontes, uma pode ser escolhida arbitrariamente antes de seguir para outra