- #include "stdafx.h"
- #include <stdio.h>
- #include <stdlib.h>
- void exit(int);
- #define MaxVerNum 40
- typedef struct{
- int arcs[MaxVerNum][MaxVerNum];
- int vexnum;
- }MGraph;
- void Input(MGraph *g)
- {
- int n,i,j;
- printf("请输入顶点个数,顶点个数必须在[1...%d]\\n",MaxVerNum);
- scanf("%d",&n);
- if(n<0||n>MaxVerNum){
- printf("顶点的个数必须在[1...%d]\\n",MaxVerNum);
- exit(-1);
- }
- g->vexnum=n;
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- g->arcs[i][j]=0;
- printf("请输入边的顶点i,j必须在[0...%d]\\n",n-1);
- do{
- scanf("%d%d",&i,&j);
- if(i==-1&&j==-1)
- break;
- if(i<0||i>=n||j<0||j>=n){
- printf("边的顶点i,j必须在[0...%d]\\n",n-1);
- continue;
- }
- g->arcs[i][j]=1;
- }while(9);
- }
- void juzhen(MGraph *g)
- {
- int c=0,i,j;
- printf("\\n图G的邻接矩阵如下:\\n");
- for(i=0;i<g->vexnum;i++)
- for(j=0;j<g->vexnum;j++)
- {printf("%d ",g->arcs[i][j]);
- if(++c%g->vexnum==0)
- printf("\\n");
- }
- }
- void cal_in(MGraph *g,int in[])
- {
- int i,j;
- for(i=0;i<g->vexnum;i++)
- in[i]=0;
- for(i=0;i<g->vexnum;i++)
- for(j=0;j<g->vexnum;j++)
- if(g->arcs[i][j])
- in[j]++;
- }
- void TopSort(MGraph *g,int in[])
- {
- int s=-1,c=0,i,j;
- printf("\\n图G的拓扑排序如下:\\n");
- for(i=0;i<g->vexnum;i++)
- if(in[i]==0){
- in[i]=s;
- s=i;
- }
- while(s!=-1){
- printf("V%d ",s);
- c++;
- i=s;
- s=in[s];
- for(j=0;j<g->vexnum;j++){
- if(g->arcs[i][j])
- in[j]--;
- if(in[j]==0){
- in[j]=s;
- s=j;
- }
- }
- }
- if(c<g->vexnum){
- printf("\\n图G中包含环路!\\n");
- }
- void main()
- {
- MGraph g;
- int InDegree[MaxVerNum];
- Input(&g);
- juzhen(&g);
- cal_in(&g,InDegree);
- TopSort(&g,InDegree);
- }
- //该片段来自于http://www.codesnippet.cn/detail/050120131301.html
来源: http://www.codesnippet.cn/detail/050120131301.html