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
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库厦门大学数据结构与算法(陈海山)期末习题答案解析(5)在线全文阅读。
相关推荐：