文章
63
粉丝
0
获赞
0
访问
13.3k
(1)计算初始入度:遍历图的邻接矩阵,计算所有顶点的初始入度,并存储在一个入度数组inDegree中。初始化队列:创建一个队列,将所有初始入度为 0 的顶点加入队列。循环处理:当队列不为空时,执行循环: a. 检查当前队列中的元素个数。如果队列中的元素个数大于 1,说明此时有多个顶点可以作为拓扑序列的下一个元素,因此拓扑序列不唯一。此时可以直接返回 0。 b. 从队列中取出一个顶点 u(由于上一步的判断,如果程序能继续,队列中只会有一个元素)。 c. 遍历顶点 u 的所有出边(即在邻接矩阵中查找 Edge[u][v] == 1 的所有顶点 v)。 d. 将所有邻接顶点 v 的入度减 1(inDegree[v]--)。 e. 如果某个邻接顶点 v 的入度在减 1 后变为 0,则将 v 加入队列。循环结束后,检查已经输出的顶点总数。如果总数小于图的总顶点数,说明图中存在环路,没有拓扑序列,自然也不是唯一的,应返回 0。如果总数等于图的总顶点数,且在整个过程中从未触发步骤a的判断,则说明拓扑序列是唯一的,返回 1。
(2)
#define MAXV 100 // 假设最大顶点数为100
int uniqueIv(MGraph G) {
// 步骤(1): 动态分配内存用于存储入度,并计算所有顶点的初始入度
int* inDegree = (int*)malloc(G.numVertices * sizeof(int));
if (inDegree == NULL) {
// 内存分配失败,返回错误码
return -1;
}
// 将入度数组初始化为0
memset(inDegree, 0, G.numVertices * sizeof(int));
for (int i = 0; i < G.numVertices; ++i) {
for (int j = 0; j < G.numVertices; ++j) {
if (G.Edge[i][j] != 0) {
inDegree[j]++;
}
}
...
登录后发布评论
暂无评论,来抢沙发