編一C程序,它能根據(jù)讀入的數(shù)據(jù)構(gòu)造有向圖G,并輸出G的DFS遍歷序列(從V0開始),圖的輸入形式為n V0 Vi0 V1 Vi1 V2 Vi2……Vi Vin -1 -1(-1,-1為輸入結(jié)束標(biāo)記,其余的值都 =0且 n),它們都是整數(shù),且100 n 0.
(注:程序的可執(zhí)行文件名必須是 e3.exe)。
#include stdio.h
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",
printf("\n");
for (i=0;i i++)
for (j=0;j j++)
G[i][j]=0;
do
{ scanf("%d %d", i,
G[i][j]=1;
}while ((i!=-1) (j!=-1));
}
void TopSort() /*拓?fù)渑判?輸出拓?fù)湫蛄?/
{ int i,j;
int degree[100]; /*按照無前驅(qū)頂點(diǎn)優(yōu)先思想,degree[]存放個(gè)節(jié)點(diǎn)的入度.*/
Boolean visited[100],flag=True;
printf("The Topolgical Order as follow:");
for (i=0;i i++)
{ degree[i]=0;
visited[i]=False;
}
printf("\n");
while(flag==True)
{
for (i=0;i i++)
for (j=0;j j++)
degree[i]=G[j][i]+degree[i];
i=0;
while ((i n) (degree[i]!=0)||visited[i]==True) i++; /*最先輸出入度為0的頂點(diǎn).*/
if (i n) /*所有節(jié)點(diǎn)均已輸出結(jié)束,否則說明存在環(huán),無拓?fù)湫蛄?/
{printf(" %d",i);
visited[i]=True;
for(j=0;j j++)
{G[i][j]=0; degree[j]=0;}
}
else flag=False;
}
}
main()
{ CreatG();
TopSort();
}