计算机应用专业上机考试辅导三

文章作者 100test 发表时间 2007:03:10 19:11:21
来源 100Test.Com百考试题网

编一C程序，它能根据读入的数据构造有向图G，并输出G的DFS遍历序列（从V0开始），图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2...Vi Vin -1 -1（-1，-1为输入结束标记，其余的值都>=0且n>0。
（注：程序的可执行文件名必须是 e3.exe）
#include
typedef enum {False,True} Boolean.

int G[100][100].
int n.

void CreatG() /*建立图的邻接矩阵G[][]*/
{int i,j.
printf("Input the number of the node:").
scanf("%d",&.n).
printf("\n").
for (i=0.i for (j=0.j G[i][j]=0.
do
{ scanf("%d %d",&.i,&.j).
G[i][j]=1.
}while ((i!=-1)&.&.(j!=-1)).
}

void TopSort() /*拓扑排序,输出拓扑序列*/
{ int i,j.
int degree[100]. /*按照无前驱顶点优先思想,degree[]存放个节点的入度.*/
Boolean visited[100],flag=True.
printf("The Topolgical Order as follow:").
for (i=0.i { degree[i]=0.
visited[i]=False.
}
printf("\n").
while(flag==True)
{
for (i=0.i for (j=0.j degree[i]=G[j][i] degree[i].
i=0.
while ((i if (i {printf(" %d",i).
visited[i]=True.
for(j=0.j {G[i][j]=0. degree[j]=0.}
}
else flag=False.
}
}

main()
{ CreatG().
TopSort().
}