算法 4.8.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 4.8  
void division ( int R[ ][ ],  int n,  int  result [ ] ) {
  // 已知 R[n][n] 是编号为 0 至 n-1 的 n 个元素的关系矩阵，子集划分的结果
  // 记入result 数组，result[k] 的值是编号为 k 的元素所属组号
  pre = n;  group = 0;
  InitQueue_Sq ( Q, n );                                   // 设置最大容量为 n 的空队列
  for ( e = 0;  e < n;  e++ )  EnQueue_Sq ( Q, e, 0 );
  while ( !QueueEmpty ( Q ) ) {
      DeQueue_Sq ( Q, i );
      if ( i < pre ) {         
      group ++;           // 增加一个新的组
      for ( j = 0;  j < n;  j ++ )   clash[j] = 0;
    }
    if ( clash[i] == 0 ) {
      result[i] = group;                                   // 编号为i 的元素入group 组
      for ( j = 0;  j < n;  j ++ )  clash[j] += R[i][j];   // 添加和 i冲突的信息
    }
    else  EnQueue ( Q, i, 0 );                             // 编号为i 的元素不能入当前组
    pre = i;
  } // while
}// division