ANSI C tarea: Depth First Search

DFS (en inglés Depth First Search) es un algoritmo que nos sirve para movernos a través de la estructura de un grafo. Básicamente permite visitar los vértices de un grafo, pero existen muchos algoritmos que están basados en DFS para realizar sus distintas funcionalidades. Su principio de funcionamiento es bastante sencillo: hay que avanzar en profundidad visitando cada nodo mientras sea posible visitarlo, si no es posible visitar a un nodo, entonces se realiza un procedimiento llamado "backtracking", en el cual comenzamos a regresar por el camino donde llegamos.

Para saber si un vértice es "visitable", contiene tres colores que funcionan como identificadores de su estado:

1. Blanco: Significa que el vértice no ha sido visitado.

2. Gris: La visita a ese vértice está en progreso.

3. Negro: Ya se terminó la exploración de ese nodo y se dice que está visitado.

También se pueden tomar sólo dos colores o los valores verdadero y falso para determinar el estado de un nodo.

Inicialmente, todos los vértices son coloreados de blanco y conforme avanza la búsqueda o visita, sus colores van cambiando para representar su estado.

En esta ocasión deseaba mostrar un ejemplo de esta implementación, sin embargo, no logré mi objetivo pero de todas formas quiero dejar el código visto en clase para representar un grafo junto con las modificaciones que comencé a hacerle para intentar producir un DFS.

Este es el código del archivo grafo.c en donde se encuentran las funciones esArista y DFS que comencé a construir:

#include <stdio.h>
#include <stdlib.h>
#include "bool.h"

typedef struct algo {
  char caracter;
  int id;
  struct algo* sig;
  //Estado del nodo: 'b' = blanco, no visitado,
  //'g' = gris, visitado, 'n' = negro, ya no tiene aristas por visitar
  char estado;
} lista;

int etiqueta(lista** nombres, char a, 
      int* sigId) {
  lista* l = *nombres;
  lista* nuevo = NULL;
  int n = *sigId;
  if (l == NULL) { // no hay nada
    nuevo = (lista*)malloc(sizeof(lista));
    nuevo->caracter = a;
    nuevo->id = n++;
    *sigId = n;
    nuevo->estado = 'b';
    nuevo->sig = NULL;
    *nombres = nuevo;
    return nuevo->id;
  }
  while (1) { // mientras siempre
    if (l->caracter == a) {
      return l->id; // ya esta
    }
    if (l->sig != NULL) {
      l = l->sig; // avanzar en la lista
    } else { // lo ponemos al final
      nuevo = (lista*)malloc(sizeof(lista));
      nuevo->caracter = a;
      nuevo->id = n++;
      *sigId = n;
      nuevo->estado = 'b';
      nuevo->sig = NULL;
      l->sig = nuevo; // ligar en la lista
      return nuevo->id;
    }
  }
}

char recuperar(lista* l, int a) {
  while (l != NULL) { // mientras siempre
    if (l->id == a) {
      return l->caracter;
    }
    if (l->sig != NULL) {
      l = l->sig; // avanzar en la lista
    }
  }
  return '?';
}

//este es un metodo que intente construir para verificar que 
//hay una arista entre dos nodos dados
bool esArista(int** matriz, int a, int b){
  return(matriz[a][b] == 1);
}

//este es el metodo que intente construir para realizar un DFS
void DFS(lista** lista, int** matriz){
  lista* listaDFS = *lista;
  lista* aux = *lista;
  listaDFS -> estado = 'g';
  while(aux != NULL){
    if(esArista(matriz, listaDFS->id, aux->id) && 
       aux->estado == 'b'){
      print("%d\n", listaDFS->id);
      DFS(aux->siguiente, matriz);
    }
  }
  listaDFS->estado = 'n';
}

int main(int argc, char** args) {
  char* archivo = NULL;
  char* segundo = NULL;
  FILE* entrada = NULL;
  FILE* salida = NULL;
  lista* nombres = NULL;
  lista* aux = NULL;
  char a, b;
  int na, nb, i, j, n = 0;
  int** matriz = NULL;
  bool sinSalida = FALSE;

  if (argc < 3) {
    printf("Ponme los archivos guey.\n");
    return 0;
  }
  archivo = args[1];
  segundo = args[2];
  entrada = fopen(archivo, "r"); // r = lectura
  if (entrada == NULL) {
    printf("No se pudo con %s.\n", archivo);
    return 0;
  }
  salida = fopen(segundo, "w+"); // escribe o crea
  if (salida == NULL) {
    sinSalida = TRUE;
    printf("No habra salida.\n");
  }
  while (!feof(entrada)) {
    fscanf(entrada, "%c %c\n", &a, &b);
    na = etiqueta(&nombres, a, &n);
    nb = etiqueta(&nombres, b, &n);
    printf("Recuperado: (%c=%d, %c=%d).\n", 
    a, na, b, nb);
  }
  printf("Fueron en total %d nodos.\n", n);
  matriz = (int**)malloc(sizeof(int*)*n);
  for (i = 0; i < n; i++) {
    matriz[i] = (int*)malloc(sizeof(int)*n);
    for (j = 0; j < n; j++) {
      matriz[i][j] = 0; // no hay conexion
    }
  }
  rewind(entrada);
  while (!feof(entrada)) {
    fscanf(entrada, "%c %c\n", &a, &b);
    na = etiqueta(&nombres, a, &n);
    nb = etiqueta(&nombres, b, &n);
    // hay arista (na, nb) = (nb, na)
    matriz[na][nb] = 1;
    matriz[nb][na] = 1;
  }
  fclose(entrada);
  if (salida == NULL) {
    salida = stdout;
  }
  fprintf(salida, "    ");
  for (j = 0; j < n; j++) {
    fprintf(salida, "%c ", recuperar(nombres, j));
  }
  fprintf(salida, "\n   ");
  for (j = 0; j < n; j++) {
    fprintf(salida, "--", recuperar(nombres, j));
  }
  fprintf(salida, "\n");
  for (i = 0; i < n; i++) {
    fprintf(salida, 
     "%c | ", recuperar(nombres, i));
    for (j = 0; j < n; j++) {
      fprintf(salida, "%d ", matriz[i][j]);
    }
    fprintf(salida, "\n");
  }
  if (!sinSalida) {
    fclose(salida); // cerrar archivo
  }

  DFS(&nombres, matriz);

  // borrar la lista (una vez que ya no se ocupa)
  while (nombres != NULL) {
    aux = nombres->sig;
    free(nombres);
    nombres = aux;
  }

  for (i = 0; i < n; i++) {
    free(matriz[i]);
  }
  free(matriz);
  return 1;
}

Al compilar lo codificado, estos son los errores que aparecen:

Referencias

Algorithms and Data Structures with implementations in Java and C++. En http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search. Visitado el 14 de Julio de 2011.