805 - Busca em Largura

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

/* Structs */
typedef struct adj_list Adjlist;
struct adj_list {
  int item;
  Adjlist *next;
};

typedef struct graph Graph;
struct graph {
  Adjlist **vertices;
  short *visited;
  int *distance;
  int *previous;
  int size;
};

typedef struct node Node;
struct node {
  int item;
  Node* next_node;
};

typedef struct queue Queue;
struct queue {
  Node *first;
  Node *rear;
};

/* Utils */
void free_adj_list(Adjlist *node) {
  if(node == NULL) return;

  free_adj_list(node->next);

  free(node);
}

void free_graph(Graph *graph) {
  int i;

  for(i = 0; i < graph->size; ++i) {
    free_adj_list(graph->vertices[i]);
  }

  free(graph);
}

/* List functions */
void sort_list(Adjlist* list) {
  Adjlist* node_aux;
  Adjlist* node;

  for(node_aux = list; node_aux->next != NULL; node_aux = node_aux->next) {
    for(node = list; node->next != NULL; node = node->next) {
      if(node->item > node->next->item) {
        char item_aux = node->item;
        node->item = node->next->item;
        node->next->item = item_aux;
      }
    }
  }
}

/* Queue functions */
Queue* create_queue() {
  Queue *queue = (Queue*) malloc(sizeof(Queue));
  queue->first = NULL;
  queue->rear = NULL;

  return queue;
}

void enqueue(Queue *queue, int item) {
  Node *new_node = (Node*) malloc(sizeof(Node));
  new_node->item = item;
  new_node->next_node = NULL;

  if(queue->rear == NULL) {
    queue->first = queue->rear = new_node;
  } else {
    queue->rear->next_node = new_node;
    queue->rear = new_node;
  }
}

int dequeue(Queue *queue) {
  int dequeued_item;
  if(queue->first == NULL) {
    return -1;
  } else {
    dequeued_item = queue->first->item;
  }


  Node* dequeued = queue->first;
  queue->first = queue->first->next_node;

  if(queue->first == NULL && queue->rear != NULL) queue->rear = NULL;

  free(dequeued);
  return dequeued_item;
}

/* Graph functions */
Graph* create_graph(int size) {
  Graph *graph = malloc(sizeof(Graph));

  graph->size = size;
  graph->vertices = malloc(size * sizeof(Adjlist *));
  graph->visited = malloc(size * sizeof(short));
  graph->distance = malloc(size * sizeof(int));
  graph->previous = malloc(size * sizeof(int));

  int i;
  for(i = 0; i < size; ++i) {
    graph->vertices[i] = NULL;
    graph->visited[i] = 0;
    graph->distance[i] = 0;
    graph->previous[i] = -1;
  }

  return graph;
}

Adjlist* create_adjlist(int item) {
  Adjlist *adjlist = (Adjlist*) malloc(sizeof(Adjlist));
  adjlist->item = item;
  adjlist->next = NULL;

  return adjlist;
}

void add_edge(Graph *graph, int orig, int dest) {
  Adjlist *vertex = create_adjlist(dest);
  vertex->next = graph->vertices[orig];
  graph->vertices[orig] = vertex;
}

void reset_graph(Graph *graph) {
  int i;

  for(i = 0; i < graph->size; ++i) {
    graph->distance[i] = 0;
    graph->previous[i] = -1;
    graph->visited[i] = 0;
  }
}

void print_path(Graph *graph, int i, int orig) {
  if(i == orig) return;

  print_path(graph, graph->previous[i], orig);

  printf("%d => ", i);
}

void print_graph(Graph *graph, int orig, int dest) {
  int i;

  printf("\n");
  for(i = 0; i < graph->size; ++i) {
    printf("%d", i);

    if(graph->distance[i] == 0 && i != orig) printf(" | - | ");
    else printf(" | %d | ", graph->distance[i]);

    if(graph->previous[i] == -1) printf("-\n");
    else printf("%d\n", graph->previous[i]);
  }

  if(graph->distance[dest] == 0) {
    printf("\nSem caminho entre %d e %d\n", orig, dest);
  } else {
    printf("\nCaminho entre %d e %d: %d => ", orig, dest, orig);
    print_path(graph, graph->previous[dest], orig);
    printf("%d\n", dest);
  }

  printf("\n");
}

void bfs(Graph *graph, int orig, int dest) {
  Queue *queue = create_queue();
  int dequeued;

  Adjlist *adjlist = graph->vertices[orig];
  graph->visited[orig] = 1;
  enqueue(queue, orig);

  while(queue->first != NULL) {
    dequeued = dequeue(queue);
    printf("Iniciando busca em largura a partir de %d\n", dequeued);
    adjlist = graph->vertices[dequeued];

    while(adjlist != NULL) {
      if (!graph->visited[adjlist->item]) {
        enqueue(queue, adjlist->item);
        graph->visited[adjlist->item] = 1;
        graph->previous[adjlist->item] = dequeued;
        graph->distance[adjlist->item] = graph->distance[dequeued] + 1;
      }

      adjlist = adjlist->next;
    }
  }

  graph->previous[orig] = -1;

  free(queue);
}

void sort_graph(Graph *graph) {
  int i;

  for(i = 0; i < graph->size; ++i) {
    if(graph->vertices[i] != NULL) sort_list(graph->vertices[i]);
  }
}

int main() {
  int v, a, t;
  int o, d;
  int i;

  scanf("%d %d %d", &v, &a, &t);
  Graph *graph = create_graph(v);

  for(i = 0; i < a; ++i) {
    scanf("%d %d", &o, &d);

    add_edge(graph, o, d);
  }

  sort_graph(graph);

  for(i = 1; i <= t; ++i) {
    scanf("%d %d", &o, &d);

    printf("--------\n\n");
    printf("Caso de Teste #%d - BFS(%d)\n\n", i, o);
    bfs(graph, o, d);
    print_graph(graph, o, d);

    reset_graph(graph);
  }

  printf("--------");

  free_graph(graph);

  return 0;
}