Representação de Grafos

Um dos assuntos mais frequentes são problemas relacionados a grafos, ou que podem ser representados como grafos, apesar de não ser óbvio à primeira vista.

Conceitos

Há diversos tipos e atributos de um grafo:

O que é um grafo?

Um grafo é definido simplesmente por um conjunto de vértices, e outro conjunto de arestas. Essas arestas ligam dois vértices, e podem ter pesos atrelados à elas.

Grafo simples

Grafo simples é um grafo que não cujas arestas não tem peso, não possui loops, e nem arestas múltiplas. Loops são arestas do tipo (u,u), ou seja, que saem do vértice u, e vão para o vértice u. Um grafo com arestas múltiplas é um grafo que tem duas aresta iguais.

Grafos direcionados

Existem grafos direcionados e não direcionados. No caso dos direcionados, significa que cada aresta tem uma direção, ou seja, se é possível chegar de a em b, não significa que é possível chegar de b em a.

Ciclos

A definição de ciclo é um pouco diferente dependendo se o grafo é direcionado ou não.

Caso o grafo não seja direcionado, e hajam dois caminhos diferentes de um vértice a para um vértice b, então há um ciclo.

Caso contrário, ou seja, caso o grafo seja direcionado, para que haja um ciclo é necessário que exista um vértice a tal que seja possível voltar a a partindo dele mesmo.

Conexo

Um grafo conexo é um grafo tal que para dois vértices quaisquer u e w, sempre existe um caminho de u para w.

Componentes conexas

Um grafo que não é conexo pode ter várias componentes conexas (grafos conexos tem somente uma componente). Essencialmente, uma componente conexa é um pedaço conexo do grafo. Esse conceito é usado no caso de grafos não-direcionados.

Componentes fortemente conexas

Já nos casos do grafos direcionados, o termo usado é esse, também chamados por SCCs(Strongly Connectec Components). A definição mais ‘formal’ é a seguinte: dentro de uma componente conexa de um grafo direcionado, para todo vértice a e b, deve ser possível de chegar de b partindo de a e em a partindo de b.

Basicamente o que a definição acima está dizendo é: uma componente fortemente conexa é um ciclo, mas é importante lembrar que se dois ciclos se juntam, formam um ciclo maior, logo, uma componente maior.

Árvore

Uma árvore é um tipo de grafo. Para ser uma árvore, o grafo precisa ser conexo, não ter ciclos e ter n-1 arestas, aonde n é o número de vértices.

DAG

DAG é uma sigla para Directed Acyclic Graph, ou seja, um grafo acíclico e direcionado. É um termo bastante usado.

Grafos bipartidos

Um grafo bipartido é um grafo tal que é possível dividir seus vértices em dois grupos, de forma que só hajam arestas ligando vértices do primeiro ao segundo grupo.

Representação de um grafo

Mas como representar um grafo em código?

Na verdade é bem mais simples do que parece. Para cada vértice, temos que manter apenas uma lista das arestas que saem daquele vértice.

Nessa representação, a i-ésima posição no vector de fora vector<int>, esse vector representam as arestas que saem daquele vértice. Então, cada vértice tem um número associado a ele.

Exemplo

vector<int> graph[7];

graph[4].push_back(6);
graph[6].push_back(4);

graph[4].push_back(5);
graph[5].push_back(4);

graph[4].push_back(3);
graph[3].push_back(4); 

graph[2].push_back(3);
graph[3].push_back(2); 

graph[2].push_back(5);
graph[5].push_back(2); 

graph[4].push_back(6);
graph[6].push_back(4); 

graph[2].push_back(1);
graph[1].push_back(2); 


// lembrando que no caso de grafos não direcionados, quando adicionamos (a,b) precisamos sempre adicionar (b,a) junto.

Representação da grafos implícitos

Considere o seguinte problema para guiar a explicação: http://codeforces.com/problemset/problem/520/B

A principio, nao parece exatamente muito fácil relacionar esse problema com grafos. Onde estão os vértices e as arestas? Na verdade nesse problema há o que chamamos de grafo implícito.

Podemos considerar os vértices como o número mostrado pelo display, e as arestas como os vértices que consigo alcançar apertando os botões, a partir do vértice que estou. Mas nós não vamos criar uma estrutura de lista de adjacências em memória igual ao caso anterior, não precisamos. A única coisa que precisamos é saber quais vértices podemos atingir a partir de um vértice x, então quando formos percorrer esse grafo implícito, como todos os vértices seguem essa regra, não precisamos criar as arestas propriamente ditas. Apenas sabemos que é possível atingir os vértices x-1 e 2x.

O mesmo ocorre pra representação de jogos de turno, por exemplo jogo da velha ou damas. Podemos considerar uma configuração do tabuleiro como um vértice, e as arestas ligando para todas as configurações possíveis de atingir segundo as regras de jogada.

VideoAulas complementares

https://www.youtube.com/watch?v=zaBhtODEL0w

Exercícios recomendados

• https://www.urionlinejudge.com.br/judge/pt/problems/view/1910 - Caminho mínimo em grafo implícito sem pesos.
• https://www.urionlinejudge.com.br/judge/pt/problems/view/1907 - Contagem de componentes conexas em grafo que é um grid (implícito).
• https://codeforces.com/gym/102346/problem/A - Se considerarmos as paredes e sensores vértices, vendo se alguns vértices estão na mesma componente conexa podemos ver se há um caminho que bloqueia o ladrão.
• https://www.urionlinejudge.com.br/judge/pt/problems/view/2194 - (implementação mais difícil), resolver o reconhecimento por meio da contagem das componentes conexas de cada hieróglifo.

Busca em Largura

Podemos chamá-la também de BFS (Breadth-First Search).

Uma das formas de percorrer um grafo é fazer um percorrimento em largura. Começamos a explorar os vértices do grafo a partir de um certo vértice a. E a ordem que vamos navegando entre os vértices é de forma que os mais próximos a a sempre serão visitados antes. Então, primeiro a será visitado, depois os vértices que são adjacentes a a(distância 1), depois os vértices que estão a duas arestas de distância, e assim por diante. Como os vértices mais próximos são sempre visitados antes, esse algoritmo serve para, por exemplo, dizer qual a distância mínima entre dois vértices no grafo.

Esse comportamento é implementado usando-se uma fila. Primeiro insere-se na fila o vértice inicial, e começa-se a desenfileirar da fila enquando houver algum nodo. Quando um vértice a é desenfileirado, enfileram-se todos os vértice adjacentes a a que não foram visitados. Caso não marquemos os visitados, e o grafo tiver ciclos, nosso programa não terminará.

O algoritmo abaixo é uma BFS que simplesmente percorre o grafo.

const int MAX_SIZE = 1e5;

// globais
// inicializa visited como false
bool visited[MAX_SIZE];
vector<int> graph[MAX_SIZE];

void bfs(int start){
    
    queue<int> q;
    q.push(start);

    visited[start] = true;
    while(!q.empty()){//Enquanto não estiver vazia
        // Retire o vértice da frente
        int u = q.front();
        q.pop();
        for(int w: graph[u]){ // Para cada vértice adjacente a u
            if(!visited[w]){
                q.push(w);
                visited[w] = true;
            }
        }
    }
}

A complexidade desse código é O(n+m), temos no máximo n vértices enfileirados, e no loop interno, cada iteração é considerar uma aresta, como não estamos voltando no grafo, não passaremos por uma aresta mais que duas vezes naquele loop. Então, em todas as chamadas, aquele loop iterará no pior caso m vezes.

Busca em Profundidade

Outra forma de percorrer um grafo é fazer percorrimento em profundidade, também de chamado de DFS(Depth-first search). O algoritmo se chama assim porque funciona de uma forma que sempre vamos ‘mergulhar’ no grafo o mais fundo que pudermos. Quando não for mais possível ir mais fundo no grafo, voltamos até que seja ir mais fundo novamente, sem repetir vértices já visitados.

A implementação da DFS mais comum é recursiva, por ser mais intuitiva. Assim como o exemplo anterior, esse programa simplesmente percorre o grafo, mas na ordem que um DFS percorre.

Visualização

Implementação

const int MAX_SIZE = 1e5;

vector<int> graph[MAX_SIZE];
bool visited[MAX_SIZE];     // globais, inicializados na main.

void dfs(int vertex){ // na main chamamos dfs(start), aonde start é o vértice que começamos o dfs
    visited[vertex] = true;

    for(int w: graph[vertex]){
        if(!visited[w]){
            dfs(w);
        }
    }    
}

A complexidade desse código é O(n+m), temos no máximo n chamadas recursivas, e no loop interno às chamadas, assim como no BFS, estaremos considerando uma aresta e não passaremos nela mais de uma vez. Então no máximo m iterações ao longo de todas as chamadas.

Dijkstra

O algoritmo de Dijkstra é um algoritmo muito conhecido para percorrimento de grafos cujas arestas tem pesos, ele nos permite percorrer os vértices na ordem de distância para um vértice fonte. E efetivamente descobrir essas distâncias.

Mais especificamente, de uma forma tal que considerando o vértice fonte como s, se o menor caminho de s para um vértice u é estritamente menor que o menor caminho de s para um outro vértice v, com certeza visitaremos u antes de v.

A forma como o algoritmo opera é muito parecida com o BFS, mas em vez de usarmos uma fila, usamos uma fila de prioridades(priorizando menores valores). O motivo de usarmos essa outra estrutura de dados é que usar uma fila não gera mais o mesmo comportamento que desejamos quando as arestas passam a ter pesos.

Como as arestas tem pesos, nosso grafo será um vector<pair<int,int>> grafo[n] ao invés de um vector<int> grafo[n].

A ideia

Assim como no BFS, teremos essa fila que ditará a ordem com que os nodos serão desenfileirados (visitados). Mas agora Nossa Fila é de prioridades abriga pares ao invés de apenas um inteiro.

Pra qualquer par p na fila, (p.first,p.second) significa: Consigo chegar no vértice p.second por um caminho de custo p.first. Por isso no começo da execução enfileiramos o par (0, s), dizendo: consigo chegar no vértice fonte pagando 0, afinal já estamos nele no começo do percorrimento.

Quando desinfileiramos um vértice, assim como no BFS, consideramos seguir por todas as arestas que partem dele, agora com pesos.

Bem, para cada aresta, sabemos seu destino e seu peso, então, a informação que podemos tirar disso é que podemos ir para aquele destino com o custo da aresta somado com o custo para chegar no vértice que acabamos de desinfileirar.

Na implementação do BFS, na hora de verificar se devíamos enfileirar algo, verificavamos apenas se aquele destino já tinha sido enfileirado antes, usando um vetor pra armazenar essa informação.

Na nossa implementação, ao invés de um vetor marcando quais já foram enfileirados, usaremos um vetor indicando o melhor custo conhecido para se atingir cada vértice.

O motivo disso é que não há mais garantia que na primeira vez que enfileiramos um vértice já obtivemos o melhor custo para chegar nele. Pode ser que posteriormente enfileiremos um custo menor pra chegar nesse vértice.

Então, na hora de enfileirarmos, verificaremos se aquele enfileiramento é vantajoso, isto é, se ele melhora o melhor custo que já conhecíamos para chegar em algum vértice. De começo assumimos o custo infinito para chegar em todos.

Visualização

Implementação

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 100005;
const ll oo = 1e18;

ll d[N]; // vetor onde guardamos as distancias

int n; // numeros de vertices

// lista de adjacencias guarda
// pair <vertice para onde a aresta vai, peso da aresta>
vector<pair<int, ll>> g[N];

void dijkstra(int start){

	// inicialmente a distancia do vertice
	// start para todo os outros é infinita
	for(int u = 1; u <= n; u++)
		d[u] = oo;

	// fila de prioridade de pair<ll, int>, mas que o
	// menor pair fica no topo da fila
	// guardamos um pair <distancia ate o vertice, vertice>
	// assim o topo da fila sempre é o vertice com menor distancia
	priority_queue<pair<ll, int>, vector<pair<ll, int>>,
		greater<pair<ll, int>> > pq;

	d[start] = 0;
	pq.emplace(d[start], start);

	ll dt, w;
	int u, v;
	while(!pq.empty()){
		tie(dt, u) = pq.top(); pq.pop();
		if(dt > d[u]) continue;
		for(auto edge : g[u]){
			tie(v, w) = edge;

			// se a distancia ate o u somado com o peso
			// da aresta é menor do que a distancia ate o v que
			// tinhamos antes, melhoramos a distancia ate o v
			if(d[v] > d[u] + w){
				d[v] = d[u] + w;
				pq.emplace(d[v], v);
			}
		}
	}
}


int main(){

	// lê o input, qnt de vertices, arestas
	// e vertice inicial(start)
	
	dijkstra(start);

	for(int u = 1; u <= n; u++){
		printf("Distancia de %d para %d: %lld\n", start, u, d[u]);
	}

}

Assim como no BFS, podemos facilmente adicionar um vetor indicando os predecessores de cada vértice, dessa forma podemos obter não só a informação dos custos, mas também a sequência de vértices que a origina.