试分别写出求DFS和BFS生成树(或生成森林)的算法,要求打印出所有的树边。
答:
(1)求DFS生成树
typedef enum{FALSE,TRUE}Boolean;//FALSE为0,TRUE为1
Boolean visited[MaxVertexNum]; //访问标志向量是全局量
void DFSTraverseTREE(ALGraph *G)
{ //求深度优先生成树(以邻接表表示的图G),而以邻接矩阵表示G时,
//算法完全与此相同,只要将DFSTree(G,i)改为DFSMTree(G,i)即可
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //vi未访问过
DFSTree(G,i); //以vi为源点开始DFS搜索,求DFS生成树的边
}//DFSTraverse
void DFSTree(ALGraph *G,int i){
//以vi为出发点对邻接表表示的图G进行深度优先搜索,打印生成树(生成森林)的边
EdgeNode *p;
visited[i]=TRUE; //标记vi已访问
p=G->adjlist[i].firstedge; //取vi边表的头指针
while(p){//依次搜索vi的邻接点vj,这里j=p->adjvex
if (!visited[p->adjvex])//若vj尚未被访问
{printf("(%c,%c)\n",G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex) ;
// 打印边
DFSTree(g,p->adjvex);//则以Vj为出发点向纵深搜索
}
p=p->next; //找vi的下一邻接点
}
本内容试读结束,登录后可阅读更多
下载后可阅读完整内容,剩余3页未读,立即下载