Estruturas de Dados - Grafos (Guilherme)

Prévia do material em texto

Estruturas de Dados
Grafos
Guilherme N. Ramos
gnramos@cic.unb.br
Departamento de Cieˆncia da Computac¸a˜o
Universidade de Bras´ılia
gnramos (CIC/UnB) ED - Grafos 1/45
Grafos
Grafo: uma representac¸a˜o de relac¸o˜es (arestas) entre objetos (ve´rtices).
A Arco (aresta): par ordenado de ve´rtices.
V Ve´rtice (no´): estrutura de dados.
Exemplo:
V = {1, 2, 3, 4, 5, 6}
A = {(1, 2), (1, 5), (2, 3), (2, 5),
(3, 4), (4, 5), (4, 6)}
gnramos (CIC/UnB) ED - Grafos 2/45
Grafos
- Um ve´rtice e´ um objeto simples que pode ter nome e outros
atributos.
- Grafos sa˜o estruturas de dados bastantes gene´ricas, englobando
todas as estruturas vistas anteriormente
- Definindo um grafo:
V = {A,B,C,D,E,F}
A = {(A,B), (B,A), (B,C), (B,D), (C,C), (D,A), (D,C), (E,F)}
A
B
C
D
E
F
gnramos (CIC/UnB) ED - Grafos 3/45
Grafos
Aplicac¸o˜es
- No´s sa˜o cidades e arcos sa˜o estradas: os grafos auxiliam a trac¸ar os
caminhos e descobrir o caminho mais curto (ou mais longo) entre
cidades
- No´s sa˜o terminais de dispositivos eletroˆnicos e arcos representam as
conexo˜es entre esses terminais
- No´s sa˜o tarefas em um projeto e arcos representam as dependeˆncias
entre as tarefas
gnramos (CIC/UnB) ED - Grafos 4/45
Conceitos e Definic¸o˜es
Grafo direcionado : as arestas ou arcos sa˜o direcionados, a conexa˜o
(A,B) e´ diferente da conexa˜o (B,A).
Grafo na˜o direcionado : as arestas ou arcos na˜o possuem direc¸a˜o e (A,B)
e´ igual a (B,A).
- Na˜o e´ permitido uma aresta para o mesmo no´ ex:
(C,C).
A
B
C
D A
B
C
D
gnramos (CIC/UnB) ED - Grafos 5/45
Conceitos e Definic¸o˜es
Ve´rtices adjacentes : sa˜o no´s ligados por um arco.
- Adjaceˆncia na˜o e´ sime´trica em grafos direcionados.
Arco incidente : e´ um arco que chega a um ve´rtice.
- arco incidente em D → (B,D)
Grau de v : Na˜o-direcionado: nu´mero de arcos incidentes em v .
Direcionado: soma dos arcos
de entrada : que chegam ao ve´rtice.
de sa´ıda : que saem do ve´rtice.
Caminho : sequeˆncia de arcos levando de um ve´rtice a outro.
- O caminho entre no´ C e no´ A e´ {(C,B), (B,A)}.
A
B
C
D
gnramos (CIC/UnB) ED - Grafos 6/45
Conceitos e Definic¸o˜es
Alcanc¸a´vel : um ve´rtice x e´ alcanc¸a´vel a partir do ve´rtice y se existe
um caminho de y ate´ x .
- D e´ alcanc¸a´vel a partir de A.
Circuito : caminho que leva de um ve´rtice a ele mesmo.
- {(B,D), (D,A), (A,B)}
Lac¸o : circuito de um u´nico arco.
- {(C,C)}
A
B
C
D
gnramos (CIC/UnB) ED - Grafos 7/45
Conceitos e Definic¸o˜es
Grafo ac´ıclico : e´ um grafo que na˜o possui circuito
Subgrafo : grafo formando por um subconjunto de ve´rtices de outro
grafo, contendo todos os arcos cujas extremidades sa˜o os
ve´rtices neste subconjunto
Grafo parcial : conte´m todos os no´s de outro grafo mas apenas um
subconjunto de seus arcos
Subgrafo
A
B
D
Grafo parcial
A
B
C
D
gnramos (CIC/UnB) ED - Grafos 8/45
Conceitos e Definic¸o˜es
Grafo Conexo : grafo que possui pelo menos um no´ a partir de qual
existem caminhos para todos os outros no´s.
Grafo Fortemente Conexo : para todos os no´s existem caminhos a partir
de todos os outros no´s
Grafo valorado ou ponderado : os arcos possuem valores ou pesos
associados
A
B
C
D
0.10.3
0.4
0.2
0.7
0.5
0.8
1
gnramos (CIC/UnB) ED - Grafos 9/45
Implementac¸a˜o
Matriz de Adjaceˆncia
- Cada posic¸a˜o na matriz e´ um arco:
- linha indica o no´ de sa´ıda do arco
- coluna indica o no´ de chegada
- Valor da posic¸a˜o indica:
- a existeˆncia ou na˜o do arco
- o peso associado ao arco
- Deve ser utilizada para grafos densos, onde o nu´mero de arcos |A| e´
pro´ximo do nu´mero de ve´rtices ao quadrado |V |2
- Complexidade de espac¸o O(V 2)
- O tempo necessa´rio para acessar um elemento e´ constante.
- Ler ou examinar a matriz tem complexidade de tempo O(V 2)
gnramos (CIC/UnB) ED - Grafos 10/45
Implementac¸a˜o
Matriz de Adjaceˆncia
gnramos (CIC/UnB) ED - Grafos 11/45
Implementac¸a˜o
Lista de Adjaceˆncia
- Os ve´rtices de uma lista de adjaceˆncia sa˜o em geral armazenados em
uma ordem arbitra´ria.
- Possui uma complexidade de espac¸o O(|V |+ |A|)
- Indicada para grafos esparsos, onde |A| e´ muito menor do que |V |2 .
- e´ compacta e usualmente utilizada na maioria das aplicac¸o˜es.
- Tempo O(|V |) para determinar se existe uma aresta entre o ve´rtice i
e o ve´rtice j , pois podem existir O(|V |)ve´rtices na lista de
adjacentes do ve´rtice i .
Ve´rtice
typedef struct v node t {
char cidade [20];
a node t ∗aresta ;
struct v node t ∗prox;
} v node t ;
Aresta
typedef struct a node t {
double peso;
struct v node t ∗ vertice ;
struct a node t ∗prox;
} a node t;
gnramos (CIC/UnB) ED - Grafos 12/45
Implementac¸a˜o
Lista de Adjaceˆncia
A
B
C
D
0.10.3
0.4
0.2
0.7
0.5
0.8
1
A
B
C
D
0.3
−→
B
0.4
−→
A 0.2
−→
C 0.7
−→
D
0.5
−→
C 0.1
−→
D
0.8
−→
A 1
−→
C
gnramos (CIC/UnB) ED - Grafos 13/45
Busca
Busca em Profundidade
- e´ um algoritmo para caminhar no grafo.
- A estrate´gia e´ buscar o mais profundo no grafo sempre que poss´ıvel.
- Os arcos sa˜o exploradas a partir do ve´rtice v mais recentemente
descoberto que ainda possui arestas na˜o exploradas saindo dele.
- Quando todas as arestas adjacentes a v tiverem sido exploradas a
busca anda para tra´s para explorar ve´rtices que saem do ve´rtice do
qual v foi descoberto.
gnramos (CIC/UnB) ED - Grafos 14/45
Busca
Busca em Profundidade - Algoritmo
Enquanto a pilha na˜o esta´ vazia fac¸a:
1 Seja v o ve´rtice no topo da pilha e AV seus arcos.
2 Se AV 6= ∅, enta˜o retire um arco (v ,w) de AV :
- Se w na˜o esta´ marcado
(i) Enta˜o enta˜o marque w
(ii) Coloque w na lista de arcos visitados
3 Sena˜o, retire v do topo da pilha.
void b prof(v node t ∗v, a node t∗∗ptr arestas) {
processa(v);
int i ;
for( i = 0; i < NUM VIZINHOS; ++i) {
v node t ∗w = vizinho(v, i) ;
if (!processado(w)) {
b prof(w, ptr arestas ) ;
insere( ptr arestas , aresta(v,w));
}
}
}
gnramos (CIC/UnB) ED - Grafos 15/45
Busca
Busca em Largura (em Extensa˜o)
- Expande a fronteira entre ve´rtices descobertos e na˜o descobertos
uniformemente atrave´s da largura da fronteira.
- O algoritmo descobre todos os ve´rtices a uma distaˆncia k do ve´rtice
origem antes de descobrir qualquer ve´rtice a uma distaˆncia k + 1.
- O grafo G (V ,A) pode ser direcionado ou na˜o direcionado.
gnramos (CIC/UnB) ED - Grafos 16/45
Busca
Busca em Largura (em Extensa˜o) - Algoritmo
1 Coloca o no´ raiz na fila.
2 Retira um no´ do in´ıcio da fila e o examina.
3 Se o elemento procurado esta´ nesse no´, interrompe a busca e
retorna o resultado.
4 Sena˜o, coloca todos os sucessores desse no´, ainda na˜o examinados,
no final da lista.
5 Se a fila esta´ vazia, cada no´ no grafo ja´ foi examinado
- interrompe a busca e retorna “na˜o encontrado”.
6 Repete passo 2.
gnramos (CIC/UnB) ED - Grafos 17/45
Busca
Ana´lise de Complexidade
- Complexidade temporal de ambos os algoritmos de busca e´
O(|V |·|A|).
- Complexidade espacial da busca em profundidade e´ O(h), onde h e´
o comprimento do mais longo caminho no grafo.
- Complexidade espacial da busca em largura e´ O(|V |·|A|)
gnramos (CIC/UnB) ED - Grafos 18/45
Busca
Busca Profundidade x Largura
- A busca em largura e´ completa apenas se a a´rvore pesquisada tem
um nu´mero finito de ramos.
- A busca em largura e´ o´tima se o custo dos passos forem ideˆnticos -
o algoritmo encontrara´ a soluc¸a˜o mais “rasa” de uma a´rvore de
busca, na˜o necessariamente a melhor. No caso em que os passos
possuem custos diferentes, a soluc¸a˜o mais “rasa” na˜o e´
necessariamente a melhor.
- A busca em profundidade e´ aplicadaem va´rios algoritmos de
ordenac¸a˜o em grafos como:
- Ordenamento topolo´gico.
- Encontrar componentes fortemente conectados.
gnramos (CIC/UnB) ED - Grafos 19/45
Busca
Exemplo: Missiona´rios e Canibais
3 missionarios e 3 canibais esta˜o em um lado de um rio, e ha´ uma canoa
onde cabem ata´ 2 pessoas. Como levar todos ao outro lado do rio sem
que os canibais fiquem em maior nu´mero que os missiona´rios em uma
margem?
Supondo a representac¸a˜o:
cMargemEsquerda/MargemDireita
gnramos (CIC/UnB) ED - Grafos 20/45
Busca
Exemplo: Missiona´rios e Canibais
c3,3/0,0
3,1/0,2c
2,2/1,1c
1,3/2,0c
c3,2/0,1
c2,3/1,0
3,0/0,3c
2,1/1,2c
1,2/2,1c
c3,1/0,2
c2,2/1,1
1,1/2,2c
2,0/1,3c
0,2/3,1c
c2,1/1,2
c1,2/2,1
1,0/2,3c
0,1/3,2c
c0,2/3,1
c1,1/2,2
0,0/3,3c
c2,0/1,3
gnramos (CIC/UnB) ED - Grafos 21/45
Ordenamento Topolo´gico
- Ordenac¸a˜o linear de todos os ve´rtices, tal que se G conte´m uma
aresta (u, v) enta˜o u aparece antes de v .
- Pode ser vista como uma ordenac¸a˜o de seus ve´rtices ao longo de
uma linha horizontal de tal forma que todas as arestas esta˜o
direcionadas da esquerda para a direita.
- Pode ser usado sempre que o problema abordado envolve uma
ordem parcial.
- Um grafo pode ter va´rios ordenamentos topolo´gicos poss´ıveis.
gnramos (CIC/UnB) ED - Grafos 22/45
Ordenamento Topolo´gico
7
11
5
2
8
3
9 10
1 7, 5, 3, 11, 8, 2, 9, 10
2 3, 5, 7, 8, 11, 2, 9, 10
3 3, 7, 8, 5, 11, 10, 2, 9
4 5, 7, 3, 8, 11, 10, 9, 2
5 7, 5, 11, 3, 10, 8, 9, 2
6 7, 5, 11, 2, 3, 8, 9, 10
3 7 8 5 11 10 2 9
gnramos (CIC/UnB) ED - Grafos 23/45
Ordenamento Topolo´gico
Algoritmo para Ordenamento Topolo´gico:
- Adaptac¸a˜o da busca em profundidade.
- Durante a busca em profundidade, a cada ve´rtice completo, insere
na frente de uma lista encadeada.
void ord top(v node t ∗v, v node t∗∗ptr vertices) {
processa(v);
int i ;
for( i = 0; i < NUM VIZINHOS; ++i) {
v node t ∗w = vizinho(v, i) ;
if (!processado(w)) {
ord top(w, ptr vertices ) ;
insere( ptr vertices , w);
}
}
}
gnramos (CIC/UnB) ED - Grafos 24/45
Ordenamento Topolo´gico
Aplicac¸a˜o: Escalonamento
Escalonamento
Organizac¸a˜o (distribuic¸a˜o e ordem de execuc¸a˜o) de tarefas nos recursos
dispon´ıveis.
Objetivos:
- Ser justo(evitando o adiamento indefinido).
- Maximizar a produtividade (throughput.
- Ser previs´ıvel.
- Minimizar o tempo de resposta para usua´rios interativos.
- Maximizar o nu´mero poss´ıvel de usua´rio interativos.
- Minimizar a sobrecarga (overhead).
- Balancear o uso de recursos.
- Exibir degradac¸a˜o previs´ıvel e progressiva em situac¸o˜es de intensa
carga de trabalho.
- Etc.
gnramos (CIC/UnB) ED - Grafos 25/45
Ordenamento Topolo´gico
Aplicac¸a˜o: Escalonamento
1 Pegar ovo.
2 Pegar o o´leo.
3 Untar a frigideira.
4 Quebrar o ovo.
5 Esquentar o o´leo.
6 Poˆr o ovo na
frigideira.
7 Esperar o ovo fritar.
8 Retirar o ovo.
1 2 3 4 5 6 7 8
1 4
532
6 7 8
Recurso 1
Recurso 2
Recurso ?
gnramos (CIC/UnB) ED - Grafos 26/45
Exerc´ıcio
Algoritmo para Encontrar Amigos em uma Rede Social
Dada uma rede social representada por um grafo, onde cada aresta
representa uma relac¸a˜o de amizade, elabore um algoritmo que liste
sugesto˜es de prova´veis amigos. Uma pessoa pode ser sugerida a outra se
elas na˜o sa˜o amigas (na rede social) e teˆm pelo menos n amigos em
comum.
1 Suponha o grafo G (V ,A) e um ve´rtice v inicial.
2 Para cada ve´rtice u tal que 6∃(v , u):
2.1 Para cada ve´rtice w 6= v tal que ∃(u,w):
Se 6 ∃(v ,w): incremente contador W (de amigos em comum com v).
2.2 Se contador W > n: adicione w a lista de sugesto˜es.
3 Retorne a lista de sugesto˜es.
gnramos (CIC/UnB) ED - Grafos 27/45
Exerc´ıcio
Algoritmo para Encontrar Amigos em uma Rede Social
A
B
C
D EK
F
G
H
I
J
L
A B C D E F G H I J K L
contador 0 0 0 0 3 0 2 1 1 1 0 0
a) Para n = 3 → {E} b) Para n = 2 → {E ,G}
gnramos (CIC/UnB) ED - Grafos 28/45
Exemplo: Mapas de Mu´sica
http://audiomap.tuneglue.net/
gnramos (CIC/UnB) ED - Grafos 29/45
A´rvore Geradora M´ınima
- Considere um grafo na˜o direcionado e conectado; e que associada a
cada arco ha´ uma distaˆncia na˜o negativa.
- O objetivo e´ encontrar o caminho mais curto de tal maneira que os
arcos fornec¸am um caminho entre todos os pares de no´s.
- O subgrafo conecta todos os ve´rtices e´ uma a´rvore geradora.
- Essa a´rvore e´ uma a´rvore geradora m´ınima se o comprimento total e´
o menor poss´ıvel.
gnramos (CIC/UnB) ED - Grafos 30/45
A´rvore Geradora M´ınima
Propriedades:
- Podem haver va´rias a´rvores geradoras m´ınimas, com o mesmo
comprimento.
- Se cada arco tem um peso diferente, existe uma u´nica a´rvore
geradora m´ınima.
- A a´rvore geradora m´ınima e´ o subgrafo de menor custo conectando
todos os ve´rtices.
Exemplo de aplicac¸a˜o: instalac¸a˜o de fibras o´ticas no campus de uma
faculdade.
- Cada trecho de fibra o´tica entre os pre´dios possui um custo
associado.
- Uma a´rvore de extensa˜o fornece um modo de conectar todos os
pre´dios sem redundaˆncia.
- Uma a´rvore geradora m´ınima desse grafo nos daria uma a´rvore com
o menor custo para fazer essa ligac¸a˜o.
gnramos (CIC/UnB) ED - Grafos 31/45
A´rvore Geradora M´ınima
Algoritmos
1 Algoritmo Gene´rico: a cada passo, adiciona-se uma aresta “segura”
a um subconjunto de arestas do grafo: o subconjunto final e´ a AGM.
2 Algoritmo de Prim: as arestas adicionadas ao subconjunto (a´rvore)
devem ser as de m´ınimo peso que conectam a a´rvore a um ve´rtice
ainda na˜o presente.
3 Algoritmo de Kruskal: as arestas adicionadas a a´rvore sa˜o as arestas
de menor peso que conecta dois componentes distintos.
gnramos (CIC/UnB) ED - Grafos 32/45
A´rvore Geradora M´ınima
Algoritmo Gene´rico
Enquanto o subconjunto A′ na˜o for uma AGM:
1 Seleciona uma aresta do grafo.
2 Se aresta e´ segura, adiciona a A′.
A aresta segura e´ sempre a aresta de peso m´ınimo que conecta a a´rvore a
um ve´rtice na˜o presente no conjunto V ′ (ve´rtices ligados pelas arestas de
A′).
Como determinar o que e´ uma aresta segura?
- Faz-se um corte do do grafo, dividindo-o em dois subgrafos: A′
estara´ contido em um deles.
- A mais leve entre as arestas que cruzam o corte e´ uma aresta segura.
gnramos (CIC/UnB) ED - Grafos 33/45
A´rvore Geradora M´ınima
Algoritmo Gene´rico: Aresta Segura
- V ′ = {0,1,2,3}
- Arestas que cruzam o corte: (1,4),(2,4),(2,5),(3,5)
- Arestas seguras: (2,5) e (3,5).
gnramos (CIC/UnB) ED - Grafos 34/45
A´rvore Geradora M´ınima
Algoritmo de Prim
Entrada: um grafo conectado ponderado com ve´rtices V e arestas A.
1 Inicialize V ′ = {u}, onde u e´ um no´ arbitra´rio de V e A′ = {∅}
2 Repita ate´ que V ′ = V :
2.1 Escolha um arco (u, v) de A com o m´ınimo peso tal que u esteja em
V ′ e v na˜o
2.2 Adicione v a V ′ e (u, v) a A′
Sa´ıda: A′, que descreve a a´rvore geradora m´ınima (junto a V ′ = V ).
gnramos (CIC/UnB) ED - Grafos 35/45
A´rvore Geradora M´ınima
Algoritmo de Prim - Exemplo1
1Imagens de Alexander Drichel
gnramos (CIC/UnB) ED - Grafos 36/45
A´rvore Geradora M´ınima
Algoritmo de Prim - Complexidade
- A complexidade desse algoritmo depende da forma como a escolha
do arco e´ feita.
- Complexidade O(|V |2)
- Usando um vetor ordenado ou a´rvore bina´ria para armazenar os
ve´rtices:
- Ordem e´ definida pelo peso do arco mais leve que liga esse ve´rtice a
qualquer um dos ve´rtices ja´ no subconjunto
- Complexidade: O(|A|log |V |)
gnramos (CIC/UnB) ED - Grafos 37/45
A´rvore Geradora M´ınima
Algoritmo de Kruskal
1 Crie uma floresta F (um conjunto de a´rvores), onde cada ve´rtice no
grafo e´ uma a´rvore separada.
2 Crie um conjunto A′ contendo todas as arestas do grafo.3 Enquanto A′ 6= ∅:
3.1 remova uma aresta com peso m´ınimo de A′
3.2 se essa aresta conecta duas a´rvores diferentes, adicione-a a F ,
combinando duas a´rvores numa u´nica a´rvore parcial
3.3 se na˜o (aresta conecta dois ve´rtices na mesma a´rvore), descarte a
aresta.
Ao fim do algoritmo, a floresta tem apenas um componente e forma uma
a´rvore geradora m´ınima do grafo.
gnramos (CIC/UnB) ED - Grafos 38/45
A´rvore Geradora M´ınima
Algoritmo de Kruskal - Exemplo2
2Imagens de Alexander Drichel
gnramos (CIC/UnB) ED - Grafos 39/45
A´rvore Geradora M´ınima
Algoritmo de Kruskal - Complexidade
Depende de como os arcos sa˜o ordenados:
- O(|A|log |A|)
gnramos (CIC/UnB) ED - Grafos 40/45
Caminhos Mais Curtos
- Muitas das aplicac¸o˜es de grafos necessitam encontrar o caminho
mais curto entre dois ve´rtices de um grafo ponderado
- Busca em largura obte´m o caminho mais curto entre dois ve´rtices,
se todos os arcos tiverem o mesmo peso
- O caminho mais curto entre dois ve´rtice e´ um subgrafo, tal que seus
ve´rtices sa˜o os ve´rtices alcanc¸a´veis do ve´rtice origem, o subgrafo
forma uma a´rvore cuja raiz e´ o ve´rtice origem e para todos os
ve´rtices, o caminho simples da origem ate´ esse ve´rtice e´ o caminho
mais curto
Algoritmo mais utilizado: Dijkstra
gnramos (CIC/UnB) ED - Grafos 41/45
Caminhos Mais Curtos
Algoritmo Djikstra
- Escolhido um ve´rtice como raiz da busca, este algoritmo calcula o
custo m´ınimo deste ve´rtice para todos os demais ve´rtices do grafo.
- O algoritmo pode ser usado sobre grafos orientados, ou na˜o, e
admite que todas as arestas possuem pesos na˜o negativos (nulo e´
poss´ıvel).
gnramos (CIC/UnB) ED - Grafos 42/45
Caminhos Mais Curtos
Algoritmo Djikstra
Seja G (V ,A) um grafo direcionado e v um ve´rtice de G :
1 Atribuic¸a˜o de distaˆncias:
0 ao ve´rtice inicial v ;
∞ aos demais.
2 Marcar todos os ve´rtices como abertos (na˜o visitados) e o inicial
como atual.
3 Para cada ve´rtice aberto adjacente ao atual, atribua a distaˆncia
estimada dele ate´ o no´ inicial. Se a distaˆncia for menor que a
distaˆncia registrada, atualize o valor.
4 Depois de processar todos os no´s aberto adjacentes ao atual,
marque-o como fechado (visitado). Sua distaˆncia e´ final e m´ınima.
5 Escolha o no´ aberto de menor distaˆncia como novo no´ atual e va´
para 3, termine se na˜o houver.
gnramos (CIC/UnB) ED - Grafos 43/45
Caminhos Mais Curtos
Algoritmo Djikstra - Exemplo
f a
g
b
e h c
d fechado
aberto
atual
2
2
2
2
11
1
11
0.5
0.5g
b
(1)
d
h
(0.5)
g h
2
(1)
h
ba
(2)
c
b
d
e
(2)
(2)
2
Atribuic¸a˜o de distaˆncias.Marcar todos os ve´rtices como abertos e g como atual.Atribuir a distaˆncia estimada ate´ o no´ inicial para cada ve´rtice aberto
adjacente, e atualizar a distaˆncia.
Marcar o atual como fechado.Escolher o no´ aberto de menor distaˆncia como novo no´ atual.Atribuir a distaˆncia estimada ate´ o no´ inicial para cada ve´rtice aberto
adjacente, e atualizar a distaˆncia.
Marcar o atual como fechado, escolher o no´ aberto de menor distaˆncia
como novo no´ atual, e atribuir distaˆncias.
Terminar quando na˜o ha´ mais no´s abertos.
gnramos (CIC/UnB) ED - Grafos 44/45
Caminhos Mais Curtos
Algoritmo Djikstra
Complexidade: O(|E |+ |V |log |V |)
Aplicac¸o˜es
- Protocolos de roteamento dinaˆmicos (OSPF, IS-IS).
- Algoritmo Bellman-Ford (grafos direcionados, arestas com peso
negativo).
- Algoritmo A* (planejamento de rota).
- Ana´lise de circuitos ele´tricos.
- Etc.
gnramos (CIC/UnB) ED - Grafos 45/45
	Grafos
	Conceitos e Definições
	Implementação
	Busca
	Ordenamento Topológico
	Árvore Geradora Mínima
	Caminhos Mais Curtos