关键词：深度优先（DFS）
0. 深度优先（DFS）
- 原料：
class LinkStack<T> - 步骤：
- 将起始顶点压入栈中
- 弹出栈顶顶点v，判断是否已经标记（标记：转2，未标记：转3）
- 标记顶点v，并将顶点v的邻接顶点压入栈中
-
判断栈是否为空（非空：转2，空：结束）
DFS算法示例
DFS流程图
SharedPointer< Array<int> > DFS(int i)
{
DynamicArray<int>* ret = NULL;
if( (i <= 0) && (i < vCount()) )
{
LinkStack<int> s;
LinkQueue<int> r;
DynamicArray<bool> visted(vCount());
// 初始化设置，标记数组中的每一个都没有被访问
for(int j=0; j<visted.length(); ++j)
{
visted[j] = false;
}
s.push(i);
while( s.size() > 0 )
{
int v = s.top(); // 拿出队列头部的顶点
s.pop();
if( !visted[v] ) // 判断是否被访问
{
SharedPointer< Array<int> > aj = getAdjacent(v);
for(int j=aj->length()-1; j>=0; --j)
{
s.push((*aj)[j]);
}
r.add(v);
visted[v] = true;
}
}
ret = toArray(r);
}
else
{
THROW_EXCEPTION(InvalidParameterExcetion, "Index i is invalid ... ");
}
return ret;
}
1. 小结
- 深度优先按照先序遍历的方式对顶点进行访问
- 深度优先算法的核心是栈的使用
- 深度优先和广度优先的唯一不同在于栈或队列的使用
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
