【数据结构】图的遍历及最小生成树

上一篇博客中讲了图的基本概念及如何存储,下面学习图的遍历及最小生成树的问题。

图的遍历

广度优先搜索(Breadth First Search, BFS)

举一个例子:
这里写图片描述
  假设我们都从顶点A开始遍历,左侧为有向图,它的广度优先搜索结果为:A D B E C;右侧为无向图,它的广度优先搜索结果为:A E D B C。
广度优先搜索类似于树的层序遍历,在实现的时候,需要借助队列来实现。

//我们使用一个数组来区别一个顶点是否已经遍历过,遍历过的设置为true。
    void BFS(const V& v)
    {
        queue<int> q;
        vector<bool> visited(_v.size(), false);//遍历过的置为true,默认为false
        size_t index = GetIndex(v);
        q.push(index);
        _BFS(q, visited);
        for (size_t i = 0; i < _v.size(); i++)//为什么要这么写?
            //假如我们的图中的一个顶点与其他的顶点没有关系,即两个顶点之间没有边,
            //那么如果我们不这么写,就会漏掉这个顶点。
            //因此,我们的处理方法是 先遍历一次,然后在看哪个点没有遍历,
            //如果有点没遍历,那么将该点push到队列中遍历。
        {
            if (visited[i] == false)
            {
                q.push(i);
                _BFS(q, visited);
            }
        }
        cout << endl;
    }

    void _BFS(queue<int>& q, vector<bool>& visited)
    {
        while (!q.empty())
        {
            size_t index = q.front();
            q.pop();
            if (visited[index] == true)
                continue;
            cout << _v[index] << " ";
            visited[index] = true;
            pNode pCur = _linkEdges[index];
            while (pCur)
            {
                if (visited[pCur->_dst] == false)
                    q.push(pCur->_dst);
                pCur = pCur->_pNext;
            }
        }
    }

还是上面图中的两个图为例:
这里写图片描述
  上图中,左侧为有向图,红色数字表示遍历的顺序,箭头表示遍历时是怎么走的,所以它的深度优先搜索结果为:A D E B C , 右侧为无向图,深度优先搜索的结果为:A D E C B。可以发现,遍历的结果并不是唯一的,跟你的图中边的存储有关系。

void DFS(const V& v)
    {
        size_t index = GetIndex(v);
        vector<bool> visited(_v.size(), false);
        _DFS(index, visited);

        for (size_t i = 0; i < _v.size(); i++)
        {
            if (visited[i] == false)
                _DFS(i, visited);
        }
        cout << endl;
    }

    void _DFS(int index, vector<bool>& visited)
    {
        cout << _v[index] << " ";
        visited[index] = true;
        pNode pCur = _linkEdges[index];
        while (pCur)
        {
            if (visited[pCur->_dst] == false)
                _DFS(pCur->_dst, visited);
            pCur = pCur->_pNext;
        }
    }

最小生成树

连通图中的每一颗生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不必再连通;反之,在其中假如一条边,就会形成回路。
若连通图由n个顶点构成,则生成树必有n个顶点和n-1条边。最小生成树是各边权值之和最小的生成树,因此,构成最小生成树有以下三点需要遵守:

  1. 只能使用图中的边来构成最小生成树
  2. 只能使用恰好n-1条边来链接图中的n个顶点
  3. 选用的n-1条边不嫩个构成回路

构成最小生成树有两种算法:Kruskal算法和Prim算法。

Kruskal算法

任给一个有n个顶点的连通网络N,首先构造一个有n个顶点组成,不含任何边的图G,其中,每个顶点自成一个连通分量,不断从N的边中找最小的一条,若该边的两个顶点来自不同的连通分量,则将此边假如到G中。如此重复,直至所有顶点在同一个连通分量上为止。
这里写图片描述
我们还是举一个例子:

  1. 新建一个图,只有顶点,没有边
  2. 将原图中边的权值,从小到大排序
  3. 我们有5个顶点,因此需要4条边
  4. 借助之前写过的并查集,如果两个顶点不在一个集合,那么将该边假如到新图中;否则,继续看下一条边。
    具体布置如下:
    这里写图片描述
    代码:
typedef Graph<V, W, IsDirect> Self;
    typedef Node LinkEdge;
    Self Kruskal()
    {
        Self g;
        g._v = _v;//新建一个图
        g._linkEdges.resize(_v.size());
        vector<LinkEdge*> edges;
        for (size_t i = 0; i < _v.size(); i++)
        {
            LinkEdge* pCur = _linkEdges[i];     
            while (pCur)
            {
                if (IsDirect || (!IsDirect && pCur->_src < pCur->_dst))//保存边的权值。
                                                   //无向图只需要保存一次,保存src<dst
                    edges.push_back(pCur);
                pCur = pCur->_pNext;
            }       
        }

        class Compare
        {
        public:
            bool operator()(const LinkEdge* left, const LinkEdge* right)
            {
                return left->_weight < right->_weight;
            }
        };
        sort(edges.begin(), edges.end(), Compare());//将保存的边的权值,从小到大排序

        size_t count = _v.size() - 1;//从前往后取n-1条边
        UnionFind u(_v.size());
        for (size_t i = 0; i < edges.size(); i++)
        {
            LinkEdge* pCur = edges[i];
            size_t srcRoot = u.FindRoot(pCur->_src);
            size_t dstRoot = u.FindRoot(pCur->_dst);
            if (srcRoot != dstRoot)//若两个顶点不在同一个集合,才将边加上
            {
                g._Add(pCur->_src, pCur->_dst, pCur->_weight);
                if (!IsDirect)//false为无向图
                    g._Add(pCur->_dst, pCur->_src, pCur->_weight);

                u.Union(pCur->_src, pCur->_dst);//合并
                count--;
                if (count == 0)
                    break;
            }
        }
        if (count > 0)
            cout << "最小生成树非法" << endl;
        return g;
    }

Prime算法

这里写图片描述 1. 给出一个只有顶点的空图; 2. 权值最小的10,将10加入到生成树中; 3. 原图中A,B相关联的边权值最小的是30,将30加入到生成树中; 4. 原图中A,B,E有关的边,权值最小的是30,将30加入到生成树中; 5. 以此类推,直至所有顶点连通。

相关文章
相关标签/搜索