拓朴排序
比如用邻接矩阵存贮有向图，以入度为“0”的标准进行拓扑排序
步骤1：建立邻接矩阵，入有向边为 1->2, 1->3, 3->4, 2->5
则邻接矩阵如下：
0 0 0 0 0
0 0 1 1 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 0
步骤2：计算各顶点的入度，就是看矩阵中每一列上“1” 的个数
用in[]来存放各顶点入度，那么
in[0] = 1, in[1]=0, in[2]=1, in[3]=1, in[4]=1
步骤3：拓朴排序
从in[]中查找值为“0”的节点并输出，例如 in==0，说明节点i 的入度为“0”，这时要把 in 置为“-1”，说明它已经被查找过了，我们还要在矩阵中的第i 行上找值为“1”的列，如找到列 j, 说明 i->j 为一条有向边，我们已经把i 节点去掉了，自然 i->j 这条有向边就不存在了，j 的入度要减去”1“， 即 in--, 循环查找，知道全部节点已序
#include<stdio.h>
#include<stdlib.h>
#define NODENUM 40
int matrix[NODENUM][NODENUM];
int num = 0;
void read(){
int i,j;
scanf("%d", &num);
printf("actural node num is: %d", num);
for(i=0; i<num; i++)
for(j=0; j<num; j++)
matrix<i>[j] = 0;
while(1){
scanf("%d %d", &i, &j);
if(i == -1 && j == -1)
break;
if( (i >= num || i < 0) &&
(j >= num || j < 0) ){
printf("please input 0 -- 40!\n");
exit(1);
}
matrix<i>[j] = 1;
}
}
void print(){
int i,j;
printf("\nMatrix is: \n");
for(i=0; i<num; i++){
for(j=0; j<num; j++)
printf("%d ", matrix<i>[j]);
printf("\n");
}
}
void topSort(){
//
int in[NODENUM]; //存放各顶点入度
int i, j, temp;
int visitedNode = 0; //已序的顶点个数
int flag;
//算出每个顶点的入度--每一列上的“1”的个数
for(j=0; j<num; j++){
temp = 0;
for(i=0; i<num; i++){
if(matrix<i>[j] == 1)
temp += 1;
}
in[j] = temp;
}
printf("\nIn array is: \n");
for(i=0; i<num; i++)
printf("%d ", in<i>);
printf("\n\n");
//循环查找“入度”数组，当找到入度为“0”的节点i时
//把当前数组值置为“-1”，表示已序
//把已序的顶点个数的节点个数加“1”
//把查找标记置为“1”，说明此循环找到了入度为0的节点
//输出此节点
//找邻接数组中的i行上所有值为“1”的列j，把in[j]值减1，
//说明此节点的入度少了一个
while(visitedNode < num){
flag = 0;
for(i=0; i<num; i++){
if(in<i> == 0){
in<i> = -1;
visitedNode++;
flag = 1;
printf("%d ", i);
for(j=0; j<num; j++){
if(matrix<i>[j] == 1)
in[j]--;
}
}
}
//如果没有找到入度为"0"的节点则退出
if(flag == 0){
printf("there is not node that its in degree is '0' \n");
break;
}
}
printf("\n");
//
}
void main(){
read();
print();
topSort();
}
irini
2007-02-28 22:29:10
评论:0
阅读:90
引用:0