文章
8
粉丝
0
获赞
1
访问
557
1.建立一个队列,将所以入度为0顶点入队,之后再依次出队,让每个顶点的入度减一,再判断入度为0的点将其入队,直至队列为空,若遭遇过仍有元素未入队,存在环路,无拓扑序列,若队列中有两个以上的元素,则不唯一
2
int uniquely(MGraph G) { int inDegree[MAXV];//保存入度 char queue[MAXV];//保存度为0的节点 int front = 0, rear = 0;//队首和队尾 int count = 0;//顶点计数 for (int i = 0; i < G.numVertices; ++i) { for (int j = 0; j < G.numVertices; ++j) { inDegree[i] += G.Edge[j][i];//统计每个顶点的入度 } } for (int i = 0; i < G.numVertices; ++i) {//将入度为0的点入队 if (inDegree[i] == 0) { queue[rear++] = G.VerticesList[i]; } } while (rear - front == 1) {//保证拓扑排序唯一 char x = queue[front++];//出队 printf("%c", x); count++; for (int i = 0; i < G.numVertices; ++i) { if (inDegree[i] != 0) { inDegree[i]--; if (inDegree[i] == 0) { queue[rear++] = G.VerticesList[i];//继续入队 } } ...
登录后发布评论
暂无评论,来抢沙发