Capítulo 5: Grafos em Algoritmos

Os grafos são uma estrutura de dados fundamental que modelam conexões e relacionamentos entre objetos. Eles têm aplicações de amplo alcance na ciência da computação e além, desde a modelagem de redes sociais e links de páginas da web, até a resolução de problemas em transporte, programação e alocação de recursos. Neste capítulo, exploramos as propriedades básicas e os algoritmos para trabalhar com grafos, com foco em grafos não direcionados, busca em profundidade e largura, árvores geradoras mínimas e caminhos mais curtos.

Grafos Não Direcionados

Um grafo não direcionado é um conjunto de vértices (ou nós) conectados por arestas. Formalmente, definimos um grafo não direcionado G como um par (V, E), onde V é um conjunto de vértices e E é um conjunto de pares não ordenados de vértices, chamados de arestas. Uma aresta (v, w) conecta os vértices v e w. Dizemos que v e w são adjacentes ou vizinhos. O grau de um vértice é o número de arestas incidentes a ele.

Aqui está um exemplo simples de um grafo não direcionado:

   A --- B
  /     / \
 /     /   \
C --- D --- E

Neste grafo, o conjunto de vértices V = {A, B, C, D, E} e o conjunto de arestas E = {(A, B), (A, C), (B, D), (B, E), (C, D), (D, E)}.

Existem várias maneiras de representar um grafo em um programa. Duas representações comuns são:

1. Matriz de Adjacência: Uma matriz booleana n x n A, onde n é o número de vértices. A entrada A[i][j] é verdadeira se houver uma aresta do vértice i para o vértice j, e falsa caso contrário.

2. Listas de Adjacência: Um array Adj de tamanho n, onde n é o número de vértices. A entrada Adj[v] é uma lista contendo os vizinhos de v.

A escolha da representação depende da densidade do grafo (razão entre arestas e vértices) e das operações que precisamos realizar. As matrizes de adjacência são simples, mas podem ser ineficientes para grafos esparsos. As listas de adjacência são mais eficientes em termos de espaço para grafos esparsos e fornecem acesso mais rápido aos vizinhos de um vértice.

Aqui está um exemplo de como poderíamos representar o grafo acima usando listas de adjacência em Java:

List<Integer>[] adj = new ArrayList[5];
for (int i = 0; i < 5; i++) {
    adj[i] = new ArrayList<>();
}
adj[0].add(1); adj[0].add(2); // Aresta (A, B) e (A, C)
adj[1].add(0); adj[1].add(3); adj[1].add(4); // Arestas (B, A), (B, D) e (B, E)
adj[2].add(0); adj[2].add(3); // Arestas (C, A) e (C, D)
adj[3].add(1); adj[3].add(2); adj[3].add(4); // Arestas (D, B), (D, C) e (D, E)
adj[4].add(1); adj[4].add(3); // Arestas (E, B) e (E, D)

>[] graph = (List<Integer>[]) new List[5];
graph[0] = Arrays.asList(1, 2);        // A -> B, C
graph[1] = Arrays.asList(0, 3, 4);     // B -> A, D, E
graph[2] = Arrays.asList(0, 3);        // C -> A, D
graph[3] = Arrays.asList(1, 2, 4);     // D -> B, C, E
graph[4] = Arrays.asList(1, 3);        // E -> B, D

Busca em Profundidade (DFS)

A busca em profundidade (DFS) é um algoritmo fundamental de travessia de grafos que explora o mais longe possível ao longo de cada ramificação antes de retroceder. Ele pode ser usado para resolver muitos problemas de grafos, como encontrar componentes conectados, ordenação topológica e detecção de ciclos.

O algoritmo DFS funciona da seguinte maneira:

1. Comece em um vértice de origem s.
2. Marque o vértice atual como visitado.
3. Visite recursivamente todos os vértices não marcados w adjacentes ao vértice atual.
4. Se todos os vértices adjacentes ao vértice atual tiverem sido visitados, retroceda para o vértice do qual o vértice atual foi explorado.
5. Se houver vértices não marcados, selecione um e repita a partir da etapa 1.

Aqui está uma implementação simples em Java de DFS usando listas de adjacência:

boolean[] visited;
 
void dfs(List<Integer>[] graph, int v) {
    visited[v] = true;
    for (int w : graph[v]) {
        if (!visited[w]) {
            dfs(graph, w);
        }
    }
}

Para realizar uma travessia DFS completa, chamamos dfs(graph, s) para cada vértice s no grafo, onde visited é inicializado como false para todos os vértices.

O DFS tem muitas aplicações. Por exemplo, podemos usá-lo para encontrar componentes conectados em um grafo não direcionado, executando o DFS a partir de cada vértice não visitado e atribuindo cada vértice a um componente com base na árvore DFS.

Busca em Largura (BFS)

A busca em largura (BFS) é outro algoritmo fundamental de travessia de grafos que explora os vértices em camadas. Ele visita todos os vértices no nível de profundidade atual antes de passar para os vértices no próximo nível de profundidade.

O algoritmo BFS funciona da seguinte maneira:

1. Comece em um vértice de origem s e marque-o como visitado.
2. Enfileire s em uma fila FIFO.
3. Enquanto a fila não estiver vazia: a. Desenfie um vértice v da fila. b. Para cada vértice w adjacente a v que não tenha sido visitado: i. Marque w como visitado. ii. Enfileire w.Enquanto a fila não estiver vazia:
   • Desenfileirar um vértice v.
   • Para cada vértice não marcado w adjacente a v:
     • Marcar w como visitado.
     • Enfileirar w.

Aqui está uma implementação em Java de BFS usando listas de adjacência:

boolean[] visited;
 
void bfs(List<Integer>[] graph, int s) {
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.offer(s);
 
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph[v]) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

BFS é particularmente útil para encontrar caminhos mais curtos em grafos não ponderados. A distância do vértice de origem a qualquer outro vértice é o número mínimo de arestas em um caminho entre eles. BFS garante encontrar o caminho mais curto.

Árvores Geradoras Mínimas

Uma árvore geradora mínima (MST) é um subconjunto das arestas de um grafo não direcionado, conectado e com pesos nas arestas, que conecta todos os vértices, sem ciclos e com o peso total mínimo possível.

Dois algoritmos clássicos para encontrar MSTs são o algoritmo de Kruskal e o algoritmo de Prim.

O algoritmo de Kruskal funciona da seguinte maneira:

1. Criar uma floresta F onde cada vértice é uma árvore separada.
2. Criar um conjunto S contendo todas as arestas do grafo.
3. Enquanto S não estiver vazio e F ainda não for uma árvore geradora:
   • Remover uma aresta de peso mínimo de S.
   • Se a aresta removida conectar duas árvores diferentes, adicioná-la a F, combinando as duas árvores em uma única árvore.

O algoritmo de Prim funciona da seguinte maneira:

1. Inicializar uma árvore com um único vértice, escolhido arbitrariamente do grafo.
2. Expandir a árvore por uma aresta: de todas as arestas que conectam a árvore a vértices ainda não na árvore, encontrar a aresta de peso mínimo e adicioná-la à árvore.
3. Repetir o passo 2 até que todos os vértices estejam na árvore.

Aqui está uma implementação em Java do algoritmo de Prim:

int minKey(int[] key, boolean[] mstSet, int V) {
    int min = Integer.MAX_VALUE, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
 
void primMST(int[][] graph, int V) {
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        key[i] = Integer.MAX_VALUE;
        mstSet[i] = false;
    }
 
    key[0] = 0;
    parent[0] = -1;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
 
    printMST(parent, graph, V);
}

As árvores geradoras mínimas (MSTs) têm muitas aplicações, como o projeto de redes (comunicação, elétrica, hidráulica, computador) e a aproximação de problemas do caixeiro viajante.

Caminhos Mais Curtos

O problema do caminho mais curto é encontrar um caminho entre dois vértices em um grafo de modo que a soma dos pesos de suas arestas seja minimizada. Este problema tem muitas variações, como caminhos mais curtos de uma única origem, caminhos mais curtos entre todos os pares de vértices e caminhos mais curtos para um único destino.

O algoritmo de Dijkstra é um algoritmo guloso que resolve o problema de caminhos mais curtos de uma única origem para um grafo com pesos de arestas não negativos. Ele funciona da seguinte maneira:

1. Crie um conjunto sptSet (conjunto da árvore de caminho mais curto) que acompanha os vértices incluídos na árvore de caminho mais curto.
2. Atribua um valor de distância a todos os vértices no grafo. Inicialize todos os valores de distância como INFINITO. Atribua o valor de distância como 0 para o vértice de origem.
3. Enquanto sptSet não incluir todos os vértices, escolha um vértice v que não esteja em sptSet e tenha o valor de distância mínimo. Inclua v em sptSet.

Atualize o valor de dist de todos os vértices adjacentes a v. Para atualizar os valores de distância, itere através de todos os vértices adjacentes. Para cada vértice adjacente w, se a soma da distância v.Aqui está a tradução em português do arquivo Markdown, com os comentários traduzidos, mas sem adicionar nenhum comentário adicional no início do arquivo:

Valor de v (da fonte) e peso da aresta v-w é menor que o valor da distância de w, então atualize o valor da distância de w.

Aqui está uma implementação em Java do algoritmo de Dijkstra:

public void dijkstra(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
    boolean[] sptSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        dist[i] = Integer.MAX_VALUE;
        sptSet[i] = false;
    }
 
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    printSolution(dist);
}

O algoritmo de Bellman-Ford é outro algoritmo para encontrar os caminhos mais curtos de uma única fonte para todos os outros vértices em um grafo direcionado com pesos. Ao contrário do algoritmo de Dijkstra, o algoritmo de Bellman-Ford pode lidar com grafos com pesos de aresta negativos, desde que não haja ciclos de peso negativo.

O algoritmo funciona da seguinte maneira:

1. Inicialize as distâncias da fonte para todos os vértices como infinito e a distância para a própria fonte como 0.
2. Relaxe todas as arestas |V| - 1 vezes. Para cada aresta u-v, se a distância para v puder ser encurtada ao tomar a aresta u-v, atualize a distância para v.
3. Verifique se há ciclos de peso negativo. Execute uma etapa de relaxação para todas as arestas. Se qualquer distância mudar, então há um ciclo de peso negativo.

Aqui está uma implementação em Java do algoritmo de Bellman-Ford:

public void bellmanFord(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
 
    for (int i = 0; i < V; i++)
        dist[i] = Integer.MAX_VALUE;
    dist[src] = 0;
 
    for (int i = 1; i < V; i++) {
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    // Se a distância do vértice u mais o peso da aresta (u, v) for menor que a distância atual do vértice v,
                    // atualize a distância de v
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
 
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            // Se existe uma aresta (u, v) e a distância de u mais o peso da aresta (u, v) é menor que a distância atual de v,
            // então o grafo contém um ciclo de peso negativo
            if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                System.out.println("O grafo contém um ciclo de peso negativo");
                return;
            }
        }
    }
 
    // Imprime a solução (distâncias mínimas)
    printSolution(dist);
}

Algoritmos de caminhos mínimos têm diversas aplicações, como em sistemas de navegação, protocolos de roteamento de rede e planejamento de transporte. Eles são ferramentas fundamentais em teoria dos grafos e essenciais em muitas tarefas de processamento de grafos.

Conclusão

Grafos são estruturas de dados versáteis e poderosas que podem modelar uma ampla variedade de problemas. Neste capítulo, exploramos as propriedades básicas e os tipos de grafos, e estudamos algoritmos fundamentais de grafos, incluindo busca em profundidade, busca em largura, árvores geradoras mínimas e caminhos mínimos.

A busca em profundidade e a busca em largura fornecem maneiras sistemáticas de explorar um grafo e formam a base para muitos algoritmos de grafos avançados. Algoritmos de árvore geradora mínima, como o de Kruskal e o de Prim, encontram uma árvore que conecta todos os vértices com o peso total mínimo. Algoritmos de caminhos mínimos, como o de Dijkstra e o de Bellman-Ford, encontram caminhos de peso mínimo entre vértices.

Entender esses conceitos e algoritmos fundamentais é crucial para trabalhar efetivamente com grafos e resolver problemas complexos em várias áreas. À medida que você avançar em seus estudos de algoritmos, você encontrará algoritmos de grafos mais avançados que se baseiam nessas técnicas fundamentais.

Grafos fornecem uma linguagem poderosa para descrever e resolver problemas na ciência da computação e além. Dominar algoritmos de grafos o equipará com um conjunto de ferramentas versátil para modelar e resolver uma ampla gama de problemas computacionais.# Desafios Finais

Desafio 1: Criar um aplicativo de lista de tarefas

Crie um aplicativo de lista de tarefas com as seguintes funcionalidades:

1. Adicionar uma nova tarefa
2. Marcar uma tarefa como concluída
3. Excluir uma tarefa
4. Exibir todas as tarefas, com indicação das tarefas concluídas

// Função para adicionar uma nova tarefa
function addTask() {
  // Código para adicionar uma nova tarefa
}
 
// Função para marcar uma tarefa como concluída
function completeTask(index) {
  // Código para marcar uma tarefa como concluída
}
 
// Função para excluir uma tarefa
function deleteTask(index) {
  // Código para excluir uma tarefa
}
 
// Função para exibir todas as tarefas
function displayTasks() {
  // Código para exibir todas as tarefas
}

Desafio 2: Criar um jogo da velha

Crie um jogo da velha com as seguintes funcionalidades:

1. Permitir que dois jogadores joguem alternadamente
2. Determinar quando um jogador vence o jogo
3. Permitir que os jogadores reiniciem o jogo

// Função para inicializar o jogo
function initGame() {
  // Código para inicializar o jogo
}
 
// Função para realizar uma jogada
function makeMove(row, col, player) {
  // Código para realizar uma jogada
}
 
// Função para verificar se há um vencedor
function checkWin(player) {
  // Código para verificar se há um vencedor
}
 
// Função para reiniciar o jogo
function resetGame() {
  // Código para reiniciar o jogo
}

Desafio 3: Criar um conversor de moedas

Crie um conversor de moedas com as seguintes funcionalidades:

1. Permitir que o usuário selecione a moeda de origem e a moeda de destino
2. Permitir que o usuário insira um valor a ser convertido
3. Exibir o valor convertido

// Função para converter moedas
function convertCurrency(amount, fromCurrency, toCurrency) {
  // Código para converter moedas
}
 
// Função para exibir o resultado da conversão
function displayConversionResult(result) {
  // Código para exibir o resultado da conversão
}