travessia.md

Travessia

A trevessia de um grafo é a operação de passar por todos os seus vértices realizando alguma operação específica. Esta operação pode ser tanto a impressão da informação que do vértice, quanto algo mais complexo.

Existem dois modos de se fazer a travessia de um grafo:

1. Por Profundidade
2. Por Largura

Por Profundidade (DFS - Depth First Search)

A travessia por profundidade, ou Depth First Seach (DFS), é um modo de travessia de grafos em que a partir de um vértice é seguindo o caminho para o próximo vertice, e do próximo vai para próximo, até chegar ao fim, ou "fundo", do grafo. Ao chegar no fim, a travessia volta para o vértice anterior, e segue pelo próximo caminho possível até o fundo. Isto é feito até que todos os vértices tenham sido explorados.

#define MAX_V 1000

vector<int> G[MAX_V];
int visited[MAX_V];

void dfs(int u) {
    visited[u] = 1;

    for(auto v: G[u])
        if (!visited[v])
            dfs(v);
}

int main() {
    memset(visited, 0, sizeof visited);
}

Nesta travessia, o array visited é utilizado para marcar quais vértices já foram visitados, ou seja, quais véritces já passaram na travessia. Por isso, é importante inicializar este array com valores false ou 0, representado que incialmente nenhum vértice foi visitado. Esta estratégia, de utilizar o array de visitados é muito comum nos algoritmos de grafos, ela evita que um vértice seja processado mais de uma vez, evitando loops infinitos.

Esta traverssia não passará por todos os vértices se o grafo for disconectado ou direcionado. Pois nestes grafos, nem sempre há um caminho de qualquer vértice A para qualquer vértice B, o que faz com que a travessia não prossiga ou não chegue a estes vértices.

Por Largura (BFS - Breadth First Search)

A travessia por largura, ou Breadth First Search (BFS), é um modo de travessia de grafos em que a partir de um vértice todos os seus vizinhos, vértices ligados a ele, são visitados, então todos os vizinhos dos vizinhos são visitados. Isto é feito até que todos os vértices tenham sido visitados. É uma travessia que vai por camadas.

#define MAX_V 1000

vector<int> G[MAX_V];
int visited[MAX_V];

void bfs() {
    memset(visited, 0, sizeof visited);

    int initial_vertice = 0;

    queue<int> to_visit;
    to_visit.push(initial_vertice);
    visited[initial_vertice] = 1;

    while(!to_visit.empty()) {
        auto u = to_visit.front();
        to_visit.pop();

        for (auto v: G[u]) {
            if (!visited[v]) {
                visited[v] = 1;
                to_visit.push(v);
            }
        }
    }
}

Assim como o DFS, esta travessia não passará por todos os vértices, se o grafo for direcionado ou disconectado. Vai depender do vértice inicial.

Distância entre vértices

Esta traverssia, diferente to DFS, não é recursiva, e pode sofrer modificações simples para contar a distância do vértice inicial, initial_vertice, para qualquer outro vértice.

#define MAX_V 1000

vector<int> G[MAX_V];
int distance[MAX_V];

void bfs_distance() {
    memset(distance, -1, sizeof distance);

    int initial_vertice = 0;

    queue<int> to_visit;
    to_visit.push(initial_vertice);
    distance[initial_vertice] = 0;

    while(!to_visit.empty()) {
        auto u = to_visit.front();
        to_visit.pop();

        for (auto v: G[u]) {
            if (distance[v] == -1) {
                distance[v] = distance[u] + 1;
                to_visit.push(v);
            }
        }
    }
}

Exercícios

1. UVA
   1. 118 - Mutant Flatworld Explorers
   2. 280 - Vertex
   3. 11831 - Sticker Collector Robots
   4. 11902 - Dominator
   5. 12442 - Forwarding Emails
2. URI
   1. 1621 - Labyrinth
   2. 1550 - Inversion
   3. 1469 - Boss
   4. 1928 - Memory Game
   5. 1317 - I Hate SPAM, But Some People Love It

Referências

HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.