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;
}