| 为什么说图的深度遍历类似于树的先序遍历？ | 您所在的位置：网站首页 › 树的后跟遍历类似于二叉树的 › 为什么说图的深度遍历类似于树的先序遍历？ |
|
DFS递归实现与树的先序遍历递归实现的相似处
在考研复习时复习到图的深度遍历时，参考书中有一句话———图的DFS遍历类似于树的先序遍历，书中给的DFS遍历是以递归方式实现的，于是作者贴出了树的先序遍历的递归代码让读者互相比较，确实可以看出一些相似之处，那就是二者算法思想其实都是，先访问根结点（图中是DFS遍历的起始点），然后递归处理它们的“子部分”，图中的“子部分”指的是这个顶点的其余邻接点，树中的这个“子部分”则是结点的左右子树。 DFS非递归遍历与树的先序遍历非递归实现的相似处通过对两种算法的递归实现从而找到其相似之处或许有些困难，那么就让我们比较这两种遍历的非递归实现代码，看看能否使我们更清晰的找出二者的相似之处 以下是DFS遍历的非递归实现代码 void DFSfei(AGraph* p,int v,int visit[maxsize]) { Arcnode *q=NULL;//用来记录某个顶点的邻接点 int stack[maxsize],top=-1,k;//k用来记录栈顶元素 stack[++top]=v; visit[v]=1; visit(v); while(top!=-1) { k=stack[top]; q=p->adjlist[k].first; while(q!=NULL&&q->adjvex==1)//找q的第一个没被访问过的邻接点，若找不到则因q为NULL退出，证明与q相连的边已处理完毕 { q=q->next; } if(q==NULL) { top--; } else { stack[++top]=q; visit(q->adjvex); visit[q->adjvex]=1; } } }以下是树的先序遍历非递归实现代码 void xianxu(BTnode *tree) { if(tree) { BTnode * stack[maxsize],p=NULL; int top=-1; stack[++top]=tree; while(top!=-1) { p=stack[top--]; visit(p);//访问某个节点 if(p->rchild!=NULL) { stack[++top]=p->rchild; } if(p->lchild!=NULL) { stack[++top]=p->lchild; } } } }通过上面的比较可以说很清晰了，二者的算法流程近乎相同，那就是根节点入栈（起始节点入栈）➡️依次出栈一个元素，出栈时并访问，然后检查左右子树（邻接点）是否存在，存在则依次入栈➡️重复第二步直到栈空。 |
| CopyRight 2018-2019 实验室设备网 版权所有 |