【图】图的遍历以及最小生成树_图的遍历及最小生成树

图的遍历

图的遍历图和树的遍历类似，那就是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程就叫做图的遍历。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。

1、深度优先遍历 DFS

深度优先遍历（Depth_First_Search）,也称为深度优先搜索，简称DFS。

沿着树的深度遍历树的节点，尽可能深的搜索树的分支节点，当节点v的所有边被访问过，搜索将回溯到发现节点v的那条边的起始位置，然后继续访问未被访问过的节点，直到所有的节点被访问。
此就需要标记访问过的节点。

类似于二叉树的前序遍历。

代码时基于邻接表实现的。
对于图来说，不一定都是连通图，所以深度优先遍历完其中的连通图后，还要查看还有节点是非连通图未访问的。

//深度优先遍历：
    void DFS(const V& v)
    {
        cout << "深度优先遍历：" << endl;
        //标记访问过的节点
        vector<bool> visited(_vex.size(), false);
        int idx = GetIndexOfVertex(v);
        _DFS(idx, visited);

        //非连通的访问
        for (size_t i = 0; i < _vex.size(); ++i)
        {
            if (!visited[i])
                _DFS(i, visited);
        }
        cout << "NULL" << endl;
    }

    void _DFS(size_t idx,vector<bool>& visitted)
    {
        //未被访问的节点，做广度搜索
        if(!visited[idx])
        {
            cout << idx << "-->";
            visited[idx] = true;
            //邻接表，所以访问单链表
            LinkEdge<W>* pCur = _LinkTable[idx];
            while (pCur)
            {
                _DFS(pCur->_desIndex, visited);
                pCur = pCur->_pNext;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2、广度优先遍历 BFS
BFS是从根节点开始出发，沿着树的宽度遍历树的节点，直到所有的节点被访问。
有点类似于树的层次遍历。

下面代码时基于邻接表实现的

//广度优先遍历图：队列
    void BFS(const V& v)
    {
        cout << "广度优先遍历：" << endl;
        vector<bool> visited(_vex.size(), false);
        _BFS(v, visited);

        //非连通的访问
        for (size_t i = 0; i < _vex.size(); ++i)
        {
            if (!visited[i])
                _BFS(_vex[i],visited);
        }
        cout << "NULL" << endl;
    }

    void _BFS(const V& v,vector<bool>& visited)
    {
        queue<size_t> q;
        int idx = GetIndexOfVertex(v);
        q.push(idx);
        while(!q.empty())
        {
            if (!visited[idx])
            {
                cout << idx << "-->";
                visited[idx] = true;
                q.pop();
                LinkEdge<W>* pCur = _LinkTable[idx];
                while (pCur)
                {
                    q.push(pCur->_desIndex);
                    pCur = pCur->_pNext;
                }
            }
        }       
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

图的最小生成树

生成树是将图中所有顶点以最少的边连通的子图。
权值和最小的生成树就是最小生成树。

从最小生成树的定义可知，构造有n个结点的无向连通带权图的最小生成树,必须满足以下三条：
（1）构造的最小生成树必须包括n个结点；
（2）构造的最小生成树中有且只有n-1条边；
（3）构造的最小生成树中不存在回路。

构造最小生成树的方法有许多种，典型的构造方法有两种，一种称作普里姆（Prim）算法，另一种称作克鲁斯卡尔（Kruskal）算法。

普里姆算法

普里姆算法思想是：利用贪心的算法。

从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

(1)输入：一个加权连通图，其中顶点集合为V，边集合为E；

(2)初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；

(3)重复下列操作，直到Vnew = V：
在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
将v加入集合Vnew中，将（u, v）加入集合Enew中；

(4)输出：使用集合Vnew和Enew来描述所得到的最小生成树。

基于邻接表代码实现
在寻找最小值，可以借助堆，

//比较器
struct Biger
    {
        bool operator()(LinkEdge<W>* Left, LinkEdge<W>* Right)
        {
            return Left->_edge >  Right->_edge;
        }
    };
//最小生成树prime算法
    pair<GraphLink<V, W>, bool> Prime(const V& vertex)
    {
        //定义一个图来接收最小生成树，下面初始化图g
        GraphLink<V, W> g;
        g._vex.resize(_vex.size());
        for (size_t idx = 0; idx < _vex.size(); ++idx)
            g._vex[idx] = _vex[idx];
        g._IsDirected = false;
        g._LinkTable.resize(_vex.size()-1, NULL);


        //给一个起始顶点，将顶点为起点的边放到最小堆中,每次从最小堆中取堆顶加到图中(判断是否已经加入)
        vector<bool> flag(_vex.size(), false);//标记顶点是否已经加入图中 
        vector<LinkEdge<W> *> vEdge;
        int index = GetIndexOfVertex(vertex);
        LinkEdge<W> *pCur = _LinkTable[index];
        while (pCur)
        {
            vEdge.push_back(pCur);
            pCur = pCur->_pNext;
        }
        //构建堆
        make_heap(vEdge.begin(), vEdge.end(), Biger());

        int count = 0;//统计加入边的数量，n-1条边就是最小生成树
        while (true)
        {
            //从最小堆中取出
            pCur = vEdge[0];
            pop_heap(vEdge.begin(), vEdge.end(), Biger());
            vEdge.pop_back();
            if (!flag[pCur->_desIndex])
            {
                g._AddEdge(pCur->_srcIndex, pCur->_desIndex, pCur->_edge);
                if (++count == _vex.size() - 1)
                    return make_pair(g, true);
                flag[pCur->_srcIndex] = true;
            }
            index = pCur->_desIndex;
            if (!flag[index])
            {
                pCur = _LinkTable[index];
                while (pCur)
                {
                    if (!flag[pCur->_desIndex])
                    {
                        vEdge.push_back(pCur);
                        push_heap(vEdge.begin(), vEdge.end(), Biger());
                    }   
                    pCur = pCur->_pNext;
                }   
            }

        }

        return make_pair(g, false);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2、克鲁斯卡尔算法

其思想就是直接了当的贪心，每次都将权值最短的边收进来：可以将每个顶点都看成一棵树，然后将权值最短的边的顶点连接起来，在不构成回路的情况下，将这些森林合并成一棵树。

考虑到构成回路的问题，这里我用到并查集。
并查集的实现 可以看下一篇博客，)

并查集的实现

    //排序比较器
    struct Compare
    {
        bool operator()(LinkEdge<W>* Left, LinkEdge<W>* Right)
        {
            return Left->_edge <  Right->_edge;
        }
    };

    //无向图的最小生成树
    pair<GraphLink<V, W>, bool> GetMinTree()
    {

        //1 将所有的边放在vector中，过滤掉重复的边
        vector<LinkEdge<W> *> edge;
        for (size_t i = 0; i < _LinkTable.size(); ++i)
        {
            LinkEdge<W> * pCur = _LinkTable[i];
            while (pCur)
            {
                if (pCur->_srcIndex < pCur->_desIndex)//过滤掉重复的边
                    edge.push_back(pCur);
                pCur = pCur->_pNext;
            }
        }

        //2 将vector 排序
        sort(edge.begin(), edge.end(), Compare());

        //生成图，保存结果
        GraphLink<V, W> g;
        g._vex.resize(_vex.size());
        for (size_t idx = 0; idx < _vex.size(); ++idx)
            g._vex[idx] = _vex[idx];
        g._LinkTable.resize(_LinkTable.size(), NULL);
        g._IsDirected = false;

        //3 从vector中取出最小值，添加到图中
        //并查集初始化
        UnionFindSet un(_vex.size());
        int count = 0;//统计加入的边数量
        for (size_t j = 0; j < edge.size(); ++j)
        {
            LinkEdge<W>* pEdge = edge[j];
            //检测是否构成了环
            if (!(un.IsSameSet(pEdge->_srcIndex,pEdge->_desIndex)))
            {
                g._AddEdge(pEdge->_srcIndex,pEdge->_desIndex, pEdge->_edge);
                un.Union(pEdge->_srcIndex, pEdge->_desIndex);
                if (++count == _vex.size() - 1)
                {
                    g._LinkTable.resize(count);
                    return make_pair(g, true);
                }               
            }
        }

        return make_pair(g, false);

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60