Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM7 - Coggle Diagram
MM7
Graphs
Grafos são estruturas formadas por vértices e segmentos que ligam esses vértices. Podem ser direcionados (digraphs) ou não. Além disso, essa definição não admite loops (auto-conexões).
Representações
Podem ser representados por uma matriz (i x j) que indica se há conexão entre os vértices i e j (1 ou 0). Além de não ser a melhor para grafos dispersos, deve-se tomar cuidado com redundância de informação.
Outra representação é a feita por listas. Basicamente, cada lista contém os vizinhos de um vértice em específico, que pode ser identificado pelo header. Acaba sendo ruim para grafos densos pois consome muito espaço extra
Grafos com Pesos
Se a aplicação necessitar de pesos para as conexões, deve-se armazenar tal informação. Na matriz, coloca-se o peso ao invés de 1 ou 0 e, na lista, adiciona-se o valor do peso em cada nó.
-
Search
Depth-First Search
A travessia por DFS funciona da seguinte forma: após passar por um vértice, passa pelo primeiro vizinho dele e continua até não achar mais vértices novos. Tal funcionamento se assemelha a uma pilha, estrutura que pode ser útil em várias situações dessa travessia.
Acaba formando uma floresta de nós conectados por "tree edges" e possivelmente "back edges", representando, respectivamente, o caminho da travessia e possíveis caminhos de volta.
Pode ser usada para checar conectividade e ciclicidade do grafo. Além disso, serve para aplicações mais avançadas como a identificação de vértices de articulação.
A conectividade do grafo é assegurada se todos os nós foram checados em uma única árvore/ciclo/travessia. Enquanto isso, a ciclicidade está presente entre dois pontos se existir, na DFS, uma back edge entre eles (ou maior ainda) e, na BFS, uma cross edge entre eles e/ou filhos deles.
Breadth-First Search
A travessia BFS, diferentemente da DFS, passa primeiro por todos os vizinhos do vértice para depois seguir com o primeiro deles. Assim, pode ser representada e/ou auxiliada por uma fila.
Também forma uma floresta, mas, ao invés de back edges, podem existir somente tree edges e cross edges, estes representando caminhos alternativos.
Além de checar conectividade e ciclicidade, pode ser utilizada para identificar o menor caminho entre dois pontos.
-
A busca em grafos é na verdade uma travessia que você pode utilizar para muitas aplicações além de checar a presença de um elemento
O desempenho de ambas travessias são V² para a aplicação em matriz e V + E para a aplicação com listas. Mas isso raramente importa, visto que sua utilidade difere de outros algoritmos.
Topological Sort
Um grafo direcionado, entre muitas coisas, pode ser útil para a ordenação de elementos por dependências. Isso é chamado de Topological Sorting e pode ser feito de duas formas:
DFS popping
Realizando uma travessia DFS no grafo direcionado, o inverso da ordem na qual os vértices encerram sua passagem é uma solução para a ordenação topológica. Em outras palavras, uma possível ordenação é o inverso da ordem de remoção de vértices da pilha DFS.
Source Deletion
Uma forma alternativa de realizar a ordenação topológica é remover, um a um, os vértices do grafo que não possuem caminhos para si. A ordem em que os vértices são removidos é uma solução.
OBS: Para a ordenação topológica ser possível, o grafo deve ser acíclico. Isso significa, por exemplo, que, na DFS não podem haver back edges, mas somente tree, cross e forward edges.