Please enable JavaScript.
Coggle requires JavaScript to display documents.
MAPA MENTAL 11 - Coggle Diagram
MAPA MENTAL 11
BFS e DFS
-
Definição de BFS: É uma abordagem transversal na qual primeiro percorremos todos os nós no mesmo nível antes de passar para o próximo nível.
-
-
Definição de DFS: Também é uma abordagem de travessia, porém, a travessia começa no nó raiz e prossegue pelos nós o mais longe possível até chegarmos ao nó sem nós próximos não visitados.
-
-
-
Quando utilizar: BFS quando o destino está próximo à origem. DFS quando o destino está distante da origem.
BFS: é usado em grafos bipartidos, caminhos curtos etc.
DFS: é usado em grafos acíclicos e ordem topológia.
Grafos
Um par de conjuntos, que são conjuntos de vértices e conjuntos de arestas. Cada aresta é um par ordenado de vértices.
-
Um vértice w é vizinho de um vértice v, se v-w (aresta que sai de v e entra em w) é uma aresta do grafo.
Arestas antiparalelas: duas arestas serão antiparalelas se o vértice inicial de um é o vértice final do outro. Ou seja, se um é v-w o outro é w-v.
Grafos não dirigidos: se cada uma das arestas forem antiparalelas a alguma outra aresta, ou seja, se para cada aresta v-w, o grafo também tem o seu oposto w-v.
Relação de adjacência: um vértice w é adjacente a um vértice v, se e somente se v é adjacente a w.
Ordenação topológica.
Ordenação linear dos vértices, aonde para cada aresta direcionada v-w, v vem antes de w na ordenação.
É basicamente uma travessia em que cada nó é visitado somente depois que todas as suas dependências são visitadas.
Só é possível, se e somente se, o grafo for um grafo acíclico direcionado.