最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 数据结构基础(21) –DFS与BFS


    DFS

        从图中某个顶点V0 动身,访问此顶点,然后顺次从V0的各个未被访问的邻接点动身深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到(使用堆栈).

     

    //使用邻接矩阵存储的无向图的深度优先遍历
    template <typename Type>
    void Graph<Type>::DFS()
    {
    stack<int> iStack;

    showVertex(0);
    vertexList[0]->wasVisted = true;
    iStack.push(0);

    while (!iStack.empty())
    {
    int top = iStack.top();
    int v = getAdjUnvisitedVertex(top);
    if (v == ⑴)
    {
    iStack.pop();
    }
    else
    {
    showVertex(v);
    vertexList[v]->wasVisted = true;
    iStack.push(v);
    }
    }

    //使其还可以再深/广度优先搜索
    for (int i = 0; i < nVerts; ++i)
    vertexList[i]->wasVisted = false;
    }

    BFS

       从图中的某个顶点V0动身,并在访问此顶点以后顺次访问V0的所有未被访问过的邻接点,以后按这些顶点被访问的前后次序顺次访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到.

      若此时图中尚有顶点未被访问,则另选图中1个未曾被访问的顶点作起始点,重复上述进程,直至图中所有顶点都被访问到为止(使用队列)。

     

    //使用邻接矩阵存储的无向图的广度优先遍历
    template <typename Type>
    void Graph<Type>::BFS()
    {
    queue<int> iQueue;

    showVertex(0);
    vertexList[0]->wasVisted = true;
    iQueue.push(0);

    while (!iQueue.empty())
    {
    int front = iQueue.front();
    iQueue.pop();
    int v = getAdjUnvisitedVertex(front);
    while (v != ⑴)
    {
    showVertex(v);
    vertexList[v]->wasVisted = true;
    iQueue.push(v);
    v = getAdjUnvisitedVertex(front);
    }
    }

    for (int i = 0; i < nVerts; ++i)
    vertexList[i]->wasVisted = false;
    }

    完全代码

    const int MAX_VERTS = 20;
    //顶点
    template <typename Type>
    class Vertex
    {
    public:
    Vertex(const Type &_node = Type())
    : node(_node), wasVisted(false) {}

    public:
    bool wasVisted; //增加1个访问位
    Type node;
    };
    //图
    template <typename Type>
    class Graph
    {
    public:
    Graph();
    ~Graph();

    void addVertex(const Type &vertex);
    void addEdge(int start, int end);
    void printMatrix();
    void showVertex(int v);
    void DFS();
    void BFS();

    private:
    int getAdjUnvisitedVertex(int v);

    private:
    Vertex<Type>* vertexList[MAX_VERTS];
    int nVerts;
    int adjMatrix[MAX_VERTS][MAX_VERTS];
    };
    template <typename Type>
    void Graph<Type>::DFS()
    {
    stack<int> iStack;

    showVertex(0);
    vertexList[0]->wasVisted = true;
    iStack.push(0);

    while (!iStack.empty())
    {
    int top = iStack.top();
    int v = getAdjUnvisitedVertex(top);
    if (v == ⑴)
    {
    iStack.pop();
    }
    else
    {
    showVertex(v);
    vertexList[v]->wasVisted = true;
    iStack.push(v);
    }
    }

    //使其还可以再深度优先搜索
    for (int i = 0; i < nVerts; ++i)
    vertexList[i]->wasVisted = false;
    }

    template <typename Type>
    void Graph<Type>::BFS()
    {
    queue<int> iQueue;

    showVertex(0);
    vertexList[0]->wasVisted = true;
    iQueue.push(0);

    while (!iQueue.empty())
    {
    int front = iQueue.front();
    iQueue.pop();
    int v = getAdjUnvisitedVertex(front);
    while (v != ⑴)
    {
    showVertex(v);
    vertexList[v]->wasVisted = true;
    iQueue.push(v);
    v = getAdjUnvisitedVertex(front);
    }
    }

    for (int i = 0; i < nVerts; ++i)
    vertexList[i]->wasVisted = false;
    }
    //获得下1个还没有访问的连通节点
    template <typename Type>
    int Graph<Type>::getAdjUnvisitedVertex(int v)
    {
    for (int j = 0; j < nVerts; ++j)
    {
    //首先是邻接的, 并且是未访问过的
    if ((adjMatrix[v][j] == 1) &&
    (vertexList[j]->wasVisted == false))
    return j;
    }
    return ⑴;
    }
    //打印节点信息
    template <typename Type>
    void Graph<Type>::showVertex(int v)
    {
    cout << vertexList[v]->node << ‘ ‘;
    }

    template <typename Type>
    Graph<Type>::Graph():nVerts(0)
    {
    for (int i = 0; i < MAX_VERTS; ++i)
    for (int j = 0; j < MAX_VERTS; ++j)
    adjMatrix[i][j] = 0;
    }
    template <typename Type>
    Graph<Type>::~Graph()
    {
    for (int i = 0; i < nVerts; ++i)
    delete vertexList[i];
    }
    template <typename Type>
    void Graph<Type>::addVertex(const Type &vertex)
    {
    vertexList[nVerts ++] = new Vertex<Type>(vertex);
    }
    template <typename Type>
    void Graph<Type>::addEdge(int start, int end)
    {
    //无向图
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
    }
    template <typename Type>
    void Graph<Type>::printMatrix()
    {
    for (int i = 0; i < nVerts; ++i)
    {
    for (int j = 0; j < nVerts; ++j)
    cout << adjMatrix[i][j] << ‘ ‘;
    cout << endl;
    }
    }

    //测试代码
    int main()
    {
    Graph<char> g;
    g.addVertex(‘A’); //0
    g.addVertex(‘B’); //1
    g.addVertex(‘C’); //2
    g.addVertex(‘D’); //3
    g.addVertex(‘E’); //4

    g.addEdge(0, 1); //A-B
    g.addEdge(0, 3); //A-D
    g.addEdge(1, 0); //B-A
    g.addEdge(1, 4); //B-E
    g.addEdge(2, 4); //C-E
    g.addEdge(3, 0); //D-A
    g.addEdge(3, 4); //D-E
    g.addEdge(4, 1); //E-B
    g.addEdge(4, 2); //E-C
    g.addEdge(4, 3); //E-D

    g.printMatrix();

    cout << "DFS: ";
    g.DFS();
    cout << "
    BFS: ";
    g.BFS();
    return 0;
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 数据结构基础(21) –DFS与BFS

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级