Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Busca em Grafos :
Profundidade :
Como o próprio nome diz, ele se caracteriza por começar num nó raiz (selecionando algum nó como sendo a raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder (backtracking)
-
-
Largura :
Começa pelo nó raiz e explora todos os nós vizinhos. Então, para cada um desses nós mais próximos, explora os seus nós vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca
-
:warning: A complexidade espacial do algoritmo de busca em profundidade é bem menor que a de um algoritmo de busca em largura. Já a complexidade temporal é igual, pois é proporcional ao número de vértices somado ao número de arestas dos grafos que eles atravessam
Um Grafo é uma estrutura de dados formada por um conjunto de não vazio de vértices (ou nós) e por um conjunto de arestas (ou arcos), ligando estes vértices
Características :
-
Um grafo completo com n vértices é um grafo simples onde existe uma aresta ligando todo par não ordenado vértices distintos.
-
Um grafo não precisa ser uma árvore, mas toda árvore é um grafo.
Um grafo é simples (ou regular) se não possuir laços e nem mais de uma aresta ligando dois vértices.
-