#defiｎeN20
＃ｄｅｆineTRUE1
＃deｆｉne FＡＬSE 0
＃deｆiｎeMＡX100
ｉnｔvｉsitｅd[N］；ﻩ/*访问标志数组*／
typedｅfsｔrｕcｔ{ ／*辅助队列的定义＊/
ｉntdatａ［N］；
iｎｔｆrｏnｔ，rear；
}ｑuｅue;
tｙpedef ｓtruｃt｛ﻩ/＊图的邻接矩阵表示＊/
intvexnuｍ，arcnum；
cｈarvｅxs[N］;
iｎtａrcｓ[N］[N］；
}MGｒａph；
voidcreａteＧraｐh（MＧrapｈ＊ｇ）；/*建立一个无向图的邻接矩阵＊／
voiｄ dfs（inti，ＭGrａph*g）; /＊从第i个顶点出发深度优先搜索＊/
voidtｄｆs（ＭGraph＊g）; ﻩ／*深度优先搜索整个图＊／
voidbfs（intｋ,MＧraph *ｇ）; ／*从第k个顶点广度优先搜索＊/
voidtbｆｓ（MGｒａｐh＊g）; ﻩ／＊广度优先搜索整个图*／
vｏid iｎit_visit（）； /＊初始化访问标识数组＊／
voiｄcｒeａｔeGrapｈ（ＭGraph＊ｇ）｛ ／＊建立一个无向图的邻接矩阵＊/
int i=0，j，e=0；
ｃharｖ；
g—＞vexnum＝0;
g—>arcｎuｍ＝0；
printf（”\n输入顶点序列（以#结束）:
\ｎ”）；
ｗhile （（v=getchａｒ（））！
＝＇#'）｛
ｇ－〉ｖｅｘs[i］＝ｖ;/*读入顶点信息＊/
i＋+；
}
g－>vexｎum=i； /＊顶点数目*/
ｆor（i=0；ｉ<ｇ-＞vexnｕm；ｉ＋+） /*邻接矩阵初始化*／
for（j=０;j〈g—>ｖexｎuｍ；j++）
g-〉arcｓ［i]［ｊ］=0;/*
（1）—邻接矩阵元素初始化为0*/
ｐｒinｔｆ（＂＼n输入边的信息（顶点序号，顶点序号），以（—1，-1）结束:
\n"）;
ｓｃanf（”％d,％d”，&i，&j）； ﻩ/*读入边（ｉ，ｊ）*/
whｉle（ｉ！
＝－1）｛ ﻩ／*读入i为－1时结束＊/
g-〉ａrcs［i］［j］=1；／＊
（2）-i,ｊ对应边等于１*/
e+＋；
scａnf（＂%d,%d”，&ｉ，&ｊ）;
｝
g—〉arcｎｕｍ=ｅ；/＊边数目*/
}/＊ creatｅＧrａph＊／
/*（３）-—－从第ｉ个顶点出发深度优先搜索，补充完整算法*／
void dfｓ（ｉｎｔi,ＭGraph＊g）
｛
inｔj；
printf（”%c”,g－>vｅxｓ［i]）；
visiｔed[i］＝1；
for（j＝0;j＜ｇ－〉ｖeｘｎum；j++）
if（（g－〉aｒcs［ｉ］［j］=＝１）＆&（!
viｓｉｔｅｄ［j］））
dfs（j，g）；
｝
/＊ dfs＊/
voiｄｔdfs（MGrａｐｈ*g）｛ ／＊深度优先搜索整个图*/
ｉnt i;
printｆ（”\n从顶点%C开始深度优先搜索序列:
”，ｇ->vexs[0］）;
for （ｉ=０;i〈g—>vexnum；ｉ++）
if （visited[ｉ］！
=1） /*（4）--—对尚未访问过的顶点进行深度优先搜索*/
dfs（i，g）；
printf（＂\ｎ"）；
}/*tdfs*/
voidbfs（iｎt k, MGrａph*g）{ /*从第k个顶点广度优先搜索＊/
intｉ，ｊ；
qｕeueqlisｔ,*q;
q=＆qliｓｔ；
ｑ—>rear＝０；
ｑ—〉front=0；
pｒｉｎtｆ（"%c＂,g—＞ｖｅxｓ[ｋ］）；
ｖisited［k]＝TＲUＥ；
ｑ-＞dａｔａ［ｑ-＞rｅar］=k;
q->rear=（q－>rear+1）%N；
ｗhｉle（ｑ->reａr!
=q—>ｆrｏｎｔ）｛ /＊当队列不为空，进行搜索＊／
i=ｑ—＞ｄata［ｑ—〉front］；
q-〉frｏnt=（q－＞fronｔ＋1）％N;
fｏr（j=0；j〈g—＞veｘnｕｍ;ｊ++）
ｉf（（g－＞ａｒcs［i]［ｊ］=＝１）＆&（！
visiteｄ［ｊ]））｛
prｉnｔf（＂％c”,g-＞vexs［ｊ]）;
visｉｔed［j］=TRUE；
q->datａ[q—〉reａr]=j;／*（５）—--刚访问过的结点入队*／
q－〉rear=（q-＞ｒear+1）%MAX； /＊（6）-－—修改队尾指针*/
｝
｝
}/＊bfs＊/
voiｄtbfs（ＭGrapｈ ＊g） ｛ /＊广度优先搜索整个图*/
inｔi;
ｐrinｔf（＂＼n从顶点％C开始广度优先搜索序列：
”，g-〉veｘs[0］）;
for（i＝0；ｉ〈ｇ-〉vexnum;i++）
if（viｓｉted[i］！
=TRＵＥ）
bfs（i,g）；ﻩﻩﻩﻩ／*从顶点ｉ开始广度优先搜索＊／
printf（"\n＂）;
｝/*tbｆｓ＊/
ｖｏiｄｉniｔ_vｉｓiｔ（）｛ /*初始化访问标识数组＊/
inti；
fｏr（i＝0;ｉ ｖｉsited[i]＝FALSE;
｝
iｎtmａin（）｛
ＭGraphgａ；
int i，j；
ｐrintf（"***＊*＊＊*＊＊＊图邻接矩阵存储和图的遍历**＊*＊*＊＊＊＊*＼ｎ＂）;
printf（＂\n１—输入图的基本信息：
\n"）;
cｒeateＧraｐh（＆gａ）；
prｉntｆ（”\ｎ2—无向图的邻接矩阵：
\n＂）；
for（ｉ=0;ｉ〈ｇａ。
vexnum；i＋+）｛
fｏr（j=0；j〈ｇa．ｖｅxnum；ｊ++）
pｒintf（＂％3d",ga．aｒcｓ［i］[ｊ］）；
printf（”\n"）；
}
pｒiｎtf（"\ｎ３—图的遍历：
\n”）；
ｉnｉt_visｉt（）;/＊初始化访问数组＊/
tdfs（＆gａ）;/＊深度优先搜索图＊/
init_visit（）；
tｂfs（&gａ）;／＊广度优先搜索图＊/
reｔurn０;
｝
2、编写程序exp7＿2.ｃ，实现图的邻接表存储和拓扑排序算法。
以图７—2的有向图为例,补充完整程序，调试运行并写出运行结果。
运行结果:
（包括输入数据）
eｘp7_2.c程序代码参考如下：
#incｌude＜ｓtdio．ｈ〉
＃incｌuｄe〈malloc.h＞
＃ｄefineN20
／*图的邻接表:
邻接链表结点＊／
typeｄefｓtruct EdｇeＮｏdｅ｛
iｎtaｄｊｖeｘ; ／*顶点序号*/
stｒuctＥdgeNode ＊neｘt；/＊下一个结点的指针*/
｝EdgeNｏde;
／＊图的邻接表：
邻接表＊/
tyｐｅdefｓtrｕctＶＮode{
charｄａta；/＊顶点信息＊/
iｎｔind; /*顶点入度＊／
ｓtｒuctＥｄgeＮｏde*link;/*指向邻接链表指针*/
}VNode；
tｙpｅdｅfsｔｒuctALgｒaph{/*图的邻接表*／
intvｅxｎｕm,arcnum;／*顶点数、弧数*／
VNodeaｄjlist[N］；
｝AＬGraph;
voｉｄｃreatｅGrａｐh＿lisｔ（ＡＬGrapｈ*g）;/＊建立有向图的邻接表＊/
voidtopSort（ＡLGraph ＊ｇ）； ／＊拓扑排序*/
/*建立有向图的邻接表＊／
voidｃreateGrａph_lｉst（ALGraph ＊g）{
intｉ，j,e;
ｃhａrv；
EdgｅＮode*s；
i＝0；
e＝0；
ｐrinｔf（"＼n输入顶点序列（以＃结束）：
\n”）；
whiｌe（（v=getｃhar（））！
=＇＃’） ｛
g—〉ａdｊlｉｓｔ[ｉ］。
data＝ｖ; ／＊读入顶点信息＊/
g—>adjlisｔ[i].ｌink=ＮULL；
g—＞adjlist[i］．inｄ=0；
ｉ++；
｝
g-＞vexnum=i；／*建立邻接链表＊／
pｒintf（”＼n请输入弧的信息（顶点序号，顶点序号），以（－1,－1）结束：
＼n＂）;
ｓcanf（＂％ｄ,%d"，＆i,&j）；
ｗhiｌｅ（i！
=－１）｛
s＝（sｔructEｄgｅNodｅ*）ｍalloc（sizｅof（EｄgｅＮodｅ））；
ｓ—>adｊｖｅx＝j；
s—＞ｎｅｘｔ=ｇ—>adjlist［i].lｉnk; ； ／＊
（1）s插入链表＊／
g->adjlｉst[i]。
ｌiｎk=s；
g－〉aｄjlist[j］．ｉnd++；/＊
（2）顶点j的入度加1＊/
e＋+;
scanf（＂％d，%d”，＆i，＆j）；
｝
g—>arcnum=e；
}/＊creaｔeGraph_lisｔ＊/
voidtopSｏrt（ALGrａph＊ｇ）{/＊拓扑排序*/
iｎtｉ,ｊ,k，top=０，m=0，ｓ[N］; /＊ｍ为拓扑排序输出的结点数＊/
EdgｅNｏｄe ＊p;
for（i＝0; i ｉｆ（!
g－＞ａdjlist[ｉ］。
ｉnd）
{
/*（3）入度为0的顶点入栈＊/
s［ｔop++］＝i；
}
prｉnｔf（”\ｎ输出拓扑序列：
＂）;
whilｅ（tｏp>0）｛
ｊ＝s［—－top］；
printf（"%c”，g－〉adjlist［j]．data）；
m+＋;
p=g－〉ａｄjｌist［ｊ］.ｌink；
while（ｐ!
=NUＬL） {
k=ｐ－>aｄｊvｅx;
g-〉aｄｊlist［k]．inｄ-—； /*顶点ｋ入度减1*／
if（g->adjlisｔ［k].ind==0） /＊顶点k入度为0，进栈＊/
s［ｔop++]=k；
p=p－>next;
}
｝
ｐrintf（"\n共输出％ｄ个顶点\ｎ＂，m）；
if（ｍ〈ｇ—>ｖｅxnum）/*（４）当输出顶点数小于图的顶点数，表示有环＊/
prｉｎtf（”图中有环！
"）；
elsｅ
priｎｔf（”图中无环！
＂）;
｝/*tｏpＳort*/
intmaiｎ（）｛
ALGｒaph g;
ｉnti；
EdgeNｏde *s；
printｆ（”＊＊***＊＊＊＊＊＊图的邻接表存储结构和拓扑排序＊＊*＊＊＊*＊*＊＊\ｎ＂）;
pｒintf（"\ｎ1－输入图的基本信息：
\n＂）；
creaｔeＧｒaph_ｌｉｓt（&ｇ）; ／*创建图的邻接表存储结构＊／
printf（"\ｎ2－图的邻接表：
”）;
for（i=０； i＜g．vｅxnｕm； i+＋）｛/＊输出图的邻接表存储结构＊/
prｉnｔｆ（"＼n％ｃ,％d：
"，g.aｄｊlist［ｉ］。
data,g.ａdjlist[ｉ].ｉｎｄ）;
s＝g。
adjliｓt[i］.ｌｉnｋ；
wｈｉle（s!
=ＮULL）{
printｆ（＂-＞%ｄ＂,ｓ->ａdjvｅｘ）；
s=s—〉next；
}
｝
pｒintｆ（＂\n＂）;
priｎtf（”\n３-根据图的邻接表实现拓扑排序:
＼n"）；
ｔｏｐＳort（&g）； /＊进行拓扑排序＊／
retｕrｎ0;
｝
（3）调试下面给出的图的信息,写出运行结果，画出该有向图.
ABＣＤEF＃
1,0
１，３
2，1
２，５
3,2
3,４
３，5
4,0
5，0
5，1
5,４
—1，-1
3、编写程序exp7_3．c，实现带权图的存储、图的最小生成树及单源最短路径算法.
以图７—３（求该图最小生成树）和图７-４（求该图的单源最短路径）为例,补充完整程序，调试运行并写出运行结果。
运行结果:
（包括输入数据）
eｘｐ7_３．c程序代码参考如下:
＃inｃlｕdｅ＜sｔdio。
h＞
#definｅＮ20
#definｅTRＵE１
#definｅINF1０00２766 /*邻接矩阵中的无穷大元素＊／
＃ｄｅfiｎe INＦIN 1００027６7 ／＊比无穷大元素大的数*／
typｅdefsｔruｃｔ{／＊图的邻接矩阵表示*/
ｉntｖexｎuｍ，arｃnuｍ；
charveｘｓ[Ｎ]；
int arｃs[N］［N］；
｝MGraph；
voidprｉnｔPａtｈ（MGrapｈg， ｉntsｔａrｔVex,iｎｔＥnｄVex, intpath［][N］）;/＊打印最短路径＊/
voidcrｅaｔｅMGraph_ｗ（MGrａph*ｇ,ｉｎtflaｇ）； /＊建带权图的邻接矩阵*/
voｉｄpｒim（MGraｐh＊g，iｎｔ ｕ）； ／*求最小生成树Prim算法，ｕ为出发顶点＊/
voiddijkｓtrａ（MＧrapｈg，intｖ）； /*dijkstra算法求单源最短路径＊/
ｖoｉd creａｔｅMＧraph_w（MGraph *g，intｆｌａg）｛
／＊建带权图的邻接矩阵，若flａg为１则为无向图，flａg为0为有向图*／
iｎti,j，ｗ;
ｃharv；
g—>vexnum=0；
g->aｒcｎum＝０;
i=0;
printｆ（＂\n输入顶点序列（以#结束）：
\ｎ＂）;
whilｅ（（v=getchaｒ（））！
＝'＃’）{
g-＞veｘｓ[i］=v; /＊读入顶点信息＊/
ｉ＋+;
}
g—>vexnum=i;
fｏｒ（i=0; i＜6; i+＋）/*邻接矩阵初始化*/
ｆor（ｊ=0；j<６； ｊ＋+）
ｇ-〉arcs[i][j］=INＦ;
prｉntｆ（＂\ｎ输入边的信息:
（顶点，顶点,权值），以（—1，-1，—1）结束\ｎ”）;
scanf（”％d，%d，％d"，＆i，&ｊ，&w）;/*读入边（i,ｊ，w）＊/
whｉlｅ（i!
＝-１）{ /*读入ｉ为-1时结束＊/
g->arcs[i］［j］＝w;
if（flaｇ==１）
g->arcs[j］［ｉ］=w；
ｓcaｎf（"%d,％ｄ，%d",＆i，＆j，＆w）；
}
}/*creａteMGrapｈ_w＊/
ｖｏiｄ ｐrｉm（MGraph*ｇ，ｉnｔｕ）｛/＊求最小生成树Prim算法，u为出发顶点*/
intloｗcost［N］,ｃlosesｔ[N］，i,j，k，miｎ；
ｆor（i=0;i〈g—〉vexnum;ｉ++）{/＊求其他顶点到出发顶点u的权*/
lowcｏsｔ［ｉ]＝ｇ-〉arcs[u］［j］;/＊
（1）—顶点i到u的代价最小的边权值*／
cloｓeｓｔ[ｉ］=u;
｝
ｌowcost［u］=0;
pｒintf（"＼n最小生成树：
\ｎ"）;
ｆｏr（i=1; i min＝IＮＦIＮ；
ｆor（ｊ＝0；j＜g－＞vexnum；j++） ／＊选择得到一条代价最小的边＊/
if（lowcｏｓｔ［ｊ]！
＝0＆&lowｃoｓｔ[j］〈ｍiｎ）{
ｍｉn＝loｗcost[j］；／＊（２）-修改当前最小边＊／
k=j;
}
prｉntf（＂（%c，％c）—－%d\n”,g－>vexｓ[ｃlosesｔ[k]］，ｇ—＞vexs［ｋ］,ｌowcost［k]）；／＊输出该边*/
lowcosｔ［k］=0; ／*顶点k纳入最小生成树＊/
for（j=0； j〈ｇ—>vexnｕｍ；j++） /＊求其他顶点到顶点ｋ的权＊/
if（g－〉arcs[ｋ］[j］！
＝0&＆g—>arcs[k］［j］＜lowcoｓｔ［j］）{
lowcost［j]=ｇ—〉aｒcs[k］[j］； /＊（3）—其他顶点到k的代价最小的边权值*/
clｏsest［j］=ｋ;
}
｝
｝/*priｍ*/
voｉd prｉntPａｔｈ（MGraphg，int startVｅx，intＥndVex，iｎtpath［］[N]）{
intstacｋ［N］，top=0; //堆栈
inti,k，j;
inｔflａg［Ｎ］;//输出路径顶点标志
k=EnｄVｅx;
for（i=0；i〈g。
vｅｘnuｍ；i++）flag［i]＝0;
j=ｓtartVeｘ；
ｐrintｆ（＂％c”，g。
vｅxs［ｊ］）；
flag［ｊ]＝1;
ｓtａck[ｔｏp++]=k；
while（ｔｏｐ>0）｛//找j到k的路径
ｆoｒ （i=０；i<ｇ.vexnum;i＋+）｛
if（ｐatｈ[ｋ］[i］==1 &＆ fｌaｇ[i］==０）{ //ｊ到k的路径含有i顶点
if（g．arcs[j］[ｉ］!
=IＮF）{//j到i的路径含有中间顶点
pｒｉntf（”-＞ %c（%ｄ）＂,ｇ。
ｖexs［i]，g.arcs[j]［ｉ］）；//输出j到ｋ路径顶点i
flag［i]=1；
j=ｉ;
ｋ＝staｃk［-—top］；
ｂｒeａk;
｝
else
ｉf（i!
=k） sｔack［toｐ＋+]=i；
｝
}
｝
if（ｆlａg[ｋ]＝=0）priｎtｆ（”—〉％c（％ｄ）",g.ｖexs［ｋ］，g．arcｓ［j］［k］）；
｝
voｉddｉjｋstra（MＧｒapｈｇ,ｉntv）｛/*ｄijksｔra算法求单源最短路径＊／
int s[N］，ｐａｔh［Ｎ］[N］,ｄisｔ[N]；
int mindis,i,ｊ，u,ｋ;
fｏr（i=０;i dist［i]=ｇ.ａｒｃs[v］［i］;
s［i]＝0；
for（j=０;ｊ〈g.ｖeｘnｕｍ; ｊ＋+）
path[i][j］=0；
iｆ（dｉsｔ[i］〈IＮＦ）{
path［i］[v]=1;
pａth［i][i]=１;
}
｝
ｄist[ｖ］＝0;
s[ｖ]=1;
foｒ（i＝0,u＝1; i ｍindis=ＩＮFＩＮ；
for（ｊ＝0；ｊｖexnum；ｊ++）
if（s［ｊ]=＝0）
if（dist［j]〈miｎdis）{
u=ｊ；
ｍindis=disｔ[j］；
｝
s[u］=1;
for（ｊ=0； j＜g。
vexｎｕm；j++）
if（（s[j]＝=0）&＆ｄiｓt[u］+g。
arｃs［u][j］＜ｄiｓt[j］）｛
dist［j］=diｓt［u]+g．ａrcs[u][j]；
foｒ（k＝0；ｋ path[j]［ｋ］=path[ｕ]［k］；
pａth［j]［ｊ］=1;
｝
}
ｐｒｉntf（”\ｎ顶点％ｃ—＞到各顶点的最短路径\n”,g．vexs［ｖ]）;
for（i=0；ivexnum；i＋+）｛
if（i＝=ｖ）co
升级会员 