文章

77

粉丝

35

获赞

2

访问

15.3k

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

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

1)存在拓扑序列的前提是图中没有出现环路,而出现唯一拓扑序列的前提是,在去除入度为0的顶点时,只存在一个入度为0的顶点;若在去除入度为0的顶点过程中发现环路或是发现多个入度为0的顶点则返回0;如果遍历结束都没有函数返回,则返回1

2)

int InDegree[MAXV];  //事先保存了各个顶点的入度
bool IsSearch[MAXV]; //记录已经访问过的顶点,防止重复访问
Queue Q;
int IsFailed;

void topology(MGraph G, int v) {
    InitQueue(Q);
    int tempV;
    int count=0;  //记录当前入度为0的顶点数
    for (int i=0; i<G.numVertices; i++) {
        if (!G.Edge[v][i]) {
            InDegree[i]--;
        }
        if (!G.Edge[v][i] && IsSearch[i] == false) {
            IsSearch[i] = true;
            EnQueue(Q, i);
        }
    }
    if (count==0) {
        return;
    }
    if (count>1) {
        IsFailed = true;
        return;
    }
    while (!IsEmpty(Q)) {
        DeQueue(Q, tempV);
        topology(G, tempV);
    }
}


int uniquely(MGraph G) {
    
    InitQueue(Q);
    for (int i=0; i<G.numVertices; i++) {
        if (!InDegree[i]) {
            topology(G, i);
            IsSearch[i] = true;
  ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发