作业图参考答案.docx
《作业图参考答案.docx》由会员分享，可在线阅读，更多相关《作业图参考答案.docx（9页珍藏版）》请在冰点文库上搜索。
作业图参考答案
作业4.图
非编程作业参考答案：
1．
已知带权无向图如图所示：
（1）.根据普里姆（Prim）算法，求它的从顶点a出发的最小生成树（写出过程，即添加顶点、边次序）；
（2）.根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树（写出过程，即添加边次序）。
普里姆（Prim）算法：
克鲁斯卡尔（Kruskal）算法：
2.已知带权有向图如图所示：
（1）.画出该图的邻接矩阵存储结构；
（2）.请写出该图的一个拓扑有序序列；
（3）.求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。
图G的一个拓扑序列：
abdfecghafbdecgh
abdfegchafbdegch
从a出发到其它顶点的最短路径及其计算过程：
编程作业：
请编写一个完整的程序，建立有向图的邻接表存储结构，并判断两顶点间是否有路径存在，要求：
（1）主函数功能：
①从键盘读入有向图的顶点数、有向边数，调用函数CreateAdjList（）建立邻接表；②在主函数中输出每个顶点的数据域及其所有邻接点；③从键盘读入两个顶点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
#include
#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;k{
printf（"请输入边的两顶点：
"）;
scanf（"%d,%d",&i,&j）;
s=（ArcNode*）malloc（sizeof（ArcNode））;
s->adjvex=j;
s->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&&q==NULL）
{
G.vertices[i].firstarc=s;
s->nextarc=p;
}
else{
q->nextarc=s;
s->nextarc=p;
}
}
}
//按深度优先判断顶点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->nextarc;//v的下一个邻接点
}
if（flag==0）
pathvexnum--;//从路径上删除V
}
voidPath（ALGraphG,VertexTypevx,VertexTypevy）
{
inti;
for（i=1;i<=Max_Vertex_Num;i++）
visited[i]=0;
for（i=1;i<=G.vexnum;i++）
if（G.vertices[i].data==vx）
break;
DFSPath（G,i,vy）;
if（flag==1）
{
printf（"顶点%c到顶点%c之间存在路径，路经为：
",vx,vy）;
for（i=1;i<=pathvexnum;i++）
printf（"%c\t",G.vertices[visitpath[i]].data）;
printf（"%c\n",vy）;
}
else
printf（"顶点%c到顶点%c之间不存在路径\n",vx,vy）;
}
voidmain（）
{
ALGraphG;
inti;
VertexTypevx,vy;
ArcNode*p;
printf（"请输入顶点和边的数目：
"）;
scanf（"%d,%d",&G.vexnum,&G.arcnum）;
CreateAdjList（G）;
printf（"\n图的邻接表为：
\n"）;
for（i=1;i<=G.vexnum;i++）
{
printf（"%c\t",G.vertices[i].data）;
p=G.vertices[i].firstarc;
while（p）
{
printf（"%d\t",p->adjvex）;
p=p->nextarc;
}
printf（"\n"）;
}
printf（"请输入需判断是否存在路径的两个顶点：
"）;
fflush（stdin）;
scanf（"%c,%c",&vx,&vy）;
Path（G,vx,vy）;
}
升级会员 