深度优先遍历
2015-12-29 14:49:30 8 举报
深度优先遍历(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。
作者其他创作
大纲/内容
否
是
返回OK
q=q-next
q!=NULL?
找出一个没有被访问的结点target,即visited[target]=0
p指向出栈的一个结点,并找到它在结点数组中的位置kq = p-next
开始
target结点入栈新建结点指针p、q和序号k定义栈的长度为len=0
q==NULL?
返回OVERFLOW
如果结点k还没有被访问?
栈非空,即len0?
结束
结点k入栈
如果k结点还没有被访问,即visited[k]=0?
当前结点的所有邻接结点已经访问,出栈
创建结点指针数组(栈)son[255]
图G是存在,即G.nides!=NULL?
查找结点q-v的位置k
创建visited数组并初始化为0,表示结点是否被访问
还有没有被访问的结点?
0 条评论
下一页