Grafos - Implementações

Estruturas

O número de vértices será sempre n e o de arestas m. Os números máximos de vértices e arestas são MAXN e MAXM, respectivamente. O maior grau possível é MAXD.

Matriz de Adjacências

Representação: (G[][], n)

int G[MAXN][MAXN];
int n;

Listas de Adjacências

Representação: (G[][], grau[], n, m)

int G[MAXN][MAXD];
int grau[MAXN];
int n, m;

Lista de Arestas

Representação: (E[], n, m)

int E[MAXM][2];
int n, m;

Matriz de Adjacências Bipartida

Representação: (G[][], n, m)

int G[MAXN][MAXM];
int n, m;

Buscas

Busca em Largura (BFS)

Entrada:

  • Grafo por Listas de Adjacências (G[][], grau[], n, m).
  • Nó inicial no_inicial.

Complexidade: O(n + m)

Global:

int fila[MAXN];
int visitado[MAXN];

main:

int ini, fim;

for(int i=0; i<n; i++)
visitado[i] = 0;
visitado[no_inicial] = 1;

ini = fim = 0;
fila[fim++] = no_inicial;

while(ini != fim) {
int no = fila[ini++];

Processa_No(no);

for(int i=0; i<grau[no]; i++) {
int viz = G[no][i];
if(!visitado[viz]) {
fila[fim++] = viz;
visitado[viz] = 1;
}
}

Busca em Profundidade (DFS)

Entrada:

  • Grafo por Listas de Adjacências (G[][], grau[], n, m).
  • Nó inicial no_inicial.

Complexidade: O(n + m)

Global:

int visitado[MAXN];

void DFS(int no) {
visitado[no] = 1;

PreProcessa(no);

for(int i=0; i<grau[no]; i++)
if(!visitado[ G[no][i] ])
DFS( G[no][i] );

PosProcessa(no);
}

main:

for(int i=0; i<n; i++)
visitado[i] = 0;

DFS(no_inicial);

Árvore Geradora Mínima

Algoritmo de Prim

Entrada:

  • Grafo por Matriz de Adjacências (G[][], n).

Saída:

  • Custo da Árvore Geradora Mínima em total.

Complexidade: O(n^2)

Global:

#include <values.h>
const int INF = MAXINT/2;

int fixo[MAXN];
int custo[MAXN];

main:

int total = 0;

for(int i=0; i<n; i++) {
fixo[i] = 0;
custo[i] = INF;
}
custo[0] = 0;

for(int faltam = n; faltam>0; faltam--) {
int no = -1;
for(int i=0; i<n; i++)
if(!fixo[i] && (no==-1 || custo[i] < custo[no]))
no = i;
fixo[no] = 1;

if(custo[no] == INF) {
total = INF;
break;
}
total += custo[no];

for(int i=0; i<n; i++)
if(custo[i] > G[no][i])
custo[i] = G[no][i];
}

Caminhos Mínimos

Busca em Largura (BFS)

Entrada:

  • Grafo por Listas de Adjacências (G[][], grau[], n, m) sem peso nas arestas.
  • Vértice de origem orig.

Saída:

  • Vetor de distâncias dist[] do vértice orig a todos os outros.

Complexidade: O(n + m)

Global:

#include <values.h>
const int INF = MAXINT/2;

int fila[MAXN];
int dist[MAXN];

main:

int ini, fim;

for(int i=0; i<n; i++)
dist[i] = INF;
dist[orig] = 0;

ini = fim = 0;
fila[fim++] = orig;

while(ini != fim) {
int no = fila[ini++];

for(int i=0; i<grau[no]; i++) {
int viz = G[no][i];
if(dist[viz] == INF) {
fila[fim++] = viz;
dist[viz] = dist[no] + 1;
}
}
}

Algoritmo de Dijkstra

Entrada:

  • Grafo por Matriz de Adjacências (G[][], n) com peso nas arestas.
  • Vértice de origem orig.

Saída:

  • Vetor de distâncias dist[] do vértice orig a todos os outros.

Complexidade: O(n^2)

Global:

#include <values.h>
const int INF = MAXINT/2;

int fixo[MAXN];
int dist[MAXN];

main:

for(int i=0; i<n; i++) {
fixo[i] = 0;
dist[i] = INF;
}
dist[0] = 0;

for(int faltam = n; faltam>0; faltam--) {
int no = -1;
for(int i=0; i<n; i++)
if(!fixo[i] && (no==-1 || dist[i] < dist[no]))
no = i;
fixo[no] = 1;

if(dist[no] == INF)
break;

for(int i=0; i<n; i++)
if(dist[i] > dist[no]+G[no][i])
dist[i] = dist[no]+G[no][i];
}

Algoritmo de Floyd-Warshall

Entrada:

  • Grafo por Matriz de Adjacências (G[][], n) com peso nas arestas.

Saída:

  • Matriz de distâncias G[][] entre todos os pares de vértices.

Complexidade: O(n.m + n^2)

Global:

#include <values.h>
const int INF = MAXINT/2;

main:

for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
if( i!=k && G[i][k]<INF )
for(int j=0; j<n; j++)
if( G[i][j] > G[i][k]+G[k][j] )
G[i][j] = G[i][k]+G[k][j];

Bipartite Matching

Entrada:

  • Grafo por Matriz de Adjacências Bipartida (G[][], n, m).

Saída:

  • Número máximo de pares casados como valor de retorno.
  • Vetores conjuge0[] e conjuge1[] que indicam um possível matching que alcança o tamanho máximo.

Complexidade: O(n^3)

Global:

int conjuge0[MAXN];
int conjuge1[MAXM];
int visitado[MAXM];

int Aumenta(int no) {
int i;
for(i=0; i<m; i++)
if(G[no][i]==1 && !visitado[i]) {
visitado[i]=1;
if(conjuge1[i]==-1 || Aumenta(conjuge1[i])) {
conjuge0[no] = i;
conjuge1[i] = no;
return 1;
}
}
return 0;
}

int Matching() {
int i;
int aumentou;
int ncasados;

for(i=0; i<n; i++)
conjuge0[i] = -1;
for(i=0; i<m; i++)
conjuge1[i] = -1;

ncasados=0;
do {
aumentou=0;
for(i=0; i<m; i++)
visitado[i] = 0;
for(i=0; i<n; i++)
if(conjuge0[i]==-1)
if(Aumenta(i)) {
aumentou = 1;
ncasados++;
}
} while(aumentou);

return ncasados;
}