首页 > 代码库 > 图的深度优先搜索（DFS）简介与实现（递归与非递归方法）

图的深度优先搜索（DFS）简介与实现（递归与非递归方法）

2024-07-03 11:46:26   221人阅读

        上一篇刚刚学习了C++图的实现，今天对深度优先搜索（DFS）进行了一定学习，并作出一定实现。在本文中图的实现，以及相应的函数调用（如获得第一个邻接顶点、获得下一个邻接顶点等）均是基于上文中的实现，故如果想参考测试代码，还需导入上文中相应的类定义。关于C++图的实现可参考此处，这里实现了对图的邻接表以及邻接矩阵两种实现，而本文的深度优先搜索对于上面两种实现均是可行的。

        当然，对于图的深度优先搜索的相关定义，本文也不再过多赘述，维基的解释应该就足够，下面将探讨其实现。

        1、深度优先搜索的非递归实现：

         要实现非递归的深度优先搜索，本文用到栈s来存储，用一个数组visited（初始所有元素为false，代表未访问）来做访问的标记。基本思想是：从给定的搜索的第一个顶点loc开始，将其压入堆栈，并标记visited[loc]为true表示已访问；之后循环进行如下操作，只要栈不为空，取出最上方元素，将其记录（本文直接打印，若有需要，可将其存入数组or Vector），然后去打所有的邻接顶点，只要还未访问（visited相应值为false），就将其压入栈，并标记为已访问。当栈中元素为0时，算法结束时，而所有访问过的点，均被标记过，并被压入栈中过，只要图是连通的，那么就做到所有点都被输出或记录。

        注意：刚才有提过，以上针对于连通的图，而对于图虫存在不同的连通分量的情况，可以在一次while循环之后，检查visited判断是否所有元素都被访问过，若存在未被访问的点，则在选取一个点，重复以上操作即可，本文中并不对此加以实现。

        下面将在说明递归调用之后统一贴出示例代码。

        2、深度优先搜索的递归实现：

        递归实现的思路则好理解的多，基于回溯的思想。对于所给的点，得到一个邻接顶点后，继续对该顶点深度搜索，指导找不到下一个点，在退回一步，找下一个邻接顶点，在进行搜索。

       以下贴出代码，结合理解。

//FileName: DFS 
//图的深度优先遍历 ---递归与非递归实现
#include"Graphlnk.h"
#include"Graphmtx.h"
#include<iostream>
#include<stack>
using namespace std;

template<class T ,class E>
void DFS(Graphmtx<T,E> &G, const T &v,int judge)//非递归算法，参数int i用以区分递归与非递归
{
    cout<<"-------非递归算法被调用-------"<<endl;
    stack<int> s;
    int i,loc,out,next;
    int n = G.NumberOfVertices(); //顶点数
    bool *visited = new bool[n];
    for(i = 0;i<n;i++)
        visited[i] = false;
    loc = G.getVertexPos(v);
    s.push(loc);
    visited[loc]=true; //标记
    while(!s.empty())
    {
        out = s.top();
        s.pop();
        cout<<G.getValue(out)<<" ";
        next = G.getFirstNeighbor(out); //将所有未被标记的邻接点压入堆栈
        while(next!=-1)
        {
            if(visited[next]==false)
            {
                s.push(next);
                visited[next] = true;
            }
            
            next = G.getNextNeighbor(out,next);
        }
    }
    delete []visited;
}
template<class T ,class E>
void DFS(Graphmtx<T,E> &G, const T &v)
//void DFS(Graphlnk<T,E> &G, const T &v)
{
    cout<<"-------递归算法被调用-------"<<endl;
    int i, loc, n =G.NumberOfVertices();
    bool *visited = new bool[n];
    for (i = 0;i<n;i++)
        visited[i] = false;
    loc = G.getVertexPos(v);
    DFS(G , loc , visited);
    delete []visited;
}

template<class T ,class E>
void DFS(Graphmtx<T,E> &G, int v, bool  *visited) //递归实现算法
//void DFS(Graphlnk<T,E> &G, int v, bool  *visited)
{
    cout<< G.getValue(v)<< " ";
    visited[v] = true;
    int w = G.getFirstNeighbor(v);
    while(w!=-1)
    {
        if(visited[w]==false)
        {    
            DFS(G, w, visited);
        }
        w = G.getNextNeighbor(v,w);        
    }
}


void test_DFS()
{
    char first;
    Graphmtx<char,int> g(30);
    //Graphlnk<char ,int> g(30);
    g.inputGraph();
    g.outputGraph();
    cout<<"输入深度优先搜索的第一个点："<<endl;
    cin>>first;
    //DFS(g,first);//递归调用
    DFS(g,first,1);//非递归调用
}

注：以上代码最后部分test_DFS()是简单的测试程序，将其在main()直接调用即可看到效果。


联系
我们