我保证没有抄袭他人的作业!.pdfVIP

我保证没有抄袭他人的作业！ 第一题：对无向图，其DFS 周游（深度优先周游）的过程PreVisit(G, V)语句所 涉及的结点按照相应的边访问顺序生成一个森林。请改写周游算法，把该生成 树的结构和相应结点信息存储在树结点中返回。 题目中用的是模板，我想那应该是针对与TreeNode(树节点) 中的节点值，而图中只有对图顶 点标号的存储，是整型的，与templateT无法对应上去，因此我在图类中加了一个公有成 员T * Value 数组，用Value[i]存储标号i 对应的值，把这个值赋给TreeNode(树节点) 的值 【思路】： 在深度周游图时，对一个顶点访问与它相关联的顶点时，第一个点是这个顶点的最左子，其 它点是这个最左子的右兄弟。于是在访问某个点完毕后，检察它是否第一个访问的点，判断 这个点是某个顶点的最左子还是之前访问点的右兄弟 检查是否是第一个点的方法：纪录前一个被访问的点，初始是把前一个被访问点设为NULL, 如果访问完一个点后，它的前一个访问点的指针是NULL ，那这个点就是第一个访问点，一 个顶点的最左子，若不是NULL 则这个顶点是它前一个访问点的右兄弟。 【代码】： //深度递归函数 template class T void DFS( Graph G, int v, TreeNodeT * point ) { G.Mark[v] = VISITED;//标记点v 为访问过的点 point-setValue( G.Value[v] );//对point 赋值(我在图类中加了一个公有成员T * Value 数 组， //用Value[i]存储标号i 对应的 //值，把这个值赋给TreeNode(树节点) 的值 //对point 的左子右兄弟初始化 point-setChild( NULL ); point-setSibling( NULL ); TreeNodeT * tempPoint = NULL;//tempPoint 纪录当前与point 相关联的点 TreeNodeT * tempPrePoint = NULL;//tempPrePoint 纪录在点 tempPoint 的前一个与 point 相关联的点 for( Edge e = G.FirstEdge(v); IsEdge(e); e = G.NextEdge(e) ) { if( G.Mark[G.ToVertices(e)] == UNVISITED )//寻找与v 相关联的点，这些点是point 的子 { temppoint = new TreeNodeT; DFS( G, G.ToVertices(e), tempPoint ); //如果tempPrePoint 为空，说明tempPoint 的是第 //一个与point 的相关联的点，即是point 的最左子 if( tempPrePoint == NULL ) { point-setChild( tempPoint ); tempPrePoint = tempPoint; } //否则tempPoint 是tempPrePoint 的右兄弟 else { tempPrePoint-setSibling( tempPoint ); tempPrePoint = tempPoint; } } } } //建树函数 template class T TreeNodeT * graph_DFS(Graph G) { TreeNodeT * root = NULL; TreeNodeT * p