文章

2

粉丝

0

获赞

0

访问

62

头像
2024年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月28日 22:28
阅读数 31

1. 代码基本思想:统计每个顶点的入度,每次看是否有唯一顶点入度为0,如果不是的话则不存在唯一拓扑序列,同时统计循环次数,若入度为0的顶点数等于图的顶点数,则存在唯一拓扑序列,否则不存在

2. 代码如下:

int uniquely (MGraph G) {
 if (!G) 
  return 0;//图为空,直接返回
 int count = 1, id = -1;
 int *indegree = (int*)malloc(sizeof(G.numVertices*int);//为入度数组indegree分配空间
 for (int i = 0; i < G.numVertices; i ++) {
  indegree[i] = 0;
  for (int j = 0; j < G.numVertices; j ++)
   indegree[i] += G.Edge[j][i];
  if (!indegree[i])
   if (id == -1) id = i;//记录入度为0的结点
   else return 0;//初始入度为0结点不唯一,一定不存在唯一拓扑排序,直接返回
 }
 if (id == -1) return 0;//不存在入度为0的结点,无拓扑排序,直接返回
 int iid;
 while (id > 0) {
  iid = id;
  id = -1;
  for (int i = 0; i < G.numVertices; i ++) {
   if (G.numVertices[iid][i]){
    indegree[i] --;
    if (indegree[i] == 0) 
     if (id == -1) {
      id = i;
      count ++;
     }
     else return 0;//入度结点不为1,拓扑排序一定不唯一,直接返回
  }
 }
 if (count == G.numVertices) 
  return 1;//存在唯一拓扑排序序列;

 return 0;
}


 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发