Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Definição
-
Se os pares de vértices forem não ordenados ((u,v) = (v, u)) e estão ligados pela mesma aresta não direcionada
-
-
Se os pares de vértices forem ordenados ((u,v) != (v, u)), dizemos que a aresta é dirigida
-
-
Quando a definição não permite varias arestas em um vértices, temos 0 ≤ | E | ≤ | V | ( | V | - 1 ) / 2
-
-
-
-
Representação
Matriz de adjacência
-
o valor da linha x na coluna y é 1 quando tiver uma aresta ligando esses vértices, caso contrario é 0
-
Quando o grafo é esparso, a lista usa menos espaço em relação a matriz, quando o grafo é denso, a matriz é uma alternativa melhor em relação a lista
pesquisa exaustiva
Depth-first search (DFS)
algoritmo
-
-
vai marcando os vértices que foram visitados, pode ser utilizar uma pilha para rastrear as operações
em caso de mais de um vértices adjacente para ser visitado, escolhe por ordem alfabética
após visitar os vértices adjacentes, ele retorna para um ponto onde tinha mais de um vértice (caso tenha acontecido) e continua a busca até que todos o vértice tenham sido visitados
-
-
-
Observações
-
BFS pode ser usada para para encontrar um caminho com o menor número de arestas entre dois dados vértices
Caminhos e ciclos
caminho
sequência de vértices adjacentes que começa do vértices inicial do caminho até o final(caminho de u para v)
se os vértices do caminho são distintos, o caminho é chamado de simples
-
-
é um grafo direcionados temos caminhos direcionados, se chegamos de u para v, não podemos voltar pela mesma aresta
-