文章

100

粉丝

0

获赞

0

访问

3.8k

头像
2024年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2026年3月28日 18:18
阅读数 23

(1)统计入度:遍历邻接矩阵,计算每个顶点的入度(即指向该顶点的边数)。

入队:将所有入度为 0 的顶点存入栈或队列(这些是没有任何前导工程的任务)。

循环处理:从栈/队列中取出一个顶点。

输出该顶点(或存入结果数组)。

遍历该顶点的所有邻接点,将它们的入度减 1。

如果某个邻接点的入度减为 0,则将其入队。

判断回路:如果输出的顶点数小于图中的总顶点数 n,说明图中存在环(即工程逻辑冲突,A依赖B,B又依赖A)。

(2)

#include <stdio.h>
#include <stdbool.h>

#define MAXV 100 // 假设最大顶点数

typedef struct {
    int numVertices, numEdges;
    char verticesList[MAXV];
    int Edge[MAXV][MAXV];
} MGraph;

// 拓扑排序函数
bool TopologicalSort(MGraph G) {
    int indegree[MAXV] = {0}; // 存储每个顶点的入度
    int stack[MAXV];          // 辅助栈
    int top = -1;
    int count = 0;            // 记录已输出的顶点数

    // 1. 计算所有顶点的入度
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            if (G.Edge[i][j] != 0) {
&n...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发