图算法二之深度优先搜索
目录
图算法二之深度优先搜索
前面我们已经介绍了广度优先算法，我们这一张介绍深度优先，深度优先不同于广度优先在于，广度优先算法是一层一层的搜索，即搜索一个节点，然后搜索它所有的字节点，而深度优先搜索则是，搜索一个节点后，先搜索其一个节点，然后深度搜索，搜索完了以后，再搜索这个节点的其他兄弟节点。
相比于广度优先算法，我们将bfs中的队列改为栈，采用同样的数据结构，实现代码如下
void dfs(graph *g,int start)
{
edgenode *p;
stack<int> q;
q.push(start);
discovered[start]=true;
while(!q.empty())
{
int x=q.top();
q.pop();
p=g->nodes[x];
if(!processed[x])
{
cout<<x<<" ";
processed[x]=true;
}
while(p)
{
int y=p->y;
if(!processed[y]&&!discovered[y])
{
parent[y]=x;
q.push(y);
discovered[y]=true;
}
p=p->next;
}
}
}