Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
Introdução Cap. 1 (28-31)
Grafos
Coleção de vértices (ou nós) no plano
Alguns conectados por arestas
Conceitos
Vértices adjacentes
Aresta não-direcionada
"Endpoints"
Vértices incidentes
Grafo não-direcionado
Cada aresta é não-direcionada
Vértices direcionados
Cauda do vértice
Cabeça do vértice
Grafos direcionados (ou digrafos)
Cada aresta é direcionada
Loops
Grafo completo (K)
Grafo denso
Grafo disperso
Fórmulas
0 <= Quantidade de arestas <= (quantidade de vértices*(quantidade de vértices -1))/2
Representações
Matriz Adjacente
Melhor para grafos densos
Listas Adjacentes
Melhor para grafos dispersos
G = (V, E)
Grafos com pesos
Grafo com números atribuídos as arestas (pesos)
Matriz de peso ou de custo
Caminhos e Ciclos
Conectividade
Caminho para todos os vértices
Componente conectado
Aciclicidade
Caminho
Simples
Tamanho
Direcionado
Força Bruta e Busca Exaustiva (Cap. 3 122-128)
(3.5) Depth-First Search and Breadth-First Search
Algoritmos que processam todos os Vértices e Arestas de um grafo
Depth-first search (DFS)
Visita um vértice arbitrário
Procede para um vértice não visitado adjacente ao escolhido
Continua até um "Dead end"
Volta um vértice e tenta continuar daí
Se ainda sobrar algum, recomeça de um deles
Usa uma pilha para guardar as operações
Depth-first search em uma floresta
Arestas tree e back
Eficiência depende da quantidade de vértices e arestas
Duas orderings
Aplicações
Conectividade
Aciclicidade
Pontos de articulação
Breadth-First Search (BFS)
Escolhe um vértice arbitrário
Visita todos os vértices adjacentes ao escolhido
Visita todos os vértices não visitados duas arestas de distância deles e por aí vai
Se sobrar, o algoritmo recomeça em dos vértices remanescentes
Uso de filas
BFS em florestas
Arestas tree e cross
Eficiência igual ao DFS
Uma ordering
Aplicações
Conectividade
Aciclicidade
Caminhos com arestas mínimas
(4) Decrescer para conquistar (138-141)
(4.2) Ordenação Topológica
Grafo direcionado (Digrafo)
Direções especificadas para todas as arestas
Mais difícil de ser representado
Aresta Back (DFS)
Ciclo direcionado
Se não tiver
Grafo direcionado acíclico (DAG)
Grafo precisa ser um DAG
Verificação e solução
DFS
Decrescer por um para conquistar
Os dois dão soluções corretas e que podem ser alternativas
Ordenação entre as direções das arestas
Aplicações
Instruction scheduling
Cell evaluation
Symbol dependecies