不好意思。关于图的拓补排序问题,谢谢

lluct

编译成功，但运行结果不是期望的。
[code:1]
#include <stdio.h>
#define vnum 20

typedef struct arcnode
{
  int adjvex;
  int info;
  struct arcnode *nextarc;
} ArcNodeTp;

typedef struct vexnode
{
  int vertex;
  int in;
  ArcNodeTp *firstarc;
} AdjList[vnum];

typedef struct linkgraph
{
  AdjList adjs;
  int vexnum, arcnum;
} LGraphTp;

typedef struct node
{
  int data;
  struct node *next;
} LStackTp;


LGraphTp* Create_LNvGraphP (LGraphTp *ga);

int main (void)
{
  LGraphTp *ga;
  ga = (LGraphTp *) malloc (sizeof(LGraphTp));

  printf("\n有向图\n");
  ga = Create_LNvGraphP(ga);
  Print_LinkList(ga);
  Top_Sort(ga);

}

LGraphTp* Create_LNvGraphP (LGraphTp *ga)
{
  ArcNodeTp *p;
  int vex, arc, vexs, arcnum;
  int i, j, k;

  printf("请输入顶点个数:");
  scanf("%d", &vex);
  printf("请输入边数个数:");
  scanf("%d", &arc);
  ga -> vexnum = vex;
  ga -> arcnum = arc;

  for (i = 0; i < vex; i++)
    {
      ga -> adjs[i].vertex = i + 1;
      ga -> adjs[i].firstarc = NULL;
    }

  for (k = 0; k < arc; k++)
    {
      printf("请输入第%d条边的起始编号和终点编号:", k + 1);
      scanf("%d %d", &i, &j);
      p = (ArcNodeTp *) malloc (sizeof(ArcNodeTp));
      p -> adjvex = j;
      p -> nextarc = ga -> adjs[i - 1].firstarc;
      ga -> adjs[i - 1].firstarc = p;
    }
  return (ga);
}

int Print_LinkList (LGraphTp *ga)
{
  ArcNodeTp *p;
  int k;
  printf("\n目前输入的邻接表为:\n\n");

  for (k = 0; k < ga -> vexnum; k++)
    {
      printf("V%d:%d |", k + 1, ga -> adjs[k].vertex);
      p = ga -> adjs[k].firstarc;
      while (p != NULL)
        {
          printf(" -> %d", p -> adjvex);
          p = p -> nextarc;
        }
      printf("\n\n");
    }
}

int InitStack(LStackTp **ls)
{
  *ls = NULL;
}

int Push(LStackTp **ls, int x)
{
  LStackTp *p;
  p = (LStackTp *) malloc (sizeof(LStackTp));
  p -> data = x;
  p -> next = *ls;
  *ls = p;
}

int Pop(LStackTp **ls, int *x)
{
  LStackTp *p;
  if (*ls != NULL)
    {
      p = *ls;
      *x = p -> data;
      *ls = (*ls) -> next;
      free(p);
      return 1;
    }
  else
    return 0;
}

int EmptyStack(LStackTp **ls)
{
  if (*ls == NULL)
    return (1);
  else
    return (0);
}

int GetTop(LStackTp **ls , int *x)
{
  if (*ls != NULL)
    {
      *x = (*ls) -> data;
      return 1;
    }
  else
    return 0;
}

int Top_Sort (LGraphTp *ga)
{
  LStackTp *S;
  ArcNodeTp *p;
  int count, i, v;
  InitStack(&S);

  for (i = 0; i < ga -> vexnum; i ++)
    {
      if (ga -> adjs[i].in == 0)
        Push(&S,i);
    }
  count = 0;
  while (! EmptyStack(&S))
    {
      Pop (&S, &v);
      printf("%d ", v);
      count ++;
      p = ga -> adjs[i].firstarc;
      
      while (p != NULL)
        {
          (ga -> adjs[p -> adjvex].in) --;
          if (ga -> adjs[p -> adjvex].in == 0)
            Push(&S, p -> adjvex);
          p = p -> nextarc;
        }
    }
  if (count < ga -> vexnum)
    {
      printf("\n图中有环!\n");
      return 0;
    }
  else
    return 1;
}
[/code:1]

sagaeon

[code:1]
有向图
请输入顶点个数:4
请输入边数个数:3
请输入第1条边的起始编号和终点编号:1 2
请输入第2条边的起始编号和终点编号:2 4
请输入第3条边的起始编号和终点编号:1 3

目前输入的邻接表为:

V1:1 | -> 3 -> 2

V2:2 | -> 4

V3:3 |

V4:4 |

3 2 1 0
[/code:1]
结果是不是这样？你想的结果是什么样的啊。

lluct

[quote:6efb52ccf7="sagaeon"][code:1]
有向图
请输入顶点个数:4
请输入边数个数:3
请输入第1条边的起始编号和终点编号:1 2
请输入第2条边的起始编号和终点编号:2 4
请输入第3条边的起始编号和终点编号:1 3

目前输入的邻接表为:

V1:1 | -> 3 -> 2

V2:2 | -> 4

V3:3 |

V4:4 |

3 2 1 0
[/code:1]
结果是不是这样？你想的结果是什么样的啊。[/quote]
根据你输入的，正确应该是：
1 -> 3 -> 2 -> 4
或
1 -> 2 -> 4 -> 3
三个答案其中一种。
（程序却是 3 -> 2 -> 1 -> 0）

lluct

图示：

sjinny

lluct, 你的图是用鼠标“手绘”的吧？建议用xfig来画图……

lluct

[quote:516959e58f="sjinny"]lluct, 你的图是用鼠标“手绘”的吧？建议用xfig来画图…… [/quote] 早讲阿。

sagaeon

明白了，再看看。

quarkonics

你这个域没有初始化
ga -> adjs.in
应该在创建图得时候就把入度给初始化了

quarkonics

有几个地方错了
[code:1]
int Top_Sort (LGraphTp *ga)
{
  LStackTp *S;
  ArcNodeTp *p;
  int count, i, v;
  InitStack(&S);

  for (i = 0; i < ga -> vexnum; i ++)
    {
      if (ga -> adjs[i].in == 0)
   Push(&S,i);
    }
  count = 0;
  while (! EmptyStack(&S))
    {
      Pop (&S, &v);
      printf("%d ", v);//这里应该是v+1
      count ++;
      p = ga -> adjs[i].firstarc; //这里应该是p = ga->adjs[v].firstarc;
      
      while (p != NULL)
   {
     (ga -> adjs[p -> adjvex].in) --; //应该是(ga -> adjs[p -> adjvex-1].in) --;
   if (ga -> adjs[p -> adjvex].in == 0) //这里同上
       Push(&S, p -> adjvex); //同上
     p = p -> nextarc;
   }
    }
  if (count < ga -> vexnum)
    {
      printf("\n图中有环!\n");
      return 0;
    }
  else
    return 1;
}
[/code:1]

lluct

[quote:f1760da3fc="quarkonics"]有几个地方错了
[code:1]
int Top_Sort (LGraphTp *ga)
{
  LStackTp *S;
  ArcNodeTp *p;
  int count, i, v;
  InitStack(&S);

  for (i = 0; i < ga -> vexnum; i ++)
    {
      if (ga -> adjs[i].in == 0)
   Push(&S,i);
    }
  count = 0;
  while (! EmptyStack(&S))
    {
      Pop (&S, &v);
      printf("%d ", v);//这里应该是v+1
      count ++;
      p = ga -> adjs[i].firstarc; //这里应该是p = ga->adjs[v].firstarc;
      
      while (p != NULL)
   {
     (ga -> adjs[p -> adjvex].in) --; //应该是(ga -> adjs[p -> adjvex-1].in) --;
   if (ga -> adjs[p -> adjvex].in == 0) //这里同上
       Push(&S, p -> adjvex); //同上
     p = p -> nextarc;
   }
    }
  if (count < ga -> vexnum)
    {
      printf("\n图中有环!\n");
      return 0;
    }
  else
    return 1;
}
[/code:1][/quote]
不行阿。结点编号还是按顺序倒序输出。我在看看。

sagaeon

[quote:c9b9014fbf="quarkonics"]你这个域没有初始化
ga -> adjs.in
应该在创建图得时候就把入度给初始化了[/quote]
对啊，是不是该这样：[code:1]
LGraphTp* Create_LNvGraphP (LGraphTp *ga)
{
  ArcNodeTp *p;
  int vex, arc, vexs, arcnum;
  int i, j, k;
   
  printf("请输入顶点个数:");
  scanf("%d", &vex);
  printf("请输入边数个数:");
  scanf("%d", &arc);
  ga -> vexnum = vex;
  ga -> arcnum = arc;

  for (i = 0; i < vex; i++)
    {
      ga -> adjs[i].vertex = i + 1;
      ga -> adjs[i].firstarc = NULL;
      ga -> adjs[i].in =0;//加加加~~~~~~~~~
    }

  for (k = 0; k < arc; k++)
    {
      printf("请输入第%d条边的起始编号和终点编号:", k + 1);
      scanf("%d %d", &i, &j);
      p = (ArcNodeTp *) malloc (sizeof(ArcNodeTp));
      p -> adjvex = j;
      p -> nextarc = ga -> adjs[i-1 ].firstarc;
      ga -> adjs[i-1 ].firstarc = p;
      ga->adjs[j-1].in= ga->adjs[j-1].in+1;//加加加~~~~~~~~
    }
  return (ga);
}[/code:1]
并且加上quarkonics兄的修改。

quarkonics

就是这样得

lluct

谢谢你们阿。 在一个初学且教科书上只有伪代码（且错漏百出）的情况下。没有你们的帮助，我看我要绕很多弯才能弄明白。