2024年数据结构真题

//2024年
//采用拓扑排序来判断这个使用邻接矩阵存储的图的拓扑序列是否唯一
//原理是：在出队的时候，判断队列是否为空，要是空队列就说明此时只有一种选择
// (也可以在入度为0的元素全部入队之后判断队列是否只有一种选择)
//不断地判断，直到拓扑序列构建完成，在此之间每次队列都只有一种选择，就说明拓扑排序唯一
//反之，只要存在一次一个元素出队之后队列不为空，就说明拓扑序列不唯一

int uniquely(mgraph g){
    int indegree[maxsize] = {0};

for (int i = 0; i < g.vernum; ++i) {
for (int j = 0; j < g.vernum; ++j) {
if (g.edge[i][j] != 0){
                indegree[j]++;   //初次计算每个顶点的入度
            }
        }
    }
    int queue[maxsize],front = 0,rear = 0;
for (int i = 0; i < g.vernum; ++i) {
if (indegree[i] == 0)
            queue[rear++] = i;  //这里是将此时全部的入度为0的点都入队了；
    }
while (front < rear){
        int u = queue[front++];
if (front != rear)
return 0;
for (int i = 0; i < g.vernum; ++i) {
if (g.edge[u][i] != 0){
                indegree[i]--;
if (indegree[i] == 0)
                    queue[rear++] = i;
            }
        }
    }
if (rear < g.vernum){
printf("having ring\n");  //这里还需要补充一下当图里面存在环路的情况
return 0;
    }
else
return 1;
}