文章
166
粉丝
0
获赞
0
访问
10.1k
(1)因为是有向图的邻接矩阵存储方式,点所对应列即是该顶点的入度,点所对应行即是该顶点的出度,进行vumVertices轮遍历,每次去判断是否有且仅有一个入度为0的顶点
(2)
int uniquely(MGraph G){
int indegrees[g.numVertices];//统计每个顶点的入度
for(int i = 0 ; i < numVertices ;i++){
for(int j = 0 ; j < numVertices ; j++){
indegrees[i] += g.Edge[j][i];
}
}
//遍历 所以顶点,每次判断是否只有一个顶点入度0
for(int i = 0 ; i < numVertices ; i++){
int count = 0;
int tail = 0;
for(int j = 0 ; j <numVertices ; j++0){
if(indegrees[j] == 0){
tail = i; //记录这一轮的弧尾结点
count ++;
}
}
if(count != 1){
return 0;//不存在只有一个入度0的结点则返回0
}
for(int k = 0 ; k <numVertices ; k++){
indegrees[k] -= g.Edge[tail][k]; //更新入度
}
}
return 1;//如果遍历完所有结点则表示存在唯一拓扑序列
}
评分及理由
(1)得分及理由(满分4分)
得分:3分
理由:学生的基本设计思想与标准答案基本一致,正确理解了拓扑排序的唯一性判断方法。但未明确提到“移除入度为0的顶点”这一关键步骤,表述不够完整。
(2)得分及理由(满分9分)
得分:6分
理由:代码整体思路正确,但存在以下问题:
1. 变量名拼写错误(如`g.numVertices`应为`G.numVertices`)
2. 循环条件错误(`j++0`应为`j++`)
3. 入度数组未初始化(`indegrees`应初始化为0)...
登录后发布评论
暂无评论,来抢沙发