bfs.c

//
//  bfs.c
//  Algorithms - Graph breadth-first search
//
//  Created by YourtionGuo on 08/05/2017.
//  Copyright © 2017 Yourtion. All rights reserved.
//

#include <stdlib.h>

#include "bfs.h"
#include "graph.h"
#include "list.h"
#include "queue.h"

#pragma mark - Public

int bfs(Graph *graph, BfsVertex *start, List *hops)
{
  Queue       queue;
  AdjList     *adjlist, *clr_adjlist;
  BfsVertex   *clr_vertex, *adj_vertex;
  ListElmt    *element, *member;

  /// 初始化图的所有顶点

  for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {

    clr_vertex = ((AdjList *)list_data(element))->vertex;

    if (graph->match(clr_vertex, start)) {

      /// 初始化起点
      clr_vertex->color = gray;
      clr_vertex->hops = 0;

    } else {

      /// 初始化其他顶点
      clr_vertex->color = white;
      clr_vertex->hops = -1;

    }
  }

  /// 根据起点邻接表初始化队列

  queue_init(&queue, NULL);

  if (graph_adjlist(graph, start, &clr_adjlist) != 0) {

    queue_destroy(&queue);
    return -1;
  }

  if (queue_enqueue(&queue, clr_adjlist) != 0) {

    queue_destroy(&queue);
    return -1;
  }

  /// 执行广度优先搜索

  while (queue_size(&queue) > 0) {

    adjlist = queue_peek(&queue);

    /// 在当前邻接表遍历每个顶点

    for (member = list_head(&adjlist->adjacent); member != NULL; member = list_next(member)) {

      adj_vertex = list_data(member);

      /// 确定下个邻接顶点的颜色

      if (graph_adjlist(graph, adj_vertex, &clr_adjlist) != 0) {

        queue_destroy(&queue);
        return -1;
      }

      clr_vertex = clr_adjlist->vertex;

      /// 将白顶点着色为灰色并将邻接表入队

      if (clr_vertex->color == white) {

        clr_vertex->color = gray;
        clr_vertex->hops = ((BfsVertex *)adjlist->vertex)->hops + 1;

        if (queue_enqueue(&queue, clr_adjlist) != 0) {

          queue_destroy(&queue);
          return -1;
        }
      }
    }

    /// 将当前邻接表出队并将其着色为黑色

    if (queue_dequeue(&queue, (void **)&adjlist) == 0) {

      ((BfsVertex *)adjlist->vertex)->color = black;

    } else {

      queue_destroy(&queue);
      return -1;
    }
  }

  queue_destroy(&queue);

  /// 回传每个顶点的跳数到表中

  list_init(hops, NULL);

  for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {

    /// 去掉跳数为 -1 的（不可达）

    clr_vertex = ((AdjList *)list_data(element))->vertex;
    
    if (clr_vertex->hops != -1) {
      
      if (list_ins_next(hops, list_tail(hops), clr_vertex) != 0) {
        
        list_destroy(hops);
        return -1;
      }
    }
  }
  
  return 0;
}