文章
15
粉丝
0
获赞
1
访问
7.8k
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];//继续入队
}
}
...
登录后发布评论
暂无评论,来抢沙发