文章
2
粉丝
0
获赞
0
访问
62
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;
}
登录后发布评论
暂无评论,来抢沙发