C语言有向图队列辅助拓扑排序函数修改

Question

C语言通过队列辅助实现拓扑排序函数如下，运行结果显示7,7，显然错误。请问问题出在哪里？如何修改？
文本文档内容：
8
0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20

typedef struct{
    int Edges[MAX][MAX];//边邻接矩阵
    int vexnum;//顶点数
}Graph;

typedef struct{
    int data[MAX];//队列元素
    int front,rear;//队头，队尾指针
}Squeue;
int InitQueue(Squeue &Q)
{
    Q.front=Q.rear=0;
    return 1;
}
int QueueEmpty(Squeue Q)//判队空
{
    if(Q.front==Q.rear)
        return 1;//队空
    else return 0;//队不空
}
int Enqueue(Squeue &Q,int e)//进队
{
    if((Q.rear+1)%MAX==Q.front) return 0;
    Q.rear=(Q.rear+1)%MAX;
    Q.data[Q.rear]=e;
    return 1;
}
int Dequeue(Squeue &Q,int e)//出队
{
    if(Q.front==Q.rear) return 0;
    Q.front=(Q.front+1)%MAX;
    e=Q.data[Q.front];
    return 1;
}

int CreatGraph(Graph &G)//读文件建立邻接矩阵
{
    FILE *fp;
    if((fp=fopen("matrix.txt","r"))==NULL)
    {
      printf("文件打开失败\n");
      return 0;
    }
    
    printf("顶点个数: ");//输出顶点个数
    fscanf(fp,"%d",&G.vexnum);
    printf("%d\n",G.vexnum);
    int i,j;
 
    for(i=1;i<=G.vexnum;i++)
    {
     for(j=1;j<=G.vexnum;j++)
       fscanf(fp,"%d",&G.Edges[i][j]);
    }
    fclose(fp);
   
        //输出边矩阵
    printf("创建无向图边关系如下：\n");
    for(i=1;i<=G.vexnum;i++)
    {
        for(j=1;j<=G.vexnum;j++)
        {
         printf("%3d",G.Edges[i][j]);
        }
        printf("\n");
    }
    return 1;
}
int FirstAdjvex(Graph G,int i)//寻找顶点i的第一个邻接顶点
{
    int k;
    for(k=1;k<=G.vexnum;k++)//遍历第i行的各列
    {
      if(G.Edges[i][k]==1)
          return k;//找到第一个邻接顶点
    }
    return 0;//若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}
int NextAdjvex(Graph G,int i,int j)//寻找顶点i继其邻接点j后的第一个邻接点
{
    int k;
    for(k=j+1;k<=G.vexnum;k++)//遍历第i行的各列
    {
      if(G.Edges[i][k]==1)
          return k;//找到第一个邻接顶点
    }
    return 0;//若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}
void FindDegree(Graph G,int indegree[])//求各顶点入度
{
   int i,j;
   for(i=1;i<=G.vexnum;i++)
       indegree[i]=0;
   for(i=1;i<=G.vexnum;i++)
   {
       for(j=1;j<=G.vexnum;j++)
       if(G.Edges[i][j])
           indegree[j]++;
   }
}
int TopologicalSort(Graph G)
{
    Squeue Q;
    Q=*(Squeue*)malloc(sizeof(Squeue));
   InitQueue(Q);
    //初始化
    int i,j,indegree[MAX];
    FindDegree(G,indegree);
    for(i=1;i<=G.vexnum;++i)
        if(indegree[i]==0)
            Enqueue(Q,i);
    int count=0;
    //排序
    while(QueueEmpty(Q)==0)
    {
      Dequeue(Q,i);
      printf("%d ",i);
      count++;
      for(j=FirstAdjvex(G,i);j;j=NextAdjvex(G,i,j))
      {
        indegree[j]--;
        if(indegree[j]==0)
            Enqueue(Q,j);
      }
    }
        printf("\n");
    if(count<G.vexnum)
        return 0;
    else return 1;
}
int main(void)
{
  Graph G;

  G=*(Graph*)malloc(sizeof(Graph));
  
  CreatGraph(G);
  TopologicalSort(G);
  return 0;
}

Answer 1

修改后的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

typedef struct {
    int Edges[MAX][MAX]; // 边邻接矩阵
    int vexnum;          // 顶点数
} Graph;

typedef struct {
    int data[MAX];      // 队列元素
    int front, rear;    // 队头，队尾指针
} Squeue;

int InitQueue(Squeue *Q) {
    Q->front = Q->rear = 0;
    return 1;
}

int QueueEmpty(Squeue Q) { // 判队空
    return Q.front == Q.rear;
}

int Enqueue(Squeue *Q, int e) { // 进队
    if ((Q->rear + 1) % MAX == Q->front) return 0;
    Q->rear = (Q->rear + 1) % MAX;
    Q->data[Q->rear] = e;
    return 1;
}

int Dequeue(Squeue *Q, int *e) { // 出队
    if (Q->front == Q->rear) return 0;
    Q->front = (Q->front + 1) % MAX;
    *e = Q->data[Q->front];
    return 1;
}

int CreatGraph(Graph *G) { // 读文件建立邻接矩阵
    FILE *fp;
    if ((fp = fopen("matrix.txt", "r")) == NULL) {
        printf("文件打开失败\n");
        return 0;
    }
    
    printf("顶点个数: "); // 输出顶点个数
    fscanf(fp, "%d", &G->vexnum);
    printf("%d\n", G->vexnum);
    int i, j;
    
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            fscanf(fp, "%d", &G->Edges[i][j]);
        }
    }
    fclose(fp);

    // 输出边矩阵
    printf("创建无向图边关系如下：\n");
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            printf("%3d", G->Edges[i][j]);
        }
        printf("\n");
    }
    return 1;
}

int FirstAdjvex(Graph G, int i) { // 寻找顶点i的第一个邻接顶点
    int k;
    for (k = 0; k < G.vexnum; k++) { // 遍历第i行的各列
        if (G.Edges[i][k] == 1)
            return k; // 找到第一个邻接顶点
    }
    return -1; // 若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}

int NextAdjvex(Graph G, int i, int j) { // 寻找顶点i继其邻接点j后的第一个邻接点
    int k;
    for (k = j + 1; k < G.vexnum; k++) { // 遍历第i行的各列
        if (G.Edges[i][k] == 1)
            return k; // 找到第一个邻接顶点
    }
    return -1; // 若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}

void FindDegree(Graph G, int indegree[]) { // 求各顶点入度
    int i, j;
    for (i = 0; i < G.vexnum; i++) {
        indegree[i] = 0;
    }
    for (i = 0; i < G.vexnum; i++) {
        for (j = 0; j < G.vexnum; j++) {
            if (G.Edges[i][j]) {
                indegree[j]++;
            }
        }
    }
}

int TopologicalSort(Graph G) {
    Squeue Q;
    InitQueue(&Q);

    // 初始化
    int i, j, indegree[MAX];
    FindDegree(G, indegree);
    for (i = 0; i < G.vexnum; ++i) {
        if (indegree[i] == 0)
            Enqueue(&Q, i);
    }
    int count = 0;
    // 排序
    while (!QueueEmpty(Q)) {
        Dequeue(&Q, &i);
        printf("%d ", i);
        count++;
        for (j = FirstAdjvex(G, i); j != -1; j = NextAdjvex(G, i, j)) {
            indegree[j]--;
            if (indegree[j] == 0)
                Enqueue(&Q, j);
        }
    }
    printf("\n");

    return count == G.vexnum;
}

int main(void) {
    Graph G;
    CreatGraph(&G);
    if (!TopologicalSort(G)) {
        printf("图中存在环，无法进行拓扑排序\n");
    }
    return 0;
}