图的深度优先搜索的非递归版本算法的两种实现
Two unrecursive implementation of the deep first graph search algorithm
EmilMatthew (EmilMatthew@126.com)
摘要:
图的深度优先算法的递归版本相当简洁好懂。将递归版本的算法改写成非递归版本的难度并不大，关键是要处理好如何正确的在搜索的过程中存储搜索树中的子结点，并正确的进行访问.一种实现采用了两个栈，而另一种则使用一个结点类型为队列的栈..
Abstract：
The recursive version of the deep first graph search algorithm is very concise to be understood. It is not a difficult job to change the recursive version into unrecursive version, the key technique in the algorithm transformation is to make and visit the child node during the search processing ,which should be handled in a correctly and precise way. One implementation use two stacks while the other version use a stack which has the node of queue type.
关键词:图的搜索,非递归,深度优先
1图的深度优先搜索算法的回顾:
图的深度优先搜索用递归实相当的简洁好懂:
void dftR(PGraphMatrix inGraph)
{
PVexType v;
assertF(inGraph!=NULL,"in dftR, pass in inGraph is null\n");
printf("\n===start of dft recursive version===\n");
for(v=firstVertex(inGraph);v!=NULL;v=nextVertex(inGraph,v))
if(v->marked==0)
dfsR(inGraph,v);
printf("\n===end of dft recursive version===\n");
}
void dfsR(PGraphMatrix inGraph,PVexType inV)
{
PVexType v1;
assertF(inGraph!=NULL,"in dfsR,inGraph is null\n");
assertF(inV!=NULL,"in dfsR,inV is null\n");
inV->marked=1;
visit(inV);
for(v1=firstAdjacent(inGraph,inV);v1!=NULL;v1=nextAdjacent(inGraph,inV,v1))
if(v1->marked==0)
dfsR(inGraph,v1);
}
2非递归版本
2.1.1非递归版本1---借助结点类型为队列的栈实现
首先,将从某个顶点开始进行的深度优先搜索树画出，可以看到，对从某个结点开始的深度优先遍历，实际上就是基于这个深度优先搜索树一个遍历，不过，树中的的很多结点当marked值为1时将不必再访问.
举例如下:
根据深度优先搜索规则，图1对应的两棵深度优先搜索树如右所示.
其中,用土黄色”\\”标注的树枝表示在第一次试探的过程中便不需要访问的边,而用蓝色”\\”标注的树枝则表示在回访过程中不再需要访问的结点.
联系树的前序遍历的非递归实现：
可知，其中无非是分成“探左”和“访右”两大块访右需借助栈中弹出的结点进行.
在图的深度优先搜索中，同样可分成“深度探索”和“回访上层未访结点”两块:
1图的深度探索这样一个过程和树的“探左”完全一致,只要对已访问过的结点作一个判定即可.
2而图的回访上层未访结点和树的前序遍历中的“访右”也是一致的.但是，对于树而言，是提供rightSibling这样的操作的，因而访右相当好实现。在这里，若要实现相应的功能，我考虑是将每一个当前结点的下层结点中，如果有m个未访问结点,则最左的一个需要访问，而将剩余的m-1个结点按从左到右的顺序推入一个队列中。并将这个队列压入一个堆栈中。
这样，当当前的结点的邻接点均已访问或无邻接点需要回访时，则从栈顶的队列结点中弹出队列元素，将队列中的结点元素依次出队,若已访问，则继续出队(当当前队列结点已空时，则继续出栈，弹出下一个栈顶的队列)，直至遇到有未访问结点(访问并置当前点为该点)或直到栈为空（则当前的深度优先搜索树停止搜索）
将算法通过精简过的C源程序的方式描述如下:
/*dfsUR:功能从一个树的某个结点inV发，以深度优先的原则访问所有与它相邻的结点*/
void dfsUR(PGraphMatrix inGraph,PVexType inV)
{
PSingleRearSeqQueue tmpQ;//定义临时队列，用以接受栈顶队列及压栈时使用
PSeqStack testStack;//存放当前层中的m-1个未访问结点构成队列的堆栈.
/*
一些变量声明,初始化动作
*/
/*访问当前结点*/
inV->marked=1;
visit(inV);
do
{
flag2=0;//flag2是一个重要的标志变量，用以、说明当前结点的所有未访问结点的个数,两个以上的用2代表*/
/*
flag2:
0:current node has no adjacent which has not been visited.
1:current node has only one adjacent node which has not been visited.
2:current node has more than one adjacent node which have not been visited.
*/
v1=firstAdjacent(inGraph,inV);
while(v1!=NULL) //访问当前结点的所有邻接点
{
if(v1->marked==0)/*find one adjacent node which has not been visited.*/
{
if(flag2==0)/*visit the first unvisited adjacent node*/
{
/*访问最左结点*/
visit(v1);
v1->marked=1;
flag2=1;
/*记录最左儿子*/
lChildV=v1; /*save the current node's first unvisited(has been visited at this time)adjacent node*/
}
else if(flag2==1)/*current node has second unvisited node*/
{
新建一个队列，申请空间，并加入第一个结点
flag2=2;
}
else if(flag2==2)/*current node has more unvisited node*/
{
enQueue(tmpQ,v1);
}
}
v1=nextAdjacent(inGraph,inV,v1);
}
if(flag2==2)/*push adjacent nodes which are not visited.*/
{
//将存有当前结点的m-1个未访问邻接点的队列压栈
seqPush(testStack,tmpQ);
inV=lChildV;
}
else if(flag2==1)/*only has one adjacent which has been visited.*/
{
//只有一个最左儿子，则置当前点为最左儿子
inV=lChildV;
}
else if(flag2==0)/*has no adjacent nodes or all adjacent nodes has been visited*/
{
/*当当前的结点的邻接点均已访问或无邻接点需要回访时，则从栈顶的队列结点中弹出队列元素，将队列中的结点元素依次出队,若已访问，则继续出队(当当前队列结点已空时，则继续出栈，弹出下一个栈顶的队列)，直至遇到有未访问结点(访问并置当前点为该点)或直到栈为空*/
flag=0;
while(!isNullSeqStack(testStack)&&!flag)
{
v1=frontQueueInSt(testStack);
deQueueInSt(testStack);
if(v1->marked==0)
{
visit(v1);
v1->marked=1;
inV=v1;
flag=1;
}
}
}
}while(!isNullSeqStack(testStack));/*the algorithm ends when the stack is null*/
}
所以，这里应使用的数据结构的构成方式应该采用下面这种形式:
1)队列的实现中，每个队列结点均为图中的结点指针类型.
定义一个以队列尾部下标加队列长度的环形队列如下:
struct SingleRearSeqQueue;
typedef PVexType QElemType;
typedef struct SingleRearSeqQueue* PSingleRearSeqQueue;
struct SingleRearSeqQueue
{
int rear;
int quelen;
QElemType dataPool[MAXNUM];
};
其余基本操作不再赘述.
2)堆栈的实现中，每个堆栈中的结点元素均为一个指向队列的指针,定义如下:
#define SEQ_STACK_LEN 1000
#define StackElemType PSingleRearSeqQueue
struct SeqStack;
typedef struct SeqStack* PSeqStack;
struct SeqStack
{
StackElemType dataArea[SEQ_STACK_LEN];
int slot;
};
为了提供更好的封装性，对这个堆栈实现两种特殊的操作
2.1) deQueueInSt操作用于将栈顶结点的队列中的队首元素弹出.
void deQueueInSt(PSeqStack inStack)
{
if(isEmptyQueue(seqTop(inStack))||isNullSeqStack(inStack))
{
printf("in deQueueInSt,under flow!\n");
return;
}
deQueue(seqTop(inStack));
if(isEmptyQueue(seqTop(inStack)))
inStack->slot--;
}
2.2) frontQueueInSt操作用以返回栈顶结点的队列中的队首元素.
QElemType frontQueueInSt(PSeqStack inStack)
{
if(isEmptyQueue(seqTop(inStack))||isNullSeqStack(inStack))
{
printf("in frontQueueInSt,under flow!\n");
return '\r';
}
return getHeadData(seqTop(inStack));
}
3)主要算法的实现:
/*外层的周游层和递归版一致*/
void dftUR(PGraphMatrix inGraph)
{
PVexType v;
assertF(inGraph!=NULL,"in dftR, pass in inGraph is null\n");
printf("\n===start of dft recursive version===\n");
for(v=firstVertex(inGraph);v!=NULL;v=nextVertex(inGraph,v))
if(v->marked==0)
dfsUR(inGraph,v);
printf("\n===end of dft recursive version===\n");
}
void dfsUR(PGraphMatrix inGraph,PVexType inV)
{
PSingleRearSeqQueue tmpQ;
PSeqStack testStack;
PVexType v1,lChildV;
int flag,flag2;
int i;
assertF(inGraph!=NULL,"in dfsR,inGraph is null\n");
assertF(inV!=NULL,"in dfsR,inV is null\n");
testStack=(PSeqStack)malloc(sizeof(struct SeqStack));
assertF(testStack!=NULL,"in main,testStack is null\n");
testStack=createNullSeqStack();
for(i=0;i<inGraph->n;i++)
testStack->dataArea[i]=(PSingleRearSeqQueue)malloc(sizeof(struct SingleRearSeqQueue));
inV->marked=1;
visit(inV);
do
{
flag2=0;
/*
flag2:
0:current node has no adjacent which has not been visited.
1:current node has only one adjacent node which has not been visited.
2:current node has more than one adjacent node which have not been visited.
*/
v1=firstAdjacent(inGraph,inV);
while(v1!=NULL)
{
if(v1->marked==0)/*find one adjacent node which has not been visited.*/
{ if(flag2==0)/*visit the first unvisited adjacent node*/
{
visit(v1);
v1->marked=1;
flag2=1;
lChildV=v1;
/*save the current node's first unvisited(has been visited at this time)adjacent node*/
}
else if(flag2==1)/*current node has second unvisited node*/
{
tmpQ=(PSingleRearSeqQueue)malloc(sizeof(struct SingleRearSeqQueue));
assertF(tmpQ!=NULL,"tmpQ is null\n");
tmpQ=createNullSingleRearSeqQueue();
/*mem apply*/
for(i=0;i<inGraph->n;i++)
tmpQ->dataPool[i]=(PVexType)malloc(sizeof(VexType));
enQueue(tmpQ,v1);
flag2=2;
}
else if(flag2==2)/*current node has more unvisited node*/
{
enQueue(tmpQ,v1);
}
}
v1=nextAdjacent(inGraph,inV,v1);
}
if(flag2==2)/*push adjacent nodes which are not visited.*/
{
seqPush(testStack,tmpQ);
inV=lChildV;
}
else if(flag2==1)/*only has one adjacent which has been visited.*/
{
inV=lChildV;
}
else if(flag2==0)/*has no adjacent nodes or all adjacent nodes has been visited*/
{
flag=0;
while(!isNullSeqStack(testStack)&&!flag)
{
v1=frontQueueInSt(testStack);
deQueueInSt(testStack);
if(v1->marked==0)
{
visit(v1);
v1->marked=1;
inV=v1;
flag=1;
}
}
}
}while(!isNullSeqStack(testStack));/*the algorithm ends when the stack is null*/
}
测试结果:
1
课本p244图8.7
graphMode=s
8,8;
a,b,c,d,e,f,g,h;
0,1,1,0,0,0,0,0;
0,0,0,1,1,0,0,0;
0,0,0,0,0,1,1,0;
0,0,0,0,0,0,0,1;
0,0,0,0,0,0,0,1;
0,0,0,0,0,0,1,0;
0,0,0,0,0,0,0,0;
0,0,0,0,0,0,0,0;
dfsOrder:
a,b,d,h,e,c,f,g
2图1
graphMode=u
6,6;
0,1,2,3,4,5;
0,1,1,0,0,0;
0,0,1,0,0,0;
0,0,0,1,0,0;
1,1,0,0,0,0;
0,0,1,0,0,1;
0,0,0,1,0,0;
dfsOrder:
0,1,2,3,4,5
3图2
graphMode=s
7,7;
0,1,2,3,4,5,6;
0,1,0,1,0,0,0;
0,0,1,0,0,0,0;
0,0,0,1,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,1,1;
0,0,0,0,0,0,1;
0,0,0,0,0,0,0;
dfsOrder:
0,1,2,3,4,5,6
从测试的结果来看，验证了这个算法的正确性.
2.1.2非递归算法1的复杂度简要分析:
设图的顶点个数为n个.
a)在最好的情况下，如图为一条连通的路径的时候（无顶点联接三条或以上的边）,每个顶点访问一次，复杂度为n
b)在最坏的情况下,如图为完全图的时候,在搜索树中层为i的结点将会有n-2-i个结点加入队列，继而压入堆栈.最多在栈中结点数为(n-2)*(n-1)/2个,每个结点入队列，出队列一次，外加n-1次队列入栈和压栈，以及n次visit操作.整体复杂度将达到n^2级别.与递归版本的复杂度类似，但由于递归版本有保护访问函数现场及恢复现场等工作，所以非递归版本在实际使用时的效率是会较递归版本有一定提搞的.
2.2.2非递归版本2---借助两个栈加以实现
这个算法在整体的思考上要较上面的算法简洁,效率亦无多少损失.从思想上而言，和上面的非递归版本1是一致的。
将这个算法抽象层描述如下:
/*设当前图(或图的某个连通分枝)的起始访问点为p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statckSec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackMain.isEmpty())
{
p=stackMain.pop();
}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//访问未访问结点.
{
visit(p);
p.marked=true;
}
}while(!stackMain.isEmpty())
参考资料:
[1]张乃孝,算法与数据结构----C语言描述,高等教育出版社,2002.
完成日:05/12/12
本文最佳浏览定位:
[url=http://www.emilmatthew.zk.cn/EmilPapers/06_1dfsUn/dfsUnRec.htm]http://www.emilmatthew.zk.cn/EmilPapers/06_1dfsUn/dfsUnRec.htm
算法测试程序下载:
