Métodos de Travsesia em Grafos

Dois métodos fundamantais para percorrer grafos:

• DFS (Busca em Profundidade)
• BFS (Busca em Largura) - implementada com fila

DFS com Lista de Adjacência

#define TAM_MAX 100
#define INF 65535

typedef struct NoAdjacente* PonteiroNo;
struct NoAdjacente {
  int Vertice;
  int Peso;
  PonteiroNo Proximo;
};

typedef struct {
  PonteiroNo PrimeiraAresta;
  char Dado;
} CelulaLista[TAM_MAX];

typedef struct GrafoLista* GrafoL;
struct GrafoLista {
  int Vertices;
  int Arestas;
  CelulaLista Adjacencias;
};

GrafoL CriarGrafo(int TotalVertices) {
  GrafoL Novo = (GrafoL)malloc(sizeof(struct GrafoLista));
  Novo->Vertices = TotalVertices;
  Novo->Arestas = 0;
  for(int v = 0; v < TotalVertices; v++)
    Novo->Adjacencias[v].PrimeiraAresta = NULL;
  return Novo;
}

void InserirAresta(GrafoL G, int Origem, int Destino, int Peso) {
  PonteiroNo NovaAresta = (PonteiroNo)malloc(sizeof(struct NoAdjacente));
  NovaAresta->Vertice = Destino;
  NovaAresta->Peso = Peso;
  NovaAresta->Proximo = G->Adjacencias[Origem].PrimeiraAresta;
  G->Adjacencias[Origem].PrimeiraAresta = NovaAresta;
}

int Visitados[TAM_MAX];
void Visitar(int V) {
  printf("Visitado: %d\n", V);
}

void DFS(GrafoL G, int V) {
  Visitar(V);
  Visitados[V] = 1;
  
  PonteiroNo Atual = G->Adjacencias[V].PrimeiraAresta;
  while(Atual) {
    if(!Visitados[Atual->Vertice])
      DFS(G, Atual->Vertice);
    Atual = Atual->Proximo;
  }
}

BFS com Matriz de Adjacência

typedef struct GrafoMatriz* GrafoM;
struct GrafoMatriz {
  int Vertices;
  int Arestas;
  int Matriz[TAM_MAX][TAM_MAX];
  char Dados[TAM_MAX];
};

GrafoM IniciarGrafo(int TotalVertices) {
  GrafoM Novo = (GrafoM)malloc(sizeof(struct GrafoMatriz));
  Novo->Vertices = TotalVertices;
  Novo->Arestas = 0;
  for(int i = 0; i < TotalVertices; i++)
    for(int j = 0; j < TotalVertices; j++)
      Novo->Matriz[i][j] = INF;
  return Novo;
}

#define CAPACIDADE 50
int Fila[CAPACIDADE];
int Inicio = 0, Fim = -1, Itens = 0;

void Enfileirar(int Elemento) {
  Fim = (Fim + 1) % CAPACIDADE;
  Fila[Fim] = Elemento;
  Itens++;
}

int Desenfileirar() {
  int Elemento = Fila[Inicio];
  Inicio = (Inicio + 1) % CAPACIDADE;
  Itens--;
  return Elemento;
}

int Vazio() { return Itens == 0; }

void BFS(GrafoM G, int Inicio) {
  int Marcados[TAM_MAX] = {0};
  Enfileirar(Inicio);
  Visitar(Inicio);
  Marcados[Inicio] = 1;

  while(!Vazio()) {
    int Atual = Desenfileirar();
    for(int w = 0; w < G->Vertices; w++) {
      if(!Marcados[w] && G->Matriz[Atual][w] != INF) {
        Enfileirar(w);
        Visitar(w);
        Marcados[w] = 1;
      }
    }
  }
}

Aplicação: Porblema de Escape

struct Ponto {
  int x;
  int y;
} Locais[TAM_MAX];

float Distancia(int x1, int y1, int x2, int y2) {
  return sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
}

int VerificarEscape(GrafoM G, int Vertice, float Limite) {
  Visitados[Vertice] = 1;
  
  float d1 = Distancia(0, 50, Locais[Vertice].x, Locais[Vertice].y);
  float d2 = Distancia(0, -50, Locais[Vertice].x, Locais[Vertice].y);
  float d3 = Distancia(50, 0, Locais[Vertice].x, Locais[Vertice].y);
  float d4 = Distancia(-50, 0, Locais[Vertice].x, Locais[Vertice].y);
  
  if(d1 <= Limite || d2 <= Limite || d3 <= Limite || d4 <= Limite)
    return 1;

  for(int i = 0; i < G->Vertices; i++) {
    if(!Visitados[i] && G->Matriz[Vertice][i])
      if(VerificarEscape(G, i, Limite))
        return 1;
  }
  return 0;
}