《数据结构及应用算法教程(修订版) 数据结构_第7章图和广义表习题.ppt》由会员分享,可在线阅读,更多相关《数据结构及应用算法教程(修订版) 数据结构_第7章图和广义表习题.ppt(14页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第7章 图和广义表习题,(1),习题7.1:,(2)邻接矩阵,(5)强连通分量:,1,5,6,2,3,4,(3)邻接表,习题7.1:,(4)逆邻接表,习题7.2:,习题7.3: int visitedMAXSIZE; /指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G, int i, int j) /深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 if(i=j) return 1; /i就是j else visitedi=1; for(p=G.verticesi.firstarc; p; p=p-nextarc) k=p-adjvex;
2、 if(!visitedk /i下游的顶点到j有路径 /for /else /exist_path_DFS,习题7.4:,(1)邻接矩阵,a,d,g,f,b,h,c,e,最小生成树,a,d,g,f,b,h,c,e,习题7.4:,(2)邻接表,习题7.5:,习题7.6:,习题7.7:,关键路径:GHK J E,习题7.8:,表头:( ( ) ) 表尾:( a,(b,c),(),d),(e) 深度:4,习题7.8:,表头:( ( (a),b) ) 表尾:( (),d),(e,f) ) 深度:4,习题7.9:,习题7.10: int GList_Getdeph(GList L) /求广义表深度的递归算法 if(!L-tag) return 0; /原子深度为0 else if(!L) return 1; /空表深度为1 m=GList_Getdeph(L-ptr.hp)+1; n=GList_Getdeph(L-ptr.tp); return mn?m:n;/GList_Getdeph,