Introdução
Definição
Grafo
É uma estrutura de dados que contém um conjunto de vértices (nós) e arestas (arcos). Para cada arestas pode ser, também, associado um valor (peso).
Grafo não-direcionado
É o nome dado ao grafo em que nenhuma aresta tem sentido, ou seja, se existe uma aresta de A para B, A tem conexão com B assim como B tem conexão com A.
Grafo direcionado
É o nome dado ao grafo em que toda aresta tem um sentido, ou seja, se existe uma aresta de A para B, A tem conexão com B, porém B não necessariamente tem uma conexão com A.
Componente conexa
Atenção: falar de componente conexa só faz sentido em grafos NÃO direcionados!
Uma componente conexa é um subgrafo onde existe um caminho entre qualquer par de nós.
Componente fortemente conexa
Atenção: falar de componente fortemente conexa só faz sentido em grafos direcionados!
Uma componente fortemente conexa é um subgrafo onde existe um caminho de ida e um de volta entre qualquer par de nós.
Ponte
Nome dado à aresta que, se retirada do grafo, aumenta o número de componentes conexas do mesmo.
Articulação (vértice de corte)
Nome dado ao vértice que, se retirado do grafo, aumenta o número de componentes conexas do mesmo.
Grafo Biconexo
Grafo conexo que não tem articulações. É preciso que dois ou mais vértices sejam retirados para que o grafo deixe de ser conexo.
Grafo Bipartido
Grafo que pode ser dividido em duas "categorias" de vértices, onde cada uma categoria só se relaciona com vértices da categoria oposta.
Algoritmos clássicos
Busca em grafos
Busca em profundidade (DFS)
Aplicações:
- Descobrir se existe um caminho do vértice A ao vértice B:
Como? Basta rodar dfs(A); e depois checar se visitado[B] == 1;
- Descobrir componentes conexas:
Como? Em um grafo não-direcionado, ao rodar dfs(V) sendo V um vértice qualquer, o algoritmo visita todos os vértices da componente conexa de V.
- Descobrir componentes fortemente conexas:
Como? Sejam G um grafo direcionado, G' o grafo inverso (com as direções das arestas invertidas) e V um vértice qualquer. Se ambos dfs(G, V) e dfs(G', V) visitam todos os vértices, então o grafo G é fortemente conexo (por consequência, G' também).
Explicação:
Se dfs(G, V) visita todos os vértices do grafo, garantimos que existe um caminho de V para qualquer vértice de G. De forma semelhante, se dfs(G', V) visita todos os vértices do grafo, garantimos que para todo vértice de G existe um caminho para V. Dessa forma, garantimos que, para todo vértice, existe pelo menos um caminho para todo outro, passando por V (não necessariamente o melhor caminho).
Vale notar que, se algum dos dois testes for falso, o grafo seguramente não é fortemente conexo, já que ou não existiria um caminho de V para algum outro vértice ou o inverso.
- Biconectividade:
Em breve
/* Código de exemplo de teste de conectividade de grafos não-orientados, utilizando uma busca em profundidade. Supõe-se uma matriz de adjacência pré-existente em adj[][]. */ #define TAM 10 int visitado[TAM]; // vetor de visitação int adj[TAM][TAM]; // matriz de adjacencia void dfs(int u) { if (visitado[u]) return; visitado[u] = 1; for (int v=0; v < TAM; v++) if (adj[u][v]) { dfs(v); } } bool conexo() { // limpa todas as marcas de visitação for (int i=0; i < TAM; i++) visitado[i] = 0; // inicia busca no nó de índice 0 dfs(0); // testa se todos os nós foram visitados com uma única busca for (int i=0; i < TAM; i++) if (!visitado[i]) return false; return true; }
Busca em largura (BFS)
Aplicações:
- Descobrir se um grafo é bipartido:
Como? Na implementação da BFS você precisa guardar em que "lado do grafo" você está e um novo vetor que te diga a que "lado do grafo" pertence cada vértice. Supondo a seguinte codificação:
lado = -1; //lado esquerdo
lado = 1; //lado direito
ladoVertice[N] = {0, 0, 0, …}
Inicialmente você assume que o vértice inicial da busca está em um dos lados e roda a BFS. Dentro da BFS você precisa atribuir a cada vértice conectado ao vértice atual um lado contrário ao lado do vértice atual. Então, se você assumiu que o vértice inicial está do lado esquerdo, precisa dizer que todos os vértices que tem conexão com ele estão do lado direito. Caso algum dos vértices que tem conexão com o vértice atual já tenha sido setado como pertencente ao mesmo "lado do grafo" que o vértice atual está, então o grafo não é bipartido.
- Descobrir o menor caminho de A para B em um grafo com arestas de valor 1:
Como? Os vizinhos diretos de A estão a uma distância de 1 para A, os vizinhos dos vizinhos de A estão a uma distância de 2 para A e assim sucessivamente.
- Encontrar todos os nós de uma componente conexa:
Como? Basta guardar a informação de quais nós foram visitados ou não.
// Implementação de BFS usando matriz de adjacências. O(N²) #include <queue> #define INF 0x3F3F3F3F using namespace std; bool grafo[1010][1010], marca[1010]; int dist[1010]; int N; void BFS(int ini) { queue<int> Q; int cur; memset(marca, 0, sizeof(marca)); memset(dist, INF, sizeof(dist)); Q.push(ini); dist[ini] = 0; marca[ini] = 1; while (!Q.empty()) { cur = Q.front(); Q.pop(); // Procura um adjacente a cur que ainda não foi visitado for (int i = 1; i <= N; i++) { if (grafo[cur][i] && !marca[i]) { Q.push(i); // Coloca o nó i no fim da fila marca[i] = 1; dist[i] = dist[cur] + 1; } } } }
Caminho mais curto (um para todos)
Estrutura de grafo utilizada nos dois algoritmos de Caminho Mais Curto (Dijkstra e Bellman-Ford)
#define MSET(a, b) memset(a, b, sizeof(a)) using namespace std; const int VT = 1010; const int AR = VT * VT; const int INF = 0x3f3f3f3f; pair<int, pair<int, int> > edges[AR]; int adj[VT][VT]; int nadj[VT], nvt, nar; bool vis[VT]; // Dijkstra int dist[VT]; // Dijkstra int prev[VT]; // Predecessor ////////////////////////////////////////////////////////////////////////////// // Inicializa o grafo. // void inic_grafo(int n = 0) { nvt = n; //nar = 0; memset(nadj, 0, sizeof(nadj)); } ////////////////////////////////////////////////////////////////////////////// // Adiciona uma aresta ao grafo. // // int contAr; void aresta(int i, int j, int u = 0) { adj[i][nadj[i]++] = contAr; edges[contAr].first = u; edges[contAr].second.first = i; edges[contAr].second.second = j; contAr++; }
Dijkstra (com heap)
//int Dijkstra(int ini, int fim); /////////////////////////////////////////////////////////////////////////////// // Dijkstra - O((V+E)*log(V+E)) // grafo direcionado, para usar com nao-direcionado duplicar cada aresta // trocando a ordem dos nos int Dijkstra(int ini, int fim) { priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; MSET(prev, -1); MSET(vis, 0); MSET(dist, INF); dist[ini] = 0; pq.push(make_pair(0, ini)); while (!pq.empty()) { pair<int, int> par = pq.top(); pq.pop(); int atual = par.second; if (vis[atual]) continue; if (atual == fim) break; vis[atual] = true; for (int i = 0;i < nadj[atual]; i++) { int prox = edges[adj[atual][i]].second.second; if (vis[prox]) continue; if (dist[prox] > dist[atual] + edges[adj[atual][i]].first) { dist[prox] = dist[atual] + edges[adj[atual][i]].first; prev[prox] = atual; pq.push(make_pair(dist[prox], prox)); } // if } // for } // while return dist[fim]; }
Bellman-Ford
///////////////////////////////////////////////////////////////////////// // Bellman-Ford - O(V*E) // grafo direcionado, para usar com nao-direcionado duplicar cada aresta // trocando a ordem dos nos // Se tem ciclo negativo retorna false bool BellmanFord(int ini) { MSET(dist, INF); MSET(prev, -1); dist[ini] = 0; for (int i = 0; i < nvt; i++ ) { for (int j = 0; j < nar; j++ ) { int a, b, c; a = edges[j].second.first; b = edges[j].second.second; c = edges[j].first; if (dist[b] > dist[a] + c) { dist[b] = dist[a] + c; prev[b] = a; } // if } // for } // for // Verifica se tem ciclo negativo for (int i=0;i < nar;i++) { int a, b, c; a = edges[i].second.first; b = edges[i].second.second; c = edges[i].first; if (dist[b] > dist[a] + c) { return false; } } return true; }
Caminho mais curto (todos para todos)
Floyd-Warshall
// Assume que grafo[i][j] = tamanho da aresta de i para j, se existir ou INF caso contrário for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(grafo[i][j] > grafo[i][k] + grafo[k][j]) grafo[i][j] = grafo[i][k]+grafo[k][j]
Árvore Geradora Mínima (Minimum Spanning Tree)
Prim
// Implementação do Prim em O(N²) (não usa heap) #define INF 0x3F3F3F3F int grafo[1010][1010], dist[1010]; bool marca[1010]; int N; int Prim() { int ans = 0; // tamanho da MST (soma das arestas) int cur, cont; memset(marca, 0, sizeof(marca)); memset(dist, INF, sizeof(dist)); cur = 1; // Nó corrente cont = 1; // Contador de quantos nós já analisou // Enquanto não analisou todos os nós do grafo while (cont < N) { marca[cur] = 1; int menor = INF, indice = -1; // Percorre todos os nós não visitados procurando pelo que tem a // menor distância para a árvore. for (int i = 1; i <= N; i++) if (!marca[i]) { // Atualiza vetor de distancia do nó if (grafo[cur][i] < dist[i]) dist[i] = grafo[cur][i]; // Verifica se a distância para este nó é a menor if (dist[i] < menor) { menor = dist[i]; indice = i; } } // Se o grafo não é conexo não vai analisar todos os nós. // Então pára quando não achar mais nenhum para visitar. if (indice == -1) break; cont++; ans += menor; cur = indice; } return ans; }
Kruskal
int pai[VERTICES]; // Representa quem é o pai de cada um na floresta de union-find (inicializado com pai[i] = i) int posto[VERTICES]; // vetor de posto, inicializado com 0 int getrep(int x) { if (pai[x] != x) pai[x] = getrep(pai[x]); return pai[x]; } // "union" é keyword do C/C++, por isso comemos o "n" no final bool unio(int a, int b) { // retorna true caso a união tenha sido realmente feita... faz a implementação do kruskal ser mais simples // atualiza ponteiros para seus representantes a = getrep(a); b = getrep(b); if (a == b) return false; // pertencem à mesma componente, então não pode unir // faz união if (posto[a] >= posto[b]) { pai[b] = a; if (posto[a] == posto[b]) posto[a]++; } else pai[a] = b; return true; } pair<double, pair<int, int> > arestas[1010]; // representa uma aresta... .first = peso e .second = vertices int m; // numero de arestas double kruskal() { double r = 0.; sort(arestas, arestas + m); for (int i = 0; i < m; i++) { if (unio(arestas[i].second.first, arestas[i].second.second)) r += arestas[i].first; } return r; }
Conexidade
Componentes fortemente conexas
Pontes
Pontos de articulação
Para praticar… (exercícios)
- Número de Erdos
- Transmissão de Energia
- Duende Perdido
- Playing with Wheels
- The mysterious X network (usar vector< vector<int> > para a lista de adjacências para caber em memória)
- Door Man