有向图的拓扑排序
下面这段代码//有向图的拓扑排序
#include <stdio.h>
#include <malloc.h>
#define MAXV 50
#define INF 32767
typedef int InfoType;
//邻接矩阵存储方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//邻接表存储方法
typedef struct ANode
{
int adjvex;
struct ANode *nextarc;
InfoType info;
} ArcNode;
typedef struct
{
VertexType data;
int count;
ArcNode *firstarc;
} VNode;
typedef VNode AdjList[MAXV];
typedef struct
{
AdjList adjlist;
int n,e;
} ALGraph;
//将邻接矩阵g转换成邻接表G
void MatToList(MGraph g,ALGraph *G)
{
int i,j,n=g.n;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;i<n;i++) G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)
{
for(j=n-1;j>=0;j--)
{
if(g.edges[i][j]!=INF&&g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
p->info=g.edges[i][j];
G->adjlist[i].firstarc=p;
}
}
}
G->n=n;G->e=g.e;
}
//拓扑排序算法
void TopSort(ALGraph *G)
{
int i,j;
int St[MAXV],top=-1;
ArcNode *p;
for(i=0;i<G->n;i++) G->adjlist[i].count=0;
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
while(p!=NULL)
{
G->adjlist[p->adjvex].count++;
p=p->nextarc;
}
}
for(i=0;i<G->n;i++)
{
if(G->adjlist[i].count==0)
{
top++;
St[top]=i;
}
}
while(top>-1)
{
i=St[top];top--;
printf("%d ",i);
p=G->adjlist[i].firstarc;
while(p!=NULL)
{
j=p->adjvex;
G->adjlist[j].count--;
if(G->adjlist[j].count==0)
{
top++;
St[top]=j;
}
p=p->nextarc;
}
}
}
//主函数
int main()
{
int i,j,n;
MGraph g;
ALGraph *G;
printf("请输入有向图的顶点个数:");//6
while(scanf("%d",&n)!=EOF)
{
printf("请输入有向图的邻接矩阵:\n");
/*
0 1 32767 32767 32767 32767
32767 0 1 32767 32767 32767
32767 32767 0 1 32767 32767
32767 32767 32767 0 32767 32767
32767 1 32767 32767 0 1
32767 32767 32767 1 32767 0
*/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&g.edges[i][j]);
}
}
g.n=n;
MatToList(g,G);
printf("有向图的拓扑排序序列为:");
TopSort(G);
printf("\n请输入有向图的顶点个数:");
}
return 0;
}
运行之后就不知道怎么搞了啊。要向老师答辩.有谁能帮忙分析下怎么解释和运用这个程序啊!谢谢啦