O conteúdo desse site não é atualizado há anos. A informação está desatualizada e links quebrados.

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;

Page updated

Report abuse