AEDs III 11/05/2011

// A aula de hoje é novamente sobre busca em profundidade com a professora Jussara

Revisão Busca em Profundidade:
Busca em Profundidade é uma busca em que voce primeiro exauri os caminhos possíveis de um ramo da árvore antes de procurar
em outro ramo. Isso aplicado recursivamente te leva a pesquisar até as folhas mais distantes, ou mais profundas e só então retornar
para procurar os vizinhos daquele ramo. Por isso o nome "Busca em Profundidade".

Como grafos podem possuir loops, voce colore os nós que voce já passou com uma cor, ou um marcador númerico para caso voce passe por
ele novamente voce não entre em um loop infinito. Uma vez que um nó tenha tido suas transições exauridas na pesquisa é preciso também
pinta-lo de uma segunda cor, isso pode ser usado para detecção de arestas de retorno, que será conceituado mais abaixo.
complexidade: O(V+A)

Revisão Busca em Largura:
Na busca em largura, voce pesquisa primeiro os nós próximos ao nó inicial de uma distancia 1, e em seguida os de distancia 2
e assim por diante até ter encontrado todos os nós e transições da árvore.
Aqui só é necessária uma "coloração"
Complexidade: O(V+A)

CONCEITO:
Aresta de árvore é uma aresta que durante a busca levou a descoberta de um nó pela primeira vez.

CONCEITO:
Aresta de retorno são as arestas que levam  durante a busca a um nó ancestral ou seja um nó raiz do nó atual.

CONCEITO:
Arestas de avanço é o caso contrario das de retorno, é quando voce encontra através dela um nó já percorrido que porém não é
antecessor do nó atual.
// Pense que voce está saindo de um ramo de uma árvore e encontrando outro ramo paralelo ao primeiro.

CONCEITO:
Arestas de cruzamento são as arestas que se conectam a um nó já percorrido ou pela própria árvore ou por outra árvore.
Isso inclui as arestas de avanço de retorno e um terceiro grupo que são as arestas que levam a outra árvore pesquisada paralelamente.

CONCEITO:
Para descobrir se um grafo tem ciclo basta verificar a existência de uma aresta de retorno.
Para isso basta utilizar um algoritimo de Busca em Profundidade e portanto este problema é O(V+A)

CONCEITO:
Para se descobrir a menor distancia entre 2 nós de um grafo não direcionado com arestas de peso 1 aplique a
busca em largura em um deles,
E marque o número de níveis que voce caminhou até encontrar o outro nó. Esse número necessáriamente é o menor caminho possível.
Isso é O(V+A)

CONCEITO:
Ordenação Topologica é colocar os vertices de um grafo direcionado em ordem de precedencia.
Isso se aplica apenas em grafos direcionados sem loops.
Dessa forma cada vertice fica depois de todos os vertices que apontam para ele, e antes de todos para os quais ele aponta.
Uma aplicação nisso é ordenar um conjunto de tarefas em um projeto de uma empresa, ou ordenar as execuções de diciplinas
em uma faculdade.
Se o grafo não for conexo obviamente não hávera uma única ordenação, mas mais de uma.

Para gerar essa ordenação pode-se usar uma busca em profundidade e sempre que voce marcar um nó como já exaurido
voce o coloca na sequencia.
// Eu não entendi direito como isso funciona, talvez valesse a pena rodar o algoritmo na mão para entender melhor.

CONCEITO:
Detecção de componentes formente conexos em grafos direcionados.
Para esse problema Precisa-se:
Usar a busca em profundidade no grafo G
Gerar o G transposto Gt O(A)
E agora usar busca em profundidae novamente em Gt começando pelo nó de maior tempo de termino da primeira busca.
Os nós retornados por essa segunda busca devem pertencer a um componente fortemente conectado.
Se restar algum nó que não pertença a este componente, reinicie a busca no próximo nó cujo o tempo de termino tenha sido maior.
Isso tem complexidade: O(V+A + A + V+A) = O(V+A)
// Outro algoritimo que não entendi bem como funciona, rodar na mão talvez fosse uma boa ideia.

CONCEITO:
Arvore geradora é uma árvore que chega a todos os vertices de uma árvore sem repetir nós.

CONCEITO:
Arvore geradora mínima é a árvore geradora cuja soma dos pesos dos nós seja o menor possível.
Esse problema pode ser pensado como a ótimização do custo de conecção entre um conjunto de computadores.
ou casas, ou cidades, etc. . .

Um algoritimo para esse problema é o algoritmo de Prim,
O algoritimo de Prim é buscar a partir de um nó inicial e suas arestas iterativamente uma aresta que ligue o conjunto de
nós que eu ja possuo a um outro nó de fora deste conjunto no menor custo possível e então incluir este novo nó e nova aresta na
minha árvore.
A árvore final deve ser a árvore geradora mínima.
Fazendo essa escolha com este critério guloso eu consigo uma solução ótima.

Uma estrutura utilizada nesse algoritimo é a arvore heap formada pelos nós do grafo e ordenada pelo menor custo de acesso conhecido
para se chegar neste nó. Observe que a medida que novos nós e arestas são incluídos na sua arvore pode ser necessário atualizar o
menor valor de acesso de um dos nós do heap e isso é O(log(V))
A complexidade é O((V+A)logV).

// Já revisado!