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

痛定思痛。 2022-05-26 12:00 166阅读 0赞

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

### 图的遍历 ###

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

举一个例子：  
![这里写图片描述][70]  
　　假设我们都从顶点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;
                }
            }
        }

#### 深度优先搜索(Depth First Search) ####

还是上面图中的两个图为例：  
![这里写图片描述][70 1]  
　　上图中，左侧为有向图，红色数字表示遍历的顺序，箭头表示遍历时是怎么走的，所以它的深度优先搜索结果为：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中。如此重复，直至所有顶点在同一个连通分量上为止。  
![这里写图片描述][70 2]  
我们还是举一个例子：

1.  新建一个图，只有顶点，没有边
2.  将原图中边的权值，从小到大排序
3.  我们有5个顶点，因此需要4条边
4.  借助之前写过的[并查集][Link 2]，如果两个顶点不在一个集合，那么将该边假如到新图中；否则，继续看下一条边。  
    具体布置如下：  
    ![这里写图片描述][70 3]  
    代码：

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算法 ####

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

[Link 1]: https://blog.csdn.net/wei_cheng18/article/details/80037496
[70]: /images/20220526/3ca7082bc88a47a0a15ff63354539e9f.png
[70 1]: /images/20220526/bd7c31cdbd3d4a8ca163910b4a4002a2.png
[70 2]: /images/20220526/451fd6b28ad74104b7a6d582185fbe76.png
[Link 2]: https://blog.csdn.net/wei_cheng18/article/details/79917908
[70 3]: /images/20220526/71e9ace60aad45ddbc27cd834ea9c581.png
[70 4]: /images/20220526/9e2c41a0eeee423cae497294f3420a06.png