文章

8

粉丝

0

获赞

1

访问

557

头像
2024年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年6月29日 16:14
阅读数 13

1.建立一个队列,将所以入度为0顶点入队,之后再依次出队,让每个顶点的入度减一,再判断入度为0的点将其入队,直至队列为空,若遭遇过仍有元素未入队,存在环路,无拓扑序列,若队列中有两个以上的元素,则不唯一
2

int uniquely(MGraph G) {
    int inDegree[MAXV];//保存入度
    char queue[MAXV];//保存度为0的节点
    int front = 0, rear = 0;//队首和队尾
    int count = 0;//顶点计数
    for (int i = 0; i < G.numVertices; ++i) {
        for (int j = 0; j < G.numVertices; ++j) {
            inDegree[i] += G.Edge[j][i];//统计每个顶点的入度
        }
    }
    for (int i = 0; i < G.numVertices; ++i) {//将入度为0的点入队
        if (inDegree[i] == 0) {
            queue[rear++] = G.VerticesList[i];
        }
    }
    while (rear - front == 1) {//保证拓扑排序唯一
        char x = queue[front++];//出队
        printf("%c", x);
        count++;
        for (int i = 0; i < G.numVertices; ++i) {
            if (inDegree[i] != 0) {
                inDegree[i]--;
                if (inDegree[i] == 0) {
                    queue[rear++] = G.VerticesList[i];//继续入队
                }
            }
    ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发