BUPT-homework/semester3/pset7/7-1-Minimum-Spanning-Tree.c

#include <stdio.h>
#define SIZE 10
#define INF 9999

void createLine(int mat[SIZE][SIZE], char start, char end, int weight) {
  mat[start - 'A'][end - 'A'] = weight;
  mat[end - 'A'][start - 'A'] = weight;
}

int getMinNode(int* dist, int* visited) {
  int minDist = INF, minEnd;
  for (int i = 0; i < SIZE; i++) {
    if (dist[i] < minDist && !visited[i]) {
      minDist = dist[i];
      minEnd = i;
    }
  }
  return minEnd;
}

int min(int l, int r) {
  return (l < r)? l : r;
}

void sort(int* ans, int size) {
  // init bucket sort
  int max = -1;
  for (int i = 0; i < size; i++) {
    if (ans[i] > max) {
      max = ans[i];
    }
  }

  int bucket[max + 1];
  for (int i = 0; i < max + 1; i++) {
    bucket[i] = 0;
  }

  // bucket sort
  for (int i = 0; i < size; i++) {
    bucket[ans[i]]++;
  }

  int count = 0;
  int sorted[size];
  for (int i = 0; i < max + 1; i++) {
    while (bucket[i]) {
      sorted[count++] = i;
      bucket[i]--;
    }
  }

  for (int i = 0; i < size; i++) {
    ans[i] = sorted[i];
  }
}

void createGraph(int mat[SIZE][SIZE]) {
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      mat[i][j] = INF;
    }
  }

  createLine(mat, 'A', 'B', 3);
  createLine(mat, 'A', 'E', 4);
  createLine(mat, 'A', 'D', 4);
  createLine(mat, 'B', 'A', 3);
  createLine(mat, 'B', 'E', 2);
  createLine(mat, 'B', 'F', 3);
  createLine(mat, 'B', 'C', 10);
  createLine(mat, 'C', 'F', 6);
  createLine(mat, 'C', 'G', 1);
  createLine(mat, 'D', 'E', 5);
  createLine(mat, 'D', 'H', 6);
  createLine(mat, 'E', 'F', 11);
  createLine(mat, 'E', 'H', 2);
  createLine(mat, 'E', 'I', 1);
  createLine(mat, 'E', 'D', 5);
  createLine(mat, 'F', 'E', 11);
  createLine(mat, 'F', 'B', 3);
  createLine(mat, 'F', 'C', 6);
  createLine(mat, 'F', 'G', 2);
  createLine(mat, 'F', 'J', 11);
  createLine(mat, 'F', 'I', 3);
  createLine(mat, 'G', 'J', 8);
  createLine(mat, 'H', 'I', 4);
  createLine(mat, 'I', 'J', 7);
}

int main(void) {
  int mat[SIZE][SIZE];
  createGraph(mat);

  char start, end;
  int weight;
  scanf("%c,%c,%d", &start, &end, &weight);
  mat[start - 'A'][end - 'A'] = weight; // the matrix is undirectional
  mat[end - 'A'][start - 'A'] = weight;

  int ans[SIZE - 1];
  int dist[SIZE] = {};
  for (int i = 1; i < SIZE; i++) {
    dist[i] = INF;
  }
  int top = 0;

  int cur;
  int visited[SIZE] = {};

  while (top != SIZE) {
    cur = getMinNode(dist, visited);
    visited[cur] = 1;

    ans[top++] = dist[cur];

    for (int j = 0; j < SIZE; j++) {
      dist[j] = min(dist[j], mat[cur][j]);
      // printf("%c -> %c: %d\n", cur + 'A', j + 'A', dist[j]);
    }
  }

  ans[0] = ans[top - 1]; // top == SIZE

  sort(ans, SIZE - 1);
  for (int i = 0; i < SIZE - 1; i++) {
    printf("%d,", ans[i]);
  }

  return 0;
}