文章
270
粉丝
1
获赞
100
访问
51.3k
(1)算法思想
先用一个数组统计每个顶点的入度,然后每次将入度为0的顶点移除,并且将该顶点的出边删去,也就是将与之相连的顶点的入度减1,之后重复
找入度为0的顶点删去相连的边,在查找入度为0的顶点过程中,若发现查找个数不等于1,代表拓扑序列不为1,返回0即可,等到查找次数等于顶点个数代表有唯一的拓扑序列,返回1。
(2)
int uniquely(MGraph G){
int n = G.numVertices;//记录顶点的个数
int *A = (int *)malloc(sizeof(int)*n);//构建辅助数组,统计顶点入度
int degree = 0;//累加顶点度
int v = -1;
int count = 0;
int num = 0;
for(int i =0;i< n;i++){
A[i] = 0;
}
for(int i =0;i< n;i++){//统计顶点入度
degree = 0;
for(int j = 0;j<n;j++){
degree += G.Edge[j][i];//累加顶点的入度
}
A[i] = degree;//统计每个顶点的入度
if(A[i] == 0){
count ++;
num++;
...
登录后发布评论
暂无评论,来抢沙发