文章
164
粉丝
0
获赞
1
访问
43.8k
(1)拓扑序列每次挑选入度为0的节点进行弹出,所以若每次弹出时,都仅有一个点满足入度为0的条件,且能够完整弹出所有点,则说明拓扑序列唯一,为便于更新弹出节点后的入度变化,采用一个辅助数组od[numVertices],记录各个节点的入度,在每轮处理时,查询od数组进行弹出,若某次处理时发现od数组中有至少两个为0,则说明不存在唯一拓扑序列。
(2)
初始化图,设置其指针为G;
int od[G.numVertices];
void initod(int od[G.numVertices], MGraph G)
{
for(int i=0; i<G.numVertices;i++)
{
for(int j=0;j<G.numVertices;j++)
{
od[i]+=G.Edge[j][i];
}
}
}
int uniquely(MGraph G)
{
initod(od,G);
int count=G.numVertices;
int num=0;//用于计数
int fz=0;//第一个入度为0的位置
While(num<count)
{
for(int i=0;i<G.numVertices;i++)
{
int count1=0;//检查入度为0的本轮节点数量
if(od[i]==0) fz=i; count++;
if(count>1) return 0;//检查到本轮入度节点个数大于1
}
od[fz]=-1;//说明节点已经弹出完毕,设置为-1
for(int i=0;i<G.numVertices;i+=)
{ od[i]-=Edge[fz][i]//除去该节点与其他节点的出边}
count++;
}
return 1;//成功返回
}
评分及理由
(1)得分及理由(满分4分)
学生给出了基本正确的设计思想:通过每次挑选入度为0的节点,若每次仅有一个入度为0的节点且能处理完所有节点,则拓扑序列唯一。思路与标准答案一致,表述清晰。得4分。
(2)得分及理由(满分9分)...
登录后发布评论
暂无评论,来抢沙发