=========深度优先搜索(DFS)=========
过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort.
深度优先遍历图的方法是,从图中某顶点v出发:
1.从根节点开始
2.放入一个节点(起始时放入的为根节点)
3.如果这个节点是第一次出现,则放入堆栈中
4.判断该节点的子节点是否搜索完成,
a.如果是则将该节点出栈,判断该栈是否为空
a.1 若为空则结束
a.2 若不为空则取栈顶元素,并回到第2步
b.如果没有完成搜索,取未被搜索的根节点,并回到第2步
递归实现
void dfs(int v)//以v开始做深度优先搜索
{
list::iterator it;
visited[v] = true;
cout << v << " ";
for (it = graph[v].begin(); it != graph[v].end(); it++)
if (!visited[*it])
dfs(*it);
}
非递归实现(栈)
void dfs(int v)//以v开始做深度优先搜索
{
list::iterator it;
visited[v] = true;
cout << v << " ";
stackmystack;
mystack.push(v);
while (!mystack.empty())
{
v = mystack.top();
mystack.pop();
if (!visited[v])
{
cout << v << " ";
visited[v] = true;
}
for (it = graph[v].begin(); it != graph[v].end(); it++)
{
if (!visited[*it])
{
mystack.push(*it);
}
}
}
cout << endl;
}