162
AULA 20

@let@token MAC00323 Algoritmos e Estruturas de Dados II

  • Upload
    others

  • View
    5

  • Download
    0

Embed Size (px)

Citation preview

Page 1: @let@token MAC00323 Algoritmos e Estruturas de Dados II

AULA 20

Page 3: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DigrafosUm digrafo (directed graph) consiste de umconjunto de vértices (bolas) e um conjunto de arcos(flechas)Exemplo: representação de um digrafo

b d

f

c

a

e

Page 4: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ArcosUm arco é um par ordenado de vérticesExemplo: v e w são vértices e v-w é um arco

v d

f

c

a

w

Page 5: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Ponta inicial e finalPara cada arco v-w, o vértice v é a ponta inicial ew é a ponta finalExemplo: v é ponta inicial e w é ponta final de v-w

v w

a

v

c w

f

d

Page 6: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Arcos anti-paralelosDois arcos são anti-paralelos se a ponta inicial deum é ponta final do outroExemplo: v-w e w-v são anti-paralelos

w

f

dv

a

c

Page 7: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digrafos simétricosUm digrafo é simétrico se cada um de seus arcos éanti-paralelo a outroExemplo: digrafo simétrico

e

f

db

a

c

Page 8: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Graus de entrada e saídagrau de entrada de v= no. arcos com pontafinal vgrau de saída de v = no. arcos com ponta inicial v

Exemplo: v tem grau de entrada 1 e de saída 2

v d

f

c

a

e

Page 9: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Número de arcos

Quantos arcos, no máximo, tem um digrafo com Vvértices?

A resposta é V × (V − 1) = Θ(V2)

digrafo completo = todo par ordenado de vérticesdistintos é arco

digrafo denso = tem “muitos” muitos arcosdigrafo esparso = tem “poucos” arcos

Page 10: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Número de arcos

Quantos arcos, no máximo, tem um digrafo com Vvértices?A resposta é V × (V − 1) = Θ(V2)

digrafo completo = todo par ordenado de vérticesdistintos é arco

digrafo denso = tem “muitos” muitos arcosdigrafo esparso = tem “poucos” arcos

Page 11: @let@token MAC00323 Algoritmos e Estruturas de Dados II

EspecificaçãoDigrafos podem ser especificados através de sualista de arcosExemplo:

b d

f

c

a

e

d-fb-da-cb-ee-fa-b

Page 13: @let@token MAC00323 Algoritmos e Estruturas de Dados II

GrafosUm grafo é um digrafo simétricoExemplo: um grafo

e

f

db

a

c

Page 14: @let@token MAC00323 Algoritmos e Estruturas de Dados II

GrafosUm grafo é um digrafo simétricoExemplo: representação usual

e

f

db

a

c

Page 15: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ArestasUma aresta é um par de arcos anti-paralelos.Exemplo: b-a e a-b são a mesma aresta

e

f

db

a

c

Page 16: @let@token MAC00323 Algoritmos e Estruturas de Dados II

EspecificaçãoGrafos podem ser especificados através de sua listade arestasExemplo:

e

f

db

a

c

f-db-dc-ae-be-fa-b

Page 17: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Graus de vérticesEm um grafograu de v = número de arestas com ponta em v

Exemplo: v tem grau 3

e

f

dv

a

c

Page 18: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Número de arestas

Quantas arestas, no máximo, tem um grafo com Vvértices?

A resposta é V × (V − 1)/2 = Θ(V2)

grafo completo = todo par não-ordenado devértices distintos é aresta

Page 19: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Número de arestas

Quantas arestas, no máximo, tem um grafo com Vvértices?A resposta é V × (V − 1)/2 = Θ(V2)

grafo completo = todo par não-ordenado devértices distintos é aresta

Page 20: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digrafos no computador

Fonte: GraphX Programming Guide

Page 21: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Matriz de adjacência de digrafos

Matriz de adjacência de um digrafo tem linhas ecolunas indexadas por vértices:

adj[v][w] = 1 se v-w é um arcoadj[v][w] = 0 em caso contrário

Exemplo:

0

1

2 3

0 1 2 30 0 1 1 01 0 0 0 12 0 1 0 13 0 0 0 0

Consumo de espaço: Θ(V2) fácil de implementar

Page 22: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Matriz de adjacência de grafos

Matriz de adjacência de um grafo tem linhas ecolunas indexadas por vértices:

adj[v][w] = 1 se v-w é um arestaadj[v][w] = 0 em caso contrário

Exemplo:

0

1

2 3

0 1 2 30 0 1 1 01 1 0 1 12 1 1 0 13 0 1 1 0

Consumo de espaço: Θ(V2) fácil de implementar

Page 23: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digrafo

Digraph G

0

2

4

3 5

1

Page 24: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Estruturas de dados

0 00

0 0 0

0 0 0 0

5

5

0

0 0 0 0

0 0

0 0 0 0 0

0 0

1 1 1

1

11

1

1

1 1

0

0

1 432001234

A

Page 25: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digrafos no algs4

Page 26: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Matriz de incidência de digrafosUma matriz de incidências de um digrafo temlinhas indexadas por vértices e colunas por arcos ecada entrada [k][vw] é −1 se k = v, +1 se k = w,e 0 em caso contrário.

0

1

2 3

0-1 0-2 2-1 2-3 1-30 -1 -1 0 0 01 +1 0 +1 0 -12 0 +1 -1 -1 03 0 0 0 +1 +1

Consumo de espaço: Θ(nm)Interessante do ponto de vista de otimização linear.

Page 27: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Vetor de listas de adjacência de digrafos

Na representação de um digrafo através de listasde adjacência tem-se, para cada vértice v, umalista dos vértices que são vizinhos v.Exemplo:

0

1

2 3

0: 1, 21: 32: 1, 33:

Consumo de espaço: Θ(V + A) (linear)Manipulação eficiente

Page 28: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Vetor de lista de adjacência de grafos

Na representação de um grafo através de listas deadjacência tem-se, para cada vértice v, uma listados vértices que são pontas de arestas incidentes a v

Exemplo:

0

1

2 3

0: 1, 21: 3, 0, 22: 1, 3, 03: 1, 2

Consumo de espaço: Θ(V + A) (linear)Manipulação eficiente

Page 29: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digrafo

Digraph G

0

2

4

3 5

1

Page 30: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Estruturas de dados

5

5

5

6

10

0123

G VAadj

2 3 4

14

4

14 1

Page 31: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Grafos no algs4

Page 32: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Esqueleto da classe Digraphpublic class Digraph {

private int V; // no. vérticesprivate int E; // no. arcosprivate Bag<Integer>[] adj;private int[] indegree;public Digraph(int V) {...}public int V() { return V; }public int E() { return E; }public void addEdge(int v, int w) { }public Iterable<Integer> adj(intv) { }public int outdegree(int v) {...}public int indegree(int v) {...}public Digraph reverse() { ...}

}

Page 33: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digraph

public Digraph(int V) {this.V = V;this.E = 0;indegree = new int[V];adj = (Bag<Integer>[]) new Bag[V];for (int v = 0; v < V; v++) {

adj[v] = new Bag<Integer>();}

}

Page 34: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digraph

// insere um arcopublic void addEdge(int v, int w) {

adj[v].add(w);indegree[w]++;E++;

}

// retorna a lista de adjacência de vpublic Iterable<Integer> adj(int v) {

return adj[v];}

Page 35: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digraph

// retorna o grau de saída de vpublic int outdegree(int v) {

return adj[v].size();}// retorna o grau de entrada de vpublic int indegree(int v) {

return indegree[v];}

Page 36: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Digraph

// retorna o sigrafo reversopublic Digraph reverse() {

Digraph reverse = new Digraph(V);for (int v = 0; v < V; v++) {

for (int w : adj(v)) {reverse.addEdge(w, v);

}}return reverse;

}

Page 37: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminhos em digrafos

Fonte: Finding Your Way & Making You A Priority

Page 38: @let@token MAC00323 Algoritmos e Estruturas de Dados II

CaminhosUm caminho num digrafo é qualquer seqüência daforma v0–v1–v2–...–vk−1–vp, onde vk−1-vk é umarco para k = 1, . . . , p.Exemplo: 2-4-1-3-5-4-5 é um caminho com origem2 é término 5

0

1 3

5

42

Page 39: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminhos simplesUm caminho é simples se não tem vérticesrepetidosExemplo: 2-4-1-3-5 é um caminho simples de 2 a 5

0

3

5

4

1

2

Page 40: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Procurando caminhos

Fonte: Mincecraft maze created by Carl Eklof(algs4)

Page 41: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Procurando um caminhoProblema: dados um digrafo G e dois vértices s e tdecidir se existe um caminho de s a t

Exemplo: para s = 0 e t = 1 a resposta é SIM

0

2

3 5

1

4

Page 42: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Procurando um caminhoProblema: dados um digrafo G e dois vértices s e tdecidir se existe um caminho de s a t

Exemplo: para s = 0 e t = 1 a resposta é SIM

0

2 1

53

4

Page 43: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Procurando um caminhoProblema: dados um digrafo G e dois vértices s e tdecidir se existe um caminho de s a t

Exemplo: para s = 5 e t = 4 a resposta é NÃO

0

2

3 5

1

4

Page 44: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpathsA classe DFSpaths recebe um digrafo G e umvértice s e determina todos os vértices alcançáveis apartir de s.A classe implementa a técnica chamada busca emprofundidade (Depth First Search).

public class DFSpaths{public void DFSpaths(Digraph G,int s){}

// retorna true se há caminho de s a vpublic boolean hasPath(int v){ ...}

private void dfs(Digraph G, int v) { }}

Page 45: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 0)

0

12

3 5

4

Page 46: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 0)

0

12

3 5

4

Page 47: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 48: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 49: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 50: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 51: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 1)

0

12

3 5

4

Page 52: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 53: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 54: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 55: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 56: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 57: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 5)

0

12

3 5

4

Page 58: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 5)

0

12

3 5

4

Page 59: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 5)

0

12

3 5

4

Page 60: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 61: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 62: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 63: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 64: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 3)

0

12

3 5

4

Page 65: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 3)

0

12

3 5

4

Page 66: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 3)

0

12

3 5

4

Page 67: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 3)

0

12

3 5

4

Page 68: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 69: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 70: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 0)

0

12

3 5

4

Page 71: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 0)

0

12

3 5

4

Page 72: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 2)

0

12

3 5

4

Page 73: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 2)

0

12

3 5

4

Page 74: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 75: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 76: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 1)

0

12

3 5

4

Page 77: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 78: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 79: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 80: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 81: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 82: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 5)

0

12

3 5

4

Page 83: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 5)

0

12

3 5

4

Page 84: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 5)

0

12

3 5

4

Page 85: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 4)

0

12

3 5

4

Page 86: @let@token MAC00323 Algoritmos e Estruturas de Dados II

dfs(G, 2)

0

12

3 5

4

Page 87: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 2)

0

12

3 5

4

Page 88: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths

public class DFSpaths {

private final int s;

private boolean[] marked;

public DFSpaths(Digraph G, int s) {}

private void dfs(Digraph G, int v) {}

public boolean hasPath(int v) {}

}

Page 89: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths

Encontra um caminho de s a todo vérticealcançável a partir de s.

public DFSpaths(Digraph G, int s) {marked = new boolean[G.V()];this.s = s;dfs(G, s);

}

Page 90: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths

private void dfs(Digraph G, int v) {marked[v] = true;for (int w : G.adj(v)) {

if (!marked[w]) {dfs(G, w);

}}

}

Page 91: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths

Há um caminho de s a v?

public boolean hasPath(int v) {return marked[v];

}

Page 92: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 0)

0

2

4

3 5

10-2 dfs(G,2)

2-1 dfs(G,1)2-4 dfs(G,4)

4-14-5 dfs(G,5)

5-10-3 dfs(G,3)

3-43-5

0-4existe caminho

Page 93: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths(G, 2)

0

2

4

3 5

12-1 dfs(G,1)2-4 dfs(G,4)

4-14-5 dfs(G,5)

5-1nao existe caminho

Page 94: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Consumo de tempo

Qual é o consumo de tempo de DFSpaths?

Qual é o consumo de tempo da função dfs?

Page 95: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Consumo de tempo

Qual é o consumo de tempo de DFSpaths?Qual é o consumo de tempo da função dfs?

Page 96: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Conclusão

O consumo de tempo de DFSpaths é Θ(V) maiso consumo de tempo da função dfs().

Page 97: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Conclusão

O consumo de tempo da função dfs() paravetor de listas de adjacência é O(V + E).

O consumo de tempo de DFSpaths para vetorde listas de adjacência é ∼ O(V + E).

Page 98: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Conclusão

O consumo de tempo da função dfs() paramatriz de adjacências é O(V2).

O consumo de tempo de DFSpaths para matrizde adjacências é O(V2).

Page 99: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminhos no computador

Fonte: Tron Legacy Light Cycle Riders wallpaper

Page 100: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminhos no computador

Como representar caminhos no computador?

Page 101: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminhos no computador

Uma maneira compacta de representar caminhosde um vértice a outros é uma arborescênciaUma arborescência é um digrafo em que

I existe exatamente um vértice com grau deentrada 0, a raiz da arborescência

I não existem vértices com grau de entradamaior que 1,

I cada um dos vértices é término de um caminhocom origem no vértice raiz.

Page 102: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ArborescênciasExemplo: a raiz da arborescência é 0

0

12

3 5

4

Page 103: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ArborescênciasExemplo: a raiz da arborescência é 0

0

12

3 5

4

Page 104: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ArborescênciasPropriedade: para todo vértice v, existe exatamenteum caminho da raiz a v

0

12

3 5

4

Page 105: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ArborescênciasTodo vértice w, exceto a raiz, tem uma pai: oúnico vértice v tal que v-w é um arco

0

12

3 5

4

Page 106: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Arborescências no computadorUm arborescência pode ser representada através deum vetor de pais: edgeTo[w] é o pai de wSe r é a raiz, então edgeTo[r]=r

0

12

3 5

4

vértice edgeTo0 01 22 03 04 25 4

Page 107: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminho

Dado o vetor de pais, edgeTo, de umaarborescência, é fácil determinar o caminho que levada raiz a um dado vértice v: basta inverter asequência impressa pelo seguinte fragmento decódigo:

for (int x=v; edgeTo[x]!=x; x=edgeTo[x])StdOut.printf("%d-", x);

StdOut.printf("%d", x);

Page 108: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Caminho

Dado o vetor de pais, edgeTo, de umaarborescência, é fácil determinar o caminho que levada raiz a um dado vértice v: basta inverter asequência impressa pelo seguinte fragmento decódigo:

for (int x=v; edgeTo[x]!=x; x=edgeTo[x])StdOut.printf("%d-", x);

StdOut.printf("%d", x);

Page 109: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths: esqueleto

public class DFSpaths {

private final int s;

private boolean[] marked;

private int[] edgeTo;

public DFSpaths(Digraph G, int s) {}

private void dfs(Digraph G, int v) {}

public boolean hasPath(int v) {}

public Iterable<Integer> pathTo(int v)}

Page 110: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths: construtor

Encontra um caminho de s a todo vérticealcançável a partir de s.

public DFSpaths(Digraph G, int s) {marked = new boolean[G.V()];edgeTo = new int[G.V()];this.s = s;dfs(G, s);

}

Page 111: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths: dfs()

private void dfs(Digraph G, int v) {marked[v] = true;for (int w : G.adj(v)) {

if (!marked[w]) {edgeTo[w] = v;dfs(G, w);

}}

}

Page 112: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpaths: pathTo()

Retorna um caminho de s a v ou null se um talcaminho não existe.

public Iterable<Integer> pathTo(int v) {if (!hasPath(v)) return null;Stack<Integer> path =

new Stack<Integer>();for (int x = v; x != s; x = edgeTo[x])

path.push(x);path.push(s);return path;

}

Page 113: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Busca em largura

Fonte: http://catalog.flatworldknowledge.com/bookhub/

Page 114: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Busca ou varredura

Um algoritimo de busca (ou varredura) examina,sistematicamente, os vértices e os arcos de umdigrafo.

Cada arco é examinado uma só vez.Depois de visitar sua ponta inicial o algoritmopercorre o arco e visita sua ponta final.

Page 115: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Busca em largura

A busca em largura (=breadth-first search search= BFS) começa por um vértice, digamos s,especificado pelo usuário.O algoritmo

visita s,depois visita vértices à distância 1 de s,depois visita vértices à distância 2 de s,depois visita vértices à distância 3 de s,e assim por diante

Page 116: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i]

0

12

3 5

4

Page 117: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i]

0

12

3 5

4

Page 118: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0

0

12

3 5

4

Page 119: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0

0

12

3 5

4

Page 120: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2

0

12

3 5

4

Page 121: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3

0

12

3 5

4

Page 122: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4

0

12

3 5

4

Page 123: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4

0

12

3 5

4

Page 124: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4

0

12

3 5

4

Page 125: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4

0

12

3 5

4

Page 126: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4

0

12

3 5

4

Page 127: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5

0

12

3 5

4

Page 128: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5

0

12

3 5

4

Page 129: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5

0

12

3 5

4

Page 130: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5

0

12

3 5

4

Page 131: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5 1

0

12

3 5

4

Page 132: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5 1

0

12

3 5

4

Page 133: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5 1

0

12

3 5

4

Page 134: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5 1

0

12

3 5

4

Page 135: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Simulaçãoi 0 1 2 3 4 5

q[i] 0 2 3 4 5 1

0

12

3 5

4

Page 136: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Arborescência da BFSA busca em largura a partir de um vértice sdescreve a arborescência com raiz s

0

12

3 5

4

Page 137: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Arborescência da BFSEssa arborescência é conhecida comoarborescência de busca em largura (= BFS tree)

0

12

3 5

4

Page 138: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Representação da BFSPodemos representar essa arborescênciaexplicitamente por um vetor de pais edgeTo[]

0

12

3 5

4

Page 139: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Representação da BFSv 0 1 2 3 4 5

edgeTo 0 5 0 0 0 3

0

12

3 5

4

Page 140: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Class BFSpaths

BFSpaths visita todos os vértices do digrafo G quepodem ser alcançados a partir de s.

A visita aos vértices é registrada no vetormarked[]. Se v foi então marked[v] == true.

Para isso BFSpaths usa uma fila de vértices:

Queue<Integer> q = new Queue<Integer>();

Page 141: @let@token MAC00323 Algoritmos e Estruturas de Dados II

BFSpaths: esqueleto

public class BFSpaths {private final int s;private boolean[] marked;private int[] edgeTo;public BFSpaths(Digraph G, int s) {}private void bfs(Digraph G, int s) {}public boolean hasPath(int v) {}public Iterable<Integer> pathTo(int v)

}

Page 142: @let@token MAC00323 Algoritmos e Estruturas de Dados II

BFSpaths

Encontra um caminho de s a todo vérticealcançável a partir de s.

public BFSpaths(Digraph G, int s) {marked = new boolean[G.V()];edgeTo = new int[G.V()];this.s = s;bfs(G, s);

}

Page 143: @let@token MAC00323 Algoritmos e Estruturas de Dados II

bfs(): inicializações

private void bfs(Digraph G, int s) {

Queue<Integer> q= new Queue<Integer>();marked[v] = true;q.enqueue(s);

// aqui vem a iteração do próximo slide

Page 144: @let@token MAC00323 Algoritmos e Estruturas de Dados II

bfs(): iteração

while (!q.isEmpty()) {int v = q.dequeue();for (int w : G.adj(v)) {

if (!marked[w]) {edgeTo[w] = v;marked[w] = true;q.enqueue(w);

}}

}}

Page 145: @let@token MAC00323 Algoritmos e Estruturas de Dados II

BFSpaths

Há um caminho de s a v?

// Método copiado de DFSpaths.public boolean hasPath(int v) {

return marked[v];}

Page 146: @let@token MAC00323 Algoritmos e Estruturas de Dados II

BFSpathsRetorna um caminho de s a v ou null se um talcaminho não existe.

// Método copiado de DFSpaths.public Iterable<Integer> pathTo(int v) {

if (!hasPath(v)) return null;Stack<Integer> path =

new Stack<Integer>();for (int x = v; x != s; x = edgeTo[x])

path.push(x);path.push(s);return path;

}

Page 147: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Relações invariantes

Digamos que um vértice v foi visitado semarked[v] == true

No início de cada iteração vale queI todo vértice que está na fila já foi visitado;I se um vértice v já foi visitado mas algum deseus vizinhos ainda não foi visitado, então vestá na fila.

Cada vértice entra na fila no máximo uma vez.Portanto, basta que a fila tenha espaço suficientepara G.V() vértices.

Page 148: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Consumo de tempo

O consumo de tempo da função BFSpaths paravetor de listas de adjacência é O(V + E).

O consumo de tempo da função BFSpathsparamatriz de adjacência é O(V2).

Page 149: @let@token MAC00323 Algoritmos e Estruturas de Dados II

BFS versus DFSI busca em largura usa fila, busca emprofundidade usa pilha

I a busca em largura é descrita em estiloiterativo, enquanto a busca em profundidade édescrita, usualmente, em estilo recursivo

I busca em largura começa tipicamente numvértice especificado, a busca emprofundidade, o próprio algoritmo escolhe ovértice inicial

I a busca em largura apenas visita os vérticesque podem ser atingidos a partir do vérticeinicial, a busca em profundidade, tipicamente,visita todos os vértices do digrafo

Page 150: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Certificados

Achievement Certificate

_________________________________________________________

is presented with the

Computer Achievement Award

On the _______ Day of __________ In the Year _______.

Signed,

____________________________

Certificate Provided by www.hooverwebdesign.com

Fonte: Free Printable Computer Achievement AwardCertificates

Page 151: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Procurando um caminhoProblema: dados um digrafo G e dois vértices s e tdecidir se existe um caminho de s a t

Exemplo: para s = 0 e t = 1 a resposta é SIM

0

2

3 5

1

4

Page 152: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Certificados

Como é possível ’verificar’ a resposta?

Como é possível ’verificar’ que existe caminho?

Como é possível ’verificar’ que não existe caminho?

Veremos questões deste tipo freqüentementeElas terão um papel suuupeeer importante no finalde MAC0338 Análise de Algoritmos e em MAC0414Autômatos, Computabilidade e ComplexidadeElas estão relacionadas com o Teorema daDualidade visto em MAC0315 Otimização Linear

Page 153: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Certificados

Como é possível ’verificar’ a resposta?

Como é possível ’verificar’ que existe caminho?

Como é possível ’verificar’ que não existe caminho?

Veremos questões deste tipo freqüentementeElas terão um papel suuupeeer importante no finalde MAC0338 Análise de Algoritmos e em MAC0414Autômatos, Computabilidade e ComplexidadeElas estão relacionadas com o Teorema daDualidade visto em MAC0315 Otimização Linear

Page 154: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Certificado de inexistênciaComo é possível demonstrar que o problema nãotem solução?

0

2

4

3 5

1 dfs(G,2)2-1 dfs(G,1)2-4 dfs(G,4)

4-14-5 dfs(G,5)

5-1nao existe caminho

Page 155: @let@token MAC00323 Algoritmos e Estruturas de Dados II

DFSpath(G,2,3)

0

12

3 5

4

Page 156: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Cortes (= cuts)Um corte é uma bipartição do conjunto de vérticesUm arco pertence ou atravessa um corte (S, T) setiver uma ponta em S e outra em T

Exemplo 1: arcos em vermelho estão no corte (S, T)

0

12

3 5

S

4

T

Page 157: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Cortes (= cuts)Um corte é uma bipartição do conjunto de vérticesUm arco pertence ou atravessa um corte (S, T) setiver uma ponta em S e outra em T

Exemplo 2: arcos em vermelho estão no corte (S, T)

0

12

3 5

4

S

T

Page 158: @let@token MAC00323 Algoritmos e Estruturas de Dados II

st-Cortes (= st-cuts)Um corte (S, T) é um st-corte se

s está em S e t está em T

Exemplo: (S, T) é um 1-3-corte um 2-5-corte . . .

0

12

3 5

S

4

T

Page 159: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Certificado de inexistência

Para demonstrarmos que não existe um caminhode s a t basta exibirmos um st-corte (S, T) em que

todo arco no corte tem ponta inicial emT e ponta final em S

Page 160: @let@token MAC00323 Algoritmos e Estruturas de Dados II

Certificado de inexistênciaExemplo: certificado de que não há caminho de 2a 3

0

12

3 5

4

S

T

Page 161: @let@token MAC00323 Algoritmos e Estruturas de Dados II

ConclusãoPara quaisquer vértices s e t de um digrafo, valeuma e apenas umas das seguintes afirmações:

I existe um caminho de s a tI existe st-corte (S, T) em que todo arco nocorte tem ponta inicial em T e ponta finalem S.

Fonte: Yin and yang (Wikipedia)

Page 162: @let@token MAC00323 Algoritmos e Estruturas de Dados II

E DFSpaths e BFSpaths com isso?

No código das classes DFSpaths e BFSpaths seexiste um caminho de s a t ele esta representado novetor edgeTo[].

No código da classes DFSpaths e BFSpaths se nãoexiste um caminho de s a t um st-corte separandos de t está representado no vetor marked[].

Em ambos os casos podemos fazer um trecho decódigo que verifica a resposta em tempoproporcional a V + E.