教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 /体基于抽象数据类型（逻辑结构）的算法*/ void DFSForest(Graph G,CSTree &T) T=NULL; for(v=0;v<G.vexnum;++v)visited[v]=FALSE; for v=0:v<G.vexnum:++v) if(!visited[v]) p=(CSTree)malloc(sizeof(CSNode)); *p={GetVex(G,v),NULL,NULL); if(T=NULL)T=p;第一棵生成树的根(T的根)*/ else q->nextsbling=p;/*其它生成树的根（前一棵的“兄弟”）*/ q=p; *q指示当前生成树的根*/ DFSTree(G,v,p); /体建立以p指向的结点为根结点的生成树/ } void DFSTree(Graph G,int v,CSTree &T) visited[v]=TRUE; first=TRUE; *标识下一个访问的邻接点是否为第一个未访问的邻接点*/ for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)) if(!visited[w]) p=(CSTree)malloc(sizeof(CSNode);/*分配孩子结点*/ *p={GetVex(G,w),NULL,NULL}; if first ) :w是v的第一个未访问的邻接点/ T->firstchild=p;first=FALSE;/*是根的第一个孩子*/ else{ q->nextsbling=p; :是上一邻接点的右兄弟结点*/ q=p; :修改上一孩子结点的指针/ DFSTree(G,w,q); 4、广度优先搜索生成树/森林算法思路 引入队列，除了保存“顶点己访问，但其邻接点未全访问”的顶点编号以外，还须保存该 顶点在生成树中的对应结点的指针。 void BFSForest(Graph G,CSTree &T) T=NULL; for(v=0;v<G.vexnum;++v)visited[v]=FALSE; InitQueue(Q): for(v=0;v<G.vexnum;++v) if(!visited[v]) 体访问某连通分量的起始顶点，起点入队/ visited[v]=TRUE; p=(CSTree malloc(sizeof(CSNode)); *p={GetVex(G,v),NULL,NULL); if(T=NULL)T=p;第一棵生成树的根(T的根)*/ else q->nextsbling=p;/快其它生成树的根（前一棵的“兄弟”）*/ 文档编号 完成时间 完成人张昱 修改时间20026-6 第11页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 11 页 /* 基于抽象数据类型(逻辑结构)的算法 */ void DFSForest(Graph G, CSTree &T) { T = NULL; for ( v=0; v<G.vexnum; ++v ) visited[v] = FALSE; for ( v=0; v<G.vexnum; ++v ) if ( !visited[v] ){ p = ( CSTree ) malloc(sizeof(CSNode)); *p = {GetVex(G, v), NULL, NULL}; if ( T == NULL ) T = p; /* 第一棵生成树的根(T 的根) */ else q->nextsbling = p;/* 其它生成树的根(前一棵的“兄弟”) */ q = p; /* q 指示当前生成树的根 */ DFSTree(G, v, p); /* 建立以 p 指向的结点为根结点的生成树 */ } } void DFSTree(Graph G, int v, CSTree & T ) { visited[v] = TRUE; first = TRUE; /* 标识下一个访问的邻接点是否为第一个未访问的邻接点 */ for ( w = FirstAdjVex( G, v); w; w = NextAdjVex(G, v, w) ) if ( !visited[w] ){ p = ( CSTree ) malloc(sizeof(CSNode)); /* 分配孩子结点 */ *p = {GetVex(G, w), NULL, NULL}; if ( first ){ /* w 是 v 的第一个未访问的邻接点 */ T->firstchild = p; first = FALSE; /*是根的第一个孩子 */ } else { q->nextsbling = p; /* 是上一邻接点的右兄弟结点 */ } q = p; /* 修改上一孩子结点的指针 */ DFSTree(G, w, q); } } 4、广度优先搜索生成树/森林算法思路 引入队列，除了保存“顶点已访问，但其邻接点未全访问”的顶点编号以外，还须保存该 顶点在生成树中的对应结点的指针。 void BFSForest(Graph G, CSTree &T) { T = NULL; for ( v=0; v<G.vexnum; ++v) visited[v] = FALSE; InitQueue(Q); for ( v=0; v<G.vexnum; ++v) if ( !visited[v] ){ /* 访问某连通分量的起始顶点，起点入队 */ visited[v] = TRUE; p = ( CSTree ) malloc(sizeof(CSNode)); *p = {GetVex(G, v), NULL, NULL}; if ( T==NULL ) T = p; /* 第一棵生成树的根(T 的根) */ else q->nextsbling = p; /* 其它生成树的根(前一棵的“兄弟”) */