作业4图 参考答案.doc

数据结构作业4图 参考答案
作业4. 图
l 非编程作业参考答案：
4
1
3
7
5
6
2
5
a
b
c
e
d
1． 已知带权无向图如图所示：
(1). 根据普里姆（Prim）算法，求它的从顶点a出发的最小生成树(写出过程，即添加顶点、边次序)；
(2). 根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树(写出过程，即添加边次序)。
普里姆（Prim）算法：

克鲁斯卡尔（Kruskal）算法：
2
aa
f
b
d
g
c
h
e
A
6
9
7
8
3
2
5
1
30
24
21

2. 已知带权有向图如图所示：
(1). 画出该图的邻接矩阵存储结构；
(2). 请写出该图的一个拓扑有序序列；
(3). 求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。

图G的一个拓扑序列：
abdfecgh afbdecgh
abdfegch afbdegch

从a出发到其它顶点的最短路径及其计算过程：

l 编程作业：
请编写一个完整的程序，建立有向图的邻接表存储结构，并判断两顶点间是否有路径存在，要求：
(1) 主函数功能：①从键盘读入有向图的顶点数、有向边数，调用函数CreateAdjList()建立邻接表；②在主函数中输出每个顶点的数据域及其所有邻接点；③从键盘读入两个顶点vs、vt（）的数据域，调用函数Path()判断其间是否存在路径；
(2) CreateAdjList()：建立有向图邻接表。功能：从键盘接收各顶点数据域及各条有向边所依附的顶点（如：“2,3”代表该边依附的两个顶点在表头数组中的下标为2和3），要求单链表中结点按数据域升序排序；
(3) Path(): 判断两顶点间是否存在路径，如果存在，将打印该路径（若存在多条路径，打印其中一条即可）。

例：输入：请输入顶点和边的数目：8，9 //(在main（）函数中输入)
请输入各顶点数据域：a b c d e f g h
//(在CreateAdjList()中输入)
请输入各条边：1,2
1,3
2,4
3,6
3,7
4,8
5,2
5,8
6,7
输出：图的邻接表为：a 2 3 //（在main（）函数中输出）
b 4
c 6 7
d 8
e 2 8
f 7
g
h
输入： 请输入要查找是否存在路径的顶点：a,h
输出： 顶点a和d之间存在路径，路经为：a b d h
输入： 请输入要查找是否存在路径的顶点：a,e
输出： 顶点a和e之间不存在路径
参考答案：
#include<stdio.h>
#include<malloc.h>
#define Max_Vertex_Num 10

typedef char VertexType;
int visited[Max_Vertex_Num];
int visitpath[Max_Vertex_Num];
int pathvexnum;
int flag;

//单链表结点(弧结点)
typedef struct Arcnode
{ int adjvex; //该弧所指向顶点（在表头数组中）的位置
struct Arcnode *nextarc; //指向依附该顶点下一条边或弧
} ArcNode;
//头结点
typedef struct Vnode
{ VertexType data; //顶点信息
Arcnode *firstarc; //指向第一条依附该顶点的弧
} VNode, AdjList[Max_Vertex_Num];
//图的定义
typedef struct
{ AdjList vertices; // 表头数组
int vexnum, arcnum; // 图中顶点及弧的数目
} ALGraph;

//建立邻接表
void CreateAdjList (ALGraph &G)
{
int k,i,j;
ArcNode *p,*q,*s;
for(k=1;k<=G.vexnum;k++)
{
printf("input data:");
fflush(stdin);
scanf("%c",&G.vertices[k].data);
G.vertices[k].firstarc=NULL;
}
for(k=0;k<G.arcnum;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;
else if(p==NULL&&q!=NULL)
q->nextarc=s;
else if(p!=NULL&&q==NULL)
{
G.vertices[i].firstarc=s;
s->nextarc=p;
}
else{
q->nextarc=s;
s->nextarc=p;
}
}
}

//按深度优先判断顶点vx和vy间是否存在路径
void DFSPath(ALGraph G, int v, VertexType vy)
{ ArcNode *w;
int i;

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;
}
else if(flag==0&&visited[i]==0)
DFSPath(G,i,vy);
w=w->nextarc; //v的下一个邻接点
}
if(flag==0)
pathvexnum--;//从路径上删除V
}

void Path(ALGraph G, VertexType vx, VertexType vy)
{
int i;

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);
}

void main()
{
ALGraph G;
int i;
VertexType vx,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);
}