TEORIA DOS GRAFOS - 11/08/09
REVISÃO
Grafos - Conjunto de vértices (V) e arestas (E)
Um passeio é uma sequência de vértices: x0, x1, ..... xi tal que quando nos movemos de xi-1 para xi há uma aresta com portas xi-1 e xi no grafo.
Formalmente,
* xi-1 pertence E para 1<= i <=k
As arestas do passeio são xi-1xi para 1<=i<=k
Uma trilha é um passeio que não repete arestas.
Um caminho é um passeio que não repete vértices.
Grafo conexo - se existe um caminho de x até y, para todo par de x,y de vértices.
O algoritmo de busca em profundidade pode ser descrito como segue:
Dado um grafo G e um vértice s. O algoritmo mantém um vetor vis indexado pelos vértices de G e uma pilha p.
Inicialmente vis [x] = FALSO para todo vértice x diferente de s, vis [s] = TRUE e a pilha inicialmente contém s.
Enquanto a pilha p não está vazia faça
Seja x o vértice que está no topo de p
se x possui um vizinho y tal que viz[y]= FALSO então
visitado[y] = verdadeiro
empilhe y na pilha p
senão desempilhe p
fim se
fim enquanto
Nenhum comentário:
Postar um comentário