欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的实现(带有深度/广度优先遍历/最小生成树算法)

程序员文章站 2024-01-23 16:14:40
...

连通图

  在图中,任意俩个节点都有一条路径,我们把这种图称为连通图。

生成树

  连通图可能有多个边其中可能有环,但是生成树是由N个节点,N-1条边构成的连通图。它是一个特殊的连通图,其中没有环路。

最小生成树

  因为N个节点,N-1条边构成生成树。那么就存在多个生成树,那么这么生成树中权值最小的生成树叫做最小生成树。
  kruskal是构成最小生成树的一种算法,这个算法就是在图中不断地选出权值最小的边,一直选出N-1条即可。如果选的过程中遇见有构成环路的边,就选下一条权值次小的边即可。

广度优先/深度优先

  这是俩种不同遍历图的方式,深度优先强调一直遍历,直到遍历到无法遍历的位置,再回退到上一节点,遍历与上一节点相邻的另一个节点。一般用递归实现。
  广度优先,强调先把当前节点相邻的节点都访问了,然后在遍历相邻节点的相邻节点,一般用队列实现。因为队列是头删尾进,先进先出的原则,所以更好符合条件。

代码实现

#pragma once
#include<string>
#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include"Union.h"
using namespace std;
struct Edge
{
    Edge( size_t src, size_t dst,int weight)
    :_weight(weight), _src(src), _dst(dst)
    {}
    int _weight;
    size_t _src;
    size_t _dst;
    Edge * next;
};
template<class V, bool digraph>
class graph
{
public:
    graph()
    {}
    graph(vector<V>&vertrix)
    {
        _vertrix.reserve(vertrix.size());
        int index = 0;
        for (auto&i : vertrix)
        {
            _vertrix.push_back(i);
            _hash[i] = index++;
        }
        linktable.resize(_vertrix.size());
    }
    graph(const graph<V, digraph>&object)
        :_vertrix(object._vertrix), linktable(object.linktable), _hash(object._hash)
    {}
    graph<V, digraph>&operator=(const graph<V, digraph>object)
    {
        _vertrix.swap(object._vertrix);
        _hash.swap(object._hash);
        // this->linktable.swap(object.linktable);
    }
    void Addedge(const V&v1, const V&v2, int weight)
    {
        int src = _hash[v1];
        int dst = _hash[v2];
        _Addedge(src, dst, weight);
        if (digraph == false)
            _Addedge(dst, src, weight);
    }
    void BFS()
    {
        queue<int> qcon;
        qcon.push(0);
        vector<bool> visited(_vertrix.size(), false);
        Edge * pCur = NULL;
        int src = 0;
        while (!qcon.empty())
        {
            src = qcon.front();
            qcon.pop();
            cout << _vertrix[src] << "->";
            visited[src] = true;
            pCur = linktable[src];
            while (pCur)
            {
                if (visited[pCur->_dst] == false)
                {
                    qcon.push(pCur->_dst);
                    visited[pCur->_dst] = true;//防止有的节点被多次push
                }
                pCur = pCur->next;
            }
        }
    }
    void DFS()
    {
        vector<bool> visited(_vertrix.size(), false);
        _DFS(0, visited);
    }
    bool kruskal(graph<V, digraph>&mintree)
    {
        mintree._vertrix = _vertrix;
        mintree._hash = mintree._hash;
        mintree.linktable.resize(linktable.size());
        Uoion uoiobject(_vertrix.size());
        struct compareGreater
        {
            bool operator()(Edge*parent, Edge*child)
            {
                return parent->_weight > child->_weight;
            }
        };
        priority_queue<Edge*, vector<Edge*>, compareGreater> MinHeap;
        Edge * pCur = NULL;
        for (auto&i : linktable)
        {
            pCur = i;
            while (pCur)
            {
                if (pCur->_src < pCur->_dst)
                    MinHeap.push(pCur);
                pCur = pCur->next;
            }
        }
        int N = _vertrix.size() - 1;
        if (MinHeap.size()<N)
        {
            cerr << "不是连通图,请先构造出来连通图" << endl;
            return false;
        }
        int src = 0;
        int dst = 0;
        while (N)
        {
            if (MinHeap.size() != 0)
                pCur = MinHeap.top();
            else
            {
                cerr << "给的图无法构成最小生成树,可能环路过多,边数过少" << endl;
                return false;
            }
            MinHeap.pop();
            src = pCur->_src;
            dst = pCur->_dst;
            if (uoiobject.GetRoot(src) != uoiobject.GetRoot(dst))
            {
                mintree._Addedge(src, dst, pCur->_weight);
                uoiobject.uni(src, dst);
                --N;
            }
        }
        return true;
    }
    ~graph()
    {
        Edge * pCur = NULL;
        Edge * pNext = NULL;
        for (auto&i : linktable)
        {
            pCur = i;
            while (pCur)
            {
                pNext = pCur->next;
                delete pCur;
                pCur = pNext;
            }
        }
    }
protected:
    void _DFS(size_t src, vector<bool>&visited)
    {
        cout << _vertrix[src] << "->";
        visited[src] = true;
        Edge* pCur = linktable[src];
        while (pCur)
        {
            if (visited[pCur->_dst] == false)
                _DFS(pCur->_dst, visited);
            pCur = pCur->next;
        }
    }
    void _Addedge(int src, int dst, int weight)
    {
        Edge * pCur = new Edge(src, dst, weight);
        pCur->next = linktable[src];
        linktable[src] = pCur;
    }
    private:
        vector<V> _vertrix;//vector析构函数会类型萃取,如果所ADT类型一个一个调用
        vector<Edge*> linktable;//析构函数,如果是内置类型什么都不做。
        unordered_map<V, int> _hash;//所以linktable我们得自己释放 
};

#include<vector>
using namespace std;
class Uoion
{
public:
    Uoion(int n = 0)
        :_uoion(n + 1, -1)
    {}
    int GetRoot(int x)
    {
        while (_uoion[x] >= 0)
        {
            x = _uoion[x];
        }
        return x;
    }
    int uni(int x, int y)
    {
        int Root = x;
        int Root2 = y;
        while (_uoion[Root] >= 0 || _uoion[Root2] >= 0)
        {
            if (_uoion[Root] >= 0)
                Root = _uoion[Root];
            if (_uoion[Root2] >= 0)
                Root2 = _uoion[Root2];
        }
        if (Root != Root2)
        {
            _uoion[Root] += _uoion[Root2];
            _uoion[Root2] = Root;
        }
        return Root;
    }
    int  Size()
    {
        int ret = 0;
        size_t size = _uoion.size();
        for (size_t i = 0; i<size; ++i)
        {
            if (_uoion[i]<0)
                ++ret;
        }
        return ret;
    }
private:
    vector<int> _uoion;
};
#include"graph.h"

int main()
{
    vector<string> str = { "西安", "上海", "广州", "深圳", "北京" };
    graph<std::string, false> graphobject(str);
    graphobject.Addedge("西安", "上海", 100);
    graphobject.Addedge("西安", "北京", 200);
    graphobject.Addedge("北京", "上海", 300);
    graphobject.Addedge("上海", "深圳", 400);
    graphobject.Addedge("深圳", "广州", 500);
    graphobject.Addedge("北京", "广州", 600);
    graphobject.DFS();
    cout << endl;
    graphobject.BFS();
    graph<std::string, false> mintree;
    graphobject.kruskal(mintree);
    mintree.DFS();
    return 0;
}
相关标签: dst kruskal算法