数据结构与算法习题及答案

精心整理

②求每个活动的最早开始时间和最迟开始时间; ③确定哪些活动是关键活动

图6.31AOE-网 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个

活动的最早可能开始时间e和最迟允许开始时间l,根据l-e=0?来确定关键活动,从而确定关键路径。 Ve Vl <1,2> e l 7 l-e 7 0 11<1,3> 0 5 0 5 0 0 17 8 <3,2> 19 29 0 2 <2,4> 19 17 1<2,5> 15 27 8 <3,5> 19 38 0 <4,6> 28 3<5,6> 30 19 15 37 38 43 1? 0 2? 19 3? 15 4? 29 5? 38 6? 43 此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6> 3.算法设计题 (1)分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ①增添一个新顶点v,InsertVex(G,v); ②删除顶点v及其相关的边,DeleteVex(G,v); ③增加一条边,InsertArc(G,v,w); ④删除一条边,DeleteArc(G,v,w)。 //本题中的图G均为有向无权图,其余情况容易由此写出 StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE; G.vexs[++G.vexnum]=v; returnOK; }//Insert_Vex StatusInsert_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; if(i==j)returnERROR; if(!G.arcs[j].adj) {

G.arcs[j].adj=1; G.arcnum++; }

returnOK; }//Insert_Arc

StatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v {

n=G.vexnum; 精心整理

精心整理

if((m=LocateVex(G,v))<0)returnERROR;

G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点 for(i=0;i

G.arcs[m]=G.arcs[n];

G.arcs[m]=G.arcs[n];//将边的关系随之交换 }

G.arcs[m][m].adj=0; G.vexnum--; returnOK; }//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加. StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; if(G.arcs[j].adj) {

G.arcs[j].adj=0; G.arcnum--; }

returnOK; }//Delete_Arc //为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出. StatusInsert_Arc(ALGraph&G,charv,charw)//在邻接表表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL; else {

if(q->adjvex==j)returnERROR;//边已经存在 q->nextarc=p; }

G.arcnum++; returnOK; }//Insert_Arc

(2)一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。

数据结构考研指导232页7.3.7

(3)设计一个算法,求图G中距离顶点v的最短路径长度最大的一个顶点,设v可达其余各个顶点。 数据结构考研指导232页7.3.8 精心整理

精心整理

(4)试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

解1:

intvisited[MAXSIZE];//指示顶点是否在当前路径上

intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 {

if(i==j)return1;//i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 解2:(以上算法似乎有问题:如果不存在路径,则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。) intvisited[MAXSIZE];//指示顶点是否在当前路径上 intlevel=1;//递归进行的层数 intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 {

if(i==j)return1;//i就是j else {

visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc,level--) {level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径 }//for }//else if(level==1)return0; }//exist_path_DFS

(5)采用邻接表存储结构,编写一个算法,判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。

(注1:一条路径为简单路径指的是其顶点序列中不含有重现的顶点。 注2:此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。) intvisited[MAXSIZE];

intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 精心整理

精心整理

{ {

if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求 elseif(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一 }//for visited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中 }//else return0;//没找到 }//exist_path_len 精心整理

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4