厦门大学数据结构与算法（陈海山）期末习题答案解析(5)

5-13 设带权无向图G =(V, E)含有n个顶点e条边。试描述从顶点u出发，构造图G的最小生成树的克鲁斯卡尔(Kruskal)算法。

5-14 在有向图中，路径( )是从v0出发的一条最短路径。

(A) v0→v1→v5 v0→v2→v5→v6

(B) v0→v2→v3

(C) v0→v2→v4 (D)

C

5-15 采用邻接表存储结构，设计一个算法，判别无向图G中指定的两个顶点之间是否存在一条长度为k的简单路径。

?注：简单路径是指顶点序列中不含有重复的顶点。

//采用邻接表存储结构

int EXL(Graph G,int i,int j,int k)//顶点i到j长度为k {

if(i==j&&k==0)

return 1;//找到一条路径，且长度符合要求 else if(k>0) {

visited[i] = 1;//将这个点标志为已走

for(p=G.vexs[i].firstarc;p;p=p->next)//这个点邻接的第一条边 {

l=p->Adjx;

if(!visited[l])

if(EXL(G,l,j,k-1))

return 1;//剩余路径长度减1，直到减到0表示找到长度为k的路径 } } }

5-16 设带权有向图G =(V, E)含有n个顶点e条边，采用邻接矩阵Graph[n][n]表示。试设计算法Dijkstra(int V0，int n)，用于计算从源点V0到其它各顶点的最短路径。

5-17 设软件工程专业开设的主要课程如表所示： 代码 课程名称 先修课程 代码 课程名称 S1 高等数学 无 S7 数据库系统 S2 程序设计基础 无 S8 编译技术

先修课程 S5 S5 S3 离散数学 S1 S9 算法分析 S1, S5 S4 计算机组成原理 S2 S10 软件工程导论 S5 S5 数据结构与算法 S2, S3 S11 计算机网络 S4, S6 S6 操作系统 S4, S5 试根据先修课程要求绘制课程体系拓扑结构图(结点用课程代码表示)。 5-18 描述关键路径基本概念，并给出有向图的关键路径。

关键路径基本概念：从源点到汇点的最长路径 本图的关键路径是：A ?C?D?E?F?N?P