大漠知秋的加油站

  • 首页
大漠知秋的加油站
你就当我的烂笔头吧
  1. 首页
  2. C++
  3. 正文

图的广度优先遍历

2022年7月7日 512点热度 0人点赞 0条评论

广度遍历路径规划

简介

官渡优先遍历

  1. 增加队列,用来存放待遍历的顶点。
  2. 先把起始顶点扔进队列。
  3. 从队列中取出第一个顶点,遍历其相邻顶点。
    1. 如果已经遍历过 或者 已经是在队列中等待遍历了,跳过。
    2. 否则就加入队列,等待遍历。
  4. 持续 3,直到没有待遍历的顶点。

广度遍历可以求最短路径。

实现

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

/**
 * 广度遍历求最短路径
 *
 * 时间复杂度:
 *  稀疏图:O(V + E)
 *  稠密图:O(V^2)
 */
template<typename Graph>
class ShortestPath {
private:
    /** 图 */
    Graph &G;
    /** 在广度遍历时,是否访问过了 */
    bool *visited;
    /** 源点、起始点 */
    int s;
    /**
     * 当前顶点是从哪个顶点过来的
     * 索引为当前顶点,值为当前顶点的上一个顶点
     */
    int *from;
    /**
     * 记录顶点距离 源点的距离
     */
    int *ord;

public:
    ShortestPath(Graph &graph, int s) : G(graph) {
        visited = new bool[G.v()];
        from = new int[G.v()];
        ord = new int[G.v()];

        // 初始化时,所有顶点都没有被访问过。
        for (int i = 0; i < G.v(); ++i) {
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this->s = s;

        // 开始广度遍历顶点,源点的 from 为 -1。
        // 创建待遍历队列
        std::queue<int> q;
        // 先把源点扔进去
        q.push(s);
        // 标记为已遍历或者待遍历
        visited[s] = true;
        // 起始点距离起始点的距离肯定是 0
        ord[s] = 0;

        // 开始遍历队列
        while (!q.empty()) {
            // 取得队列中第一个的顶点
            int v = q.front();
            q.pop();
            // 遍历顶点的邻边并添加到队列
            typename Graph::AdjIterator adjIter(G, v);
            for (int i = adjIter.begin(); !adjIter.end(); i = adjIter.next()) {
                // 当前邻边必须是没有遍历过 并且 不在在待遍历中了
                if (!visited[i]) {
                    // 可以入队列
                    q.push(i);
                    // 标记为已遍历或者待遍历
                    visited[i] = true;
                    // 从 v 来到 i
                    from[i] = v;
                    // 记录 i 距离起始点的距离
                    ord[i] = ord[v] + 1;
                }
            }
        }

    }

    ~ShortestPath() {
        delete[] visited;
        delete[] from;
    }

    /**
     * 查看源点 与 w 顶点之间是否存在路径
     *
     * 如果 w 被遍历过,说明在一个连通分量中,肯定是存在路径的。
     */
    bool hasPath(int w) {
        assert(w >= 0 && w < G.v());

        return visited[w];
    }

    /**
     * 获取源点到 w 顶点的路径
     */
    void path(int w, std::vector<int> &vector) {
        assert(hasPath(w));

        std::stack<int> s;

        int p = w;
        while (p != -1) {
            // 只要 p 不等于 -1,说明还没倒推到源点(源点的 from 是 -1),就 push 到栈中
            s.push(p);
            p = from[p];
        }

        vector.clear();
        while (!s.empty()) {
            vector.push_back(s.top());
            s.pop();
        }
    }

    /**
     * 打印路径
     */
    void showPath(int w) {
        assert(hasPath(w));

        std::vector<int> vec;
        path(w, vec);
        for (int i = 0; i < vec.size(); i++) {
            std::cout << vec[i];
            if (i == vec.size() - 1)
                std::cout << std::endl;
            else
                std::cout << " -> ";
        }
    }

    /**
     * 查看源点到顶点 w 的距离
     */
    int length(int w) {
        assert(hasPath(w));

        return ord[w];
    }
};

测试

void testPath() {
    string filename = "testG2.txt";
    SparseGraph g = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph(g, filename);
    g.show();

    ShortestPath<SparseGraph> bfs(g, 0);
    cout << "BFS : ";
    bfs.showPath(6);
}

// testG2.txt
7 8
0 1
0 2
0 5
0 6
3 4
3 5
4 5
4 6
标签: C++ 图论 数据结构与算法
最后更新:2022年7月7日

大漠知秋

唯黄昏而思烛明,唯覆雪始念日暖,唯放手方知情真,今困苦而怀峥嵘,今飘零而涌乡愁,今孑然而徒唏嘘,唏嘘成愁。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

文章目录
  • 广度遍历路径规划
    • 简介
    • 实现
    • 测试

COPYRIGHT © 2022 大漠知秋的加油站. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang