文章

28

粉丝

19

获赞

0

访问

1.4k

头像
【2024年】408计算机统考真题模拟考试 - 第41题答案笔记
数据结构
发布于2024年12月18日 16:11
阅读数 38

计算机考研408统考历年真题及答案解析

(1)用一个数组indegree[numVertices]记录每个顶点的入度,zero用于记录当前入度为0的节点号,初值为-1.,按以下思路进行算法:
1.遍历邻接矩阵的列填入indegree数组;
2.遍历indegree数组,找出indegree为0的索引号存入zero中,如果找到2个(即zero!=-1的情况下有indegree为0),则返回false;
3.否则遍历邻接矩阵中的第zero行找到与选中节点的邻接节点,将zero指向节点以及其邻接节点入度-1
4.若zero!=-1,重复过程2;否则返回true
(2)
int uniquely(MGraph G)
{
int indegree[MAXV] = {0};

//初始化indegree
for(int i = 0; i< G.numVertices; i++)
{
int deg = 0;
for(int j = 0; j< G.numVertices; j++)
{
if(G.Edges[j][i] > 0)
{
deg++;
}
}
indegree[i] = deg;
}

//开始拓扑
int zero = -1;
do
{
for(int i = 0;i < G.numVertices; i++)
{
 if(indegree[i] == 0){
 if(zero == -1)
 zero = i;
else
//存在两种拓扑
 return false
}
}
if(zero != -1)
{
for(int j = 0; j< G.numVertices; j++)
{
if(G.Edges[zero][j] > 0) indegree[j]--;
}
indegree[zero]--;
}
}while (zero != -1)
//遍历完毕,存在唯一拓扑
return true;
}

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发