Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM5 - Grafos pt1, O que são, Tipos de Grafos, Representações de Grafos,…
-
O que são
Aplicações
-
-
-
- Modelagem de dependências
- Grafos são estruturas que modelam relações entre objetos
- Composto por vértices (nós) e arestas (ligações)
- Podem ser direcionados ou não direcionados
- Podem ter pesos (valores associados às arestas)
-
Tipos de Grafos
Direcionados (Digraphs)
-
- (u → v) é diferente de (v → u)
Ponderados
- Cada aresta tem um peso (distância ou custo)
- Usado em algoritmos como Dijkstra e Prim
Não Ponderados
- Todas as arestas têm peso igual
- Usado em buscas simples BFS
Não Direcionados
- Arestas conectam vértices em ambos os sentidos
-
Representações de Grafos
Matriz de Adjacência
- Usa uma matriz n x n para armazenar conexões
- Valor 1 (ou peso) indica aresta entre vértices
- Boa para grafos densos (muitas conexões)
-
- Fácil verificar se existe uma aresta
- Difícil listar vizinhos rapidamente
Lista de Adjacência
- Cada vértice mantém uma lista de vértices conectados
- Boa para grafos esparsos (poucas conexões)
-
-
-
- Mais eficiente em buscas BFS e DFS
Lista de Arestas
- Armazena todas as arestas como pares (u, v)
-
- Útil em algoritmos baseados em arestas como Kruskal
- Não eficiente para percorrer vizinhos
-
Competição
Em C++
- int matrix[V][V] → matriz de adjacência
- vector<pair<int, int>> edges → lista de arestas
- vector<vector<int>> adj → lista de adjacência
Conversões
- Escolha depende da densidade do grafo
- De matriz para lista e vice-versa são possíveis, mas custosas
-