作业图参考答案Word文档格式.docx
《作业图参考答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《作业图参考答案Word文档格式.docx（9页珍藏版）》请在冰点文库上搜索。
②在主函数中输出每个顶点的数据域及其所有邻接点；
③从键盘读入两个顶点vs、vt（
）的数据域，调用函数Path（）判断其间是否存在路径；
（2）CreateAdjList（）：
建立有向图邻接表。
功能：
从键盘接收各顶点数据域及各条有向边所依附的顶点（如：
“2,3”代表该边依附的两个顶点在表头数组中的下标为2和3），要求单链表中结点按数据域升序排序；
（3）Path（）:
判断两顶点间是否存在路径，如果存在，将打印该路径（若存在多条路径，打印其中一条即可）。
例：
输入：
请输入顶点和边的数目：
8，9//（在main（）函数中输入）
请输入各顶点数据域：
abcdefgh
//（在CreateAdjList（）中输入）
请输入各条边：
1,2
1,3
2,4
3,6
3,7
4,8
5,2
5,8
6,7
输出：
图的邻接表为：
a23//（在main（）函数中输出）
b4
c67
d8
e28
f7
g
h
输入：
请输入要查找是否存在路径的顶点：
a,h
顶点a和d之间存在路径，路经为：
abdh
a,e
顶点a和e之间不存在路径
参考答案：
#include<
stdio.h>
malloc.h>
#defineMax_Vertex_Num10
typedefcharVertexType;
intvisited[Max_Vertex_Num];
intvisitpath[Max_Vertex_Num];
intpathvexnum;
intflag;
//单链表结点（弧结点）
typedefstructArcnode
{intadjvex;
//该弧所指向顶点（在表头数组中）的位置
structArcnode*nextarc;
//指向依附该顶点下一条边或弧
}ArcNode;
//头结点
typedefstructVnode
{VertexTypedata;
//顶点信息
Arcnode*firstarc;
//指向第一条依附该顶点的弧
}VNode,AdjList[Max_Vertex_Num];
//图的定义
typedefstruct
{AdjListvertices;
//表头数组
intvexnum,arcnum;
//图中顶点及弧的数目
}ALGraph;
//建立邻接表
voidCreateAdjList（ALGraph&
G）
{
intk,i,j;
ArcNode*p,*q,*s;
for（k=1;
k<
=G.vexnum;
k++）
{
printf（"
inputdata:
"
）;
fflush（stdin）;
scanf（"
%c"
&
G.vertices[k].data）;
G.vertices[k].firstarc=NULL;
}
for（k=0;
G.arcnum;
请输入边的两顶点：
%d,%d"
i,&
j）;
s=（ArcNode*）malloc（sizeof（ArcNode））;
s->
adjvex=j;
nextarc=NULL;
q=NULL;
p=G.vertices[i].firstarc;
while（（p!
=NULL）&
&
（j>
p->
adjvex））
{
q=p;
p=p->
nextarc;
}
if（p==NULL&
q==NULL）
G.vertices[i].firstarc=s;
elseif（p==NULL&
q!
=NULL）
q->
nextarc=s;
elseif（p!
=NULL&
s->
nextarc=p;
else{
}
//按深度优先判断顶点vx和vy间是否存在路径
voidDFSPath（ALGraphG,intv,VertexTypevy）
{ArcNode*w;
inti;
visitpath[++pathvexnum]=v;
visited[v]=1;
w=G.vertices[v].firstarc;
//顶点v的第一个邻接点
while（w!
=NULL）//是否存在
{
i=w->
adjvex;
//邻接点下标
if（G.vertices[i].data==vy）
flag=1;
return;
elseif（flag==0&
visited[i]==0）
DFSPath（G,i,vy）;
w=w->
//v的下一个邻接点
if（flag==0）
pathvexnum--;
//从路径上删除V
voidPath（ALGraphG,VertexTypevx,VertexTypevy）
for（i=1;
i<
=Max_Vertex_Num;
i++）
visited[i]=0;
if（G.vertices[i].data==vx）
break;
DFSPath（G,i,vy）;
if（flag==1）
顶点%c到顶点%c之间存在路径，路经为：
vx,vy）;
for（i=1;
=pathvexnum;
printf（"
%c\t"
G.vertices[visitpath[i]].data）;
%c\n"
vy）;
else
顶点%c到顶点%c之间不存在路径\n"
voidmain（）
ALGraphG;
VertexTypevx,vy;
ArcNode*p;
printf（"
scanf（"
G.vexnum,&
G.arcnum）;
CreateAdjList（G）;
\n图的邻接表为：
\n"
G.vertices[i].data）;
while（p）
%d\t"
p->
adjvex）;
p=p->
请输入需判断是否存在路径的两个顶点：
fflush（stdin）;
%c,%c"
vx,&
vy）;
Path（G,vx,vy）;
升级会员 