计算机应用专业数据结构上机考试辅导（2）

编一C程序，它能根据读入的数据构造有向图G，并输出G的DFS遍历序列（从V0开始），图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2……Vi Vin -1 -1（-1，-1为输入结束标记，其余的值都=0且<n），它们都是整数，且100n0.

（注：程序的可执行文件名必须是 e3.exe）。

#include<stdio.h
typedefenum{False,True}Boolean;

intG[100][100];
intn;

voidCreatG()/*建立图的邻接矩阵G[][]*/
{inti,j;
printf("Inputthenumberofthenode:");
scanf("%d",&n);
printf("n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
G[i][j]=0;
do
{scanf("%d%d",&i,&j);
G[i][j]=1;
}while((i!=-1)&&(j!=-1));
}

voidTopSort()/*拓扑排序,输出拓扑序列*/
{inti,j;
intdegree[100];/*按照无前驱顶点优先思想,degree[]存放个节点的入度.*/
Booleanvisited[100],flag=True;
printf("TheTopolgicalOrderasfollow:");
for(i=0;i<n;i++)
{degree[i]=0;
visited[i]=False;
}
printf("n");
while(flag==True)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
degree[i]=G[j][i]+degree[i];
i=0;
while((i<n)&&(degree[i]!=0)||visited[i]==True)i++;/*最先输出入度为0的顶点.*/
if(i<n)/*所有节点均已输出结束,否则说明存在环,无拓扑序列*/
{printf("%d",i);
visited[i]=True;
for(j=0;j<n;j++)
{G[i][j]=0;degree[j]=0;}
}
elseflag=False;
}
}

main()
{CreatG();
TopSort();
}