h2 Grafos e Árvores: Estruturas de Dados e Algoritmos

• Grafo

Estrutura independente de dados

G = {D, R}

D = conjunto de dados, também chamados de vértices

R = conjunto de pares {i, j} tal que i, j pertencem ao conjunto D – também chamado de conj. de relacionamentos ou conj. de arestas.

Número máximo de arestas = d², onde d = |D| e d(d-1)/2 num grafo simplificado.

- Custo matriz x lista

- Aplicações

Vários tipos de problemas: distribuição/logística, torneios, alocação de dados, web (crawling), rede de dados e comunicação, fluxo de usabilidade,...

- Simplificações

Há apenas uma aresta ligando o mesmo par de vértices, arestas ligam sempre pares diferentes de vértices, facilita a expressão das propriedades sobre grafos, na maioria das vezes representam a realidade das aplicações mais comuns

- Densidade: relação entre |R| e |D|

Denso quando |R| se aproxima de |D|²

Determina grau médio de um vértice = 2|A|/|V|

- Matriz de incidência

typedef struct par{int i;int j;} par;

struct grafo{int D;int R.int**matInc;} ;

typedef struct grafo *Grafo;

par Par(int I,int j){par p={I,j};return p;}

Grafo iniciaGrafo(int D){

Grafo G = malloc(sizeof *G);

G->D=D;G->R=0;

G->matInc=iniciaMatriz(D,D,0);

return G;

}

int **iniciaMatriz(int lin,int col,int val){

int I,j;

int **ret=malloc(lin*sizeof(int *));

for(i=0;i

for(i=0;i

return ret;

}

void insereRelacionamento(Grafo G,par r){

int i=r.i,j=r.j;

if(!(G->matInc[i][j])){ G->R++; G->matInc[i][j]=+1; G->matInc[j][i]=-1; }

}

Int listaDeRelacionamentos(par almp[],Grafo G){ int i,j,R=0;

for(i=0;iD;i++) for(j=v+1;jD;j++) if(G->matInc[i][j]) almp[R++]=Par(I,j); return R;

}

- Lista de adjacências

Imagine uma lista encadeada. Em substituição ao nó “prox” teríamos uma lista indicando os nós adjacentes ao nó corrente.

typedef struct noh *ligação;

struct noh{int D;ligação próximo;};

typedef struct grafo *Grafo;

struct grafo{int D;int R;ligacao adj;}

Grafo iniciaGrafo(int D){ int d;

Grafo G=malloc(sizeof*G);

G->D=D;G->R=0;

G->adj=malloc(D*sizeof(ligacao));

for(d=0;dadj[d]=NULL;

return G;

}

void insereRelacionamento(Grafo G,par p){ int i=e.i,j=e.j;

G->adj[i]=novoRel(j,G->adj[i]); G->adj[j]=novoRel(i,G->adj[j]); G->R++;

}

ligação novoRel(int aRel,ligação proximo){ ligacao x=malloc(sizeof ligacao); x->D=aRel;x->proximo=proximo; return x;

}

int listaRelacionamentos(par list[],Grafo G){ int i,R=0;

ligação r;

for(i=0;iD;i++) for(r=G->adj[i];r!=NULL;r=r->proximo) if(ii) list[R++]=Par(i,r->D); return R;

}

- Percorrendo grafos por largura

: a partir de um vértice i qualquer, marque-o como visitado, coloque todos os vértices de i numa fila, marcando-os. Remova um vértice j da fila e coloque todos os vértices adjacentes a j, não visitados, na fila, marcando-os. A busca termina quando a fila estiver vazia.

void percorreLargura(int r){

ligação l;

iniciaFila(numDados); colocaFila(r);

while(!filaVazia()) if(!visitado[r=desenfileira()]){ visitado[r]=1; for(l=adj[r];l!=NULL;l->l->proximo) if(!(visitado[l->D])) colocaFila(l->D); }

}

- Percorrendo grafos por profundidade

: a partir de um vértice qualquer, marque-o como visitado, tome um vertice j qualquer, adjacente a i que ainda não foi visitado, marque-o como visitado e repita o procedimento. Quando todos os vértices tiverem sido visitados retorne ao vértice anterior e transforme-o em corrente, repetindo o procedimento.

void percorreProfundidade(Grafo G,int r,int *matVisitado){

ligacao l;

matVisitado[r]=1;

for(l=G->adj[r];l!=NULL;l=l->proximo) if(!visitado[l->D]) percorreProfundidade(l->D,matVisitado);

}

- Determinando caminho

Seja G={D,R}

1-Alcance k pertencente a D tal que k é adjacente a i

2-Se k==j,existe um caminho

3-Caso contrario: se k já foi visitado vá para 1, caso contrario faça k ser um novo i e vá para o passo 1

static int visitado[maxD];

int caminhoGrafo(Grafo G,int i,int j){

int t;

for(t=0;tD;t++) visitado[t]=0;

return caminhoR(G,i,j);

}

int caminhoR(Grafo G,int i,int j){

int t;

if(i==j) return 1;

visitado[i]=1;

for(t=0;tD;t++) if(G->adj[i][t]==1) if(visitado[t]==0) IF(caminhoR(G,t,j)) return 1;

return 0;

}

Caminho mais longo – gerencia de projetos

Caminho mais curto – logística

- Caminho mais longo

Grafo de precedência de tarefas: orientado; vértices=inicio/término de uma tarefa;arestas=tarefas;dados 2 vértices i e j há apenas uma aresta de i para j.

Representa o menor tempo de conclusão do projeto

- Caminho crítico

Caminho formado pelas tarefas que não podem sofrer atraso

- Caminho mais curto

Algoritmo deDijkstra: restrito a grafos dirigidos, par(i,j) tem custo > 0.

Algoritmo A*

void dijkistraPath(int r)//prepara as estruturas e chama o algoritmo recursivo dijikstra{

int i;

perm = (int*)malloc(g->V*sizeof(int));

dist = (int*)malloc(g->V*sizeof(int));

path = (int*)malloc(g->V*sizeof(int)

for(i=0; iV; i++){ perm[i] = 0; dist[i] = INT_MAX; path[i] = -1;}

dist[r] = 0;

dijkistraAlg(r);}

void dijkistraAlg(int r)//calcula o menor caminho entre o vértice r e todos os outros vértices do grafo

{

int i; int menor; link t; perm[r] = 1;

if(g->adj[r]==NULL) return;

for(t=g->adj[r]; t!=NULL; t=t->next){ if(dist[t->v] > (dist[r] + t->value)){ dist[t->v] = dist[r] + t->value; path[t->v] = r;}}

menor = -1;

for(i=0; iV; i++){ if(!perm[i]){ menor = i; break;}}

if(menor==-1) return;

for(i=0; iV; i++){ if(!perm[i] && dist[i]menor = i;}

dijkistraAlg(menor);}

- Caminho de Hamilton

Seja G={D,P}, há um caminho simples que conecta i,j em D tal que para todo k pertencente a P, k é visitado apenas uma vez? Se houver, temos o caminho de Hamilton. Se o caminho retornar ao vértice inicial temos o ciclo de Hamilton.

- Caminho de Euler

Seja G={D,P}, há um caminho simples que passe por (i,j) pertencente a D apenas uma vez? Se houver, temos o caminho de Euler. Se o caminho retornar ao vértice inicial temos o ciclo de Euler.

- Árvore geradora mínima

Seja G={D,P} e H={U,B} um subgrafo de G tal que U=D e B está contido ou é igual a P tal que para todo i e j pertencentes a U i é alcançável e há apenas um caminho entre os vértices i e j. Isso me fornece uma árvore gerado mínima(Minimal Spanning Tree).

• Árvores

Grafo A={N,F}

N=nós, os dados das árvores

F=filhos, pares de relacionamentos (i,j) tais que i e j pertençam a N

F não produz nenhum ciclo

A é um grafo conectado acíclico, isto é, sempre há um caminho entre i e j pertencentes a N e esse caminho é único.

Um conjunto de nós tal que: raiz (nó que não possui ancestrais), subárvore(árvore cujo nó raiz é descendente do nó correntemente processado),filhos ou descendentes(nós diretamente acessíveis ao nó raiz), folhas(nós que não possuem descendentes).

Utilização: genealogia, representação de estruturas de equações matemáticas, sistema de arquivos, organização de cena 3D, IA, etc.

- Nível de um nó

Distância entre um nó e a raiz

Raiz = nível 0, filhos da raiz = nível 1

Nós irmãos: nós que compartilham o mesmo pai.

- Altura ou profundidade de uma árvore

Definida pelo nó de nível mais alto

- Nó interno: nó que possui pai e filhos

- Grau de um nó: número de filhos do nó

- Grau de uma árvore: definido pelo nó de maior grau

typedef struct no{

struct no *filhos;

char dado;

} no;

typedef no *arvore;

- Árvore binária: árvore de grau 2, pode ou não ser ordenada, filhos são chamados de sub-árvore à esquerda ou à direita, sempre preenche-se da esquerda para a direita.

typedef struct no{

struct no *esquerda;

struct no *direita;

char dado;

} no;

typedef no *arvore_binaria;

Árvores binárias são usadas em expressões matemáticas e estrutura de busca e ordenação.

- Árvore de expressão (matemática)

Notação polonesa

*+/-9 1 2 2 *+ 2 2 3

Notação polonesa inversa

9 1 – 2 / 2 + 2 2 + 3 *

Notação normal

(((9-1)/2)+2)*((2+2)*3)

- Percorrendo árvores binárias

void percorre_prefixa(arvore raiz){

processa_dado(raiz->dado);

processa_prefixa(raiz->esquerda);

percorre_prefixa(raiz->direita);

}

void percorre_posfixa(arvore raiz){

percorre_posfixa(raiz->esquerda);

percorre_posfixa(raiz->direita);

processa_dado(raiz->dado);

}

void percorre_infixa(arvore raiz){

percorre_infixa(raiz->esquerda);

processa_dado(raiz->dado);

percorre_infixa(raiz->direita);

}

3 formas de se recuperar os dados

Prefixa: dado recuperado antes de processar as sub-árvores, logo na 1ª visita ao nó.

Infixa: dado recuperado após o processamento da sub-árvore à esquerda, na 2ª visita ao nó.

Pós-fixa: dado recuperado após o processamento de ambas as sub-árvores, na saída do nó.

- Árvores binárias de busca

: árvore binária com a seguinte propriedade:

Dados menores que o armazenado no nó – armazenado na sub-árvore à esquerda do nó

Dados maiores que o armazenado no nó – armazenado na sub-árvore à direita do nó

- Inserção

Insere_ordenado(raiz,dado){

Se dado>raiz->dado

Se raiz->direita == null

raiz->direita = nova_arvore(dado)

Senão insere_ordenado(raiz->direita,dado)

Senão

Se raiz->esquerda == null

Raiz->esquerda=nova_arvore(dado)

Senão insere_ordenado(raiz->esquerda,dado)

- Remoção

Algoritmo iterativo-recursivo

Iterativo: busca do maior valor menos que o nó e substituição do valor

Recursivo: remoção do nó encontrado no passo anterior

Remove_noh(noh){

noh maiormenorquedado = noh->esquerda;

se(maiormenorquedado==null)

se(noh->direita==null) libera_memória;

senão

arvore a_remover=noh

noh=noh->direita;

Enquanto(maiormenorquedado->direita!=null)

maiormenosquedado=maiormenorquedado->direita

noh->dado=maiormenorquedado->dado

Se(maiormenorquedado->esquerda!=null)

Remove_noh(maiormenorquedado)

}

- Árvores binárias com restrições

Dados menores que o da raiz na sub-árvore á esquerda

Dados maiores que o da raiz na sub-árvore à direita

Objetiva facilitar/acelerar a busca de dados

- Árvores binárias balanceadas

Mantêm as regras das árvores binárias de busca: maiores à direita e menores à esquerda

Apresentam outras restrições que demandam mecanismos para garanti-las: profundidade relativa da árvore (árvores AVL), largura relativa da árvore (árvores vermelho-preto)

-Árvores binárias balanceadas – AVL

Diferença entre profundidades das sub-árvores esquerda-direita não deve exceder 1

Caso exceda há necessidade de se “reconfigurar” a árvore

É necessário um método para o cálculo da diferença das profundidades

Métodos importantes: calculo da profundidade, “rotação” à esquerda, “rotação” à direita

- Cálculo de nível de profundidade de um nó

Profundidade de um nó é igual ao nível mais alto de seu descendente a partir dele.

Cálculo recursivo

profundidade(no){

prof_esq=1;

prof_dir=1;

se no->esq!=null

prof_esq=1+profundidade(no->esquerda)

se no->dir!=null

prof_dir=1+profundidade(no->direita)

return Max(prof_dir,prof_esq)

}

- Balanceamento de um nó

Diferença entre profundidade da sub-árvore à esquerda e a sub-árvore à direita

Deve ser sinalizado

Negativo = pende à esquerda

Positivo = pende à direita

Manter o processo de busca de dados com complexidade O(log n)

Nó com balanço maior que 1 ou menor que -1 deve ser ajustado

Int balance(no)

return profundidade(no->direita)-profundidade(no->esquerda)

struct node{

struct node *left;

struct node *reight;

int dado;

int profundidade;

}

A cada operação de inserção/remoção é necessária a verificação e o cálculo do balanceamento da árvore

- Mecanismos de balanceamento

Rotação simples: esquerda (LL), direita (RR)

Rotação dupla: esquerda-direita (LR) (ou dupla esquerda), direita-esquerda (RL) (ou dupla direita)

- Rotação simples à esquerda (LL)

Ocorre quando o balanceamento do nó tende à direita:

quando o sinal é positivo. E quando o balanceamento do nó á direita tende à direita: quando o sinal é positivo

a->right = a->right->left

a->right->left = a

raiz = a->right

- Rotação simples à direita (RR)

Ocorre quando o balanceamento tende à esquerda: quando o sinal é negativo. E quando o balanceamento do nó à esquerda tende à esquerda: quando o sinal é negativo

a->left = a->left->right

a->left->right = a

raiz = a -> left

- Rotação dupla à esquerda (LR)

Ocorre no filho de a, onde tende o desbalanceamento tem sinal inverso. Devemos realizar a rotação no filho de a onde tende o balanceamento

- Rotação dupla à direita (RL)

Ocorre quando o nó desbalanceado tende à esquerda. Filho à esquerda tende à direita. Rotação inicial deve reajustar isso.

Filho à esquerda do filho à direita do nó torna-se o filho à direita do nó. Nó torna-se filho à esquerda do antigo filho à direita dele.

- Árvore binárias balanceadas – AVL

- Algoritmo de cálculo de profundidade

int profundidade (no *raiz)

int esquerda=0

int direita=0

     se raiz->esquerda

     esquerda=1+profundidade(raiz->esquerda)

     se raiz->direita

     direita=1+profundidade(raiz->direita)

     retorna máximo(esquerda,direita)

- Algoritmo de cálculo de balanço

int balanço(no raiz)

return profundidade(raiz->direita)-profundidade(raiz->esquerda)

Cálculo da profundidade sempre que necessitar calcular o balanço. Não é viável. Para otimizar necessitamos modificar a estrutura da árvore.

typedef struct node {

     struct node *esquerda;

     struct node *direita;

     int dado;

     int profundidade;

}

- Código rotação à esquerda

RotacionaEsquerda(node *raiz)

node *a_subir=raiz->direita;

raiz->direita=a_subir->esquerda;

a_subir->esquerda=raiz;

raiz->profundidade=profundidade(raiz);

a_subir->profundidade=profundidade(a_subir);

retorna a_subir;

- Código rotação à direita

RotacionaDireita(node *raiz)

node *a_subir=raiz->esquerda;

raiz->esquerda=a_subir->direita;

a_subir->direita=raiz;

raiz->profundidade=profundidade(raiz);

a_subir->profundidade=profundidade(a_subir);

retorna a_subir;

- Código rotação dupla à esquerda    

rotacionaDuplaEsquerda(node *raiz)

raiz->esquerda=rotacionaDireita(raiz->esquerda);

retorna RotacionaEsquerda(raiz);

- Código rotação dupla à direita

rotacionaDuplaDireita(node *raiz)

raiz->direita=rotacionaEsquerda(raiz->direita);

retorna rotacionaDireita(raiz);

- Inserção

Inserção(node *raiz,int dado)

     Se raiz=nulo

        raiz=nova_arvore(dado)

     Se dado

        raiz->esquerda=insere(dado,raiz->esquerda)

        se profundidade(raiz->esquerda)-profundidade(raiz->direita)==2

        se dadoesquerda->dado

        raiz=rotacionaDireita(raiz)

        senão

        raiz=rotacionaDuplaDireita(raiz)

     se dado>raiz

        raiz->direita=insere(dado,raiz->direita)

        se profundidade(raiz->esquerda)-profundidade(raiz->direita)==2

        se dado>raiz->direita->dado

        raiz=rotacionaEsquerda(raiz)

        senão

        raiz=rotacionaDuplaEsquerda(raiz)

     retorn raiz

- Remoção

Funciona como em árvores binárias de busca. Porém podemos nos beneficiar do fator balanço.

Caso balanço tender à esquerda

     Sub-árvore à esquerda é maior

     Busca-se o maior valor menor que o dado a remover

Caso o balanço tender à direita

     Sub-árvore à direita é maior

     Busca-se o menor valor maior que o dado a remover