mst.c

//
//  mst.c
//  Algorithms - Minimum spanning tree
//
//  Created by YourtionGuo on 23/05/2017.
//  Copyright © 2017 Yourtion. All rights reserved.
//

#include <float.h>
#include <stdlib.h>

#include "graph.h"
#include "graphalg.h"
#include "list.h"


int mst(Graph *graph, const MstVertex *start, List *span,
        int (*match)(const void *key1, const void *key2))
{
  AdjList     *adjlist = NULL;
  MstVertex   *mst_vertex, *adj_vertex;
  ListElmt    *element, *member;
  double      minimum;
  int         found, i;

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

  found = 0;

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

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

    if (match(mst_vertex, start)) {

      /// 初始化起点
      mst_vertex->color = white;
      mst_vertex->key = 0;
      mst_vertex->parent = NULL;
      found = 1;

    } else {

      /// 初始化起点外的其他顶点
      mst_vertex->color = white;
      mst_vertex->key = DBL_MAX;
      mst_vertex->parent = NULL;

    }
  }

  /// 如果找不到起点返回 -1
  if (!found) return -1;

  /// 使用 Prim 算法计算最小生成树

  i = 0;

  while (i < graph_vcount(graph)) {

    /// 选择最小权重的白色顶点
    minimum = DBL_MAX;

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

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

      if (mst_vertex->color == white && mst_vertex->key < minimum) {

        minimum = mst_vertex->key;
        adjlist = list_data(element);

      }
    }

    /// 将选中的顶点涂为黑色
    ((MstVertex *)adjlist->vertex)->color = black;

    /// 遍历选中顶点的每个邻接顶点
    for (member = list_head(&adjlist->adjacent); member != NULL; member = list_next(member)) {

      adj_vertex = list_data(member);

      /// 通过顶点的邻接表找到邻接顶点
      for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {

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

        if (match(mst_vertex, adj_vertex)) {

          /// 决定是否改变邻接表中邻接顶点的权重和父节点
          if (mst_vertex->color == white && adj_vertex->weight < mst_vertex->key) {

            mst_vertex->key = adj_vertex->weight;
            mst_vertex->parent = adjlist->vertex;

          }

          break;

        }
      }
    }

    /// 准备选择下一个顶点
    i++;
  }

  /// 将最小生成树载入列表

  list_init(span, NULL);

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

    /// 从邻接表中加载每个黑色顶点
    mst_vertex = ((AdjList *)list_data(element))->vertex;
    
    if (mst_vertex->color == black) {
      
      if (list_ins_next(span, list_tail(span), mst_vertex) != 0) {
        
        list_destroy(span);
        return -1;
      }
    }
  }
  
  return 0;
}