高阶数据结构-图

[bosthhe1]

图分为无向图和有向图，其中图的路径是权值，图关注的就是顶点和边的权值，所以可以根据边的多少分为稠密图和稀疏图但是在了解图之前，需要了解一下并查集，并查集可以看作森林，并查集可以看作关系图的一种映射 首先我们需要初始化并采集表，这里的-1代表每个节点都是自己的根节点

[bosthhe1]

我们假设下表为4和下标为5的节点，可以和下标位0的节点相结合，并查集则会变成下方的图 我们看到下标4和下标5的值存的下标0，而下标为0的值则将4和5的-1并起来，为-3，所以简单总结得出，如果下标对应的值为正数，则表示存的是父节点的下标，如果表示为负数，则表示该节点为根节点，切根节点的数目为对应值的绝对值

[bosthhe1]

我们加入再让6、8、9与下标为2的节点结合，并查集的图为： 这里和上面规则一样，当然如果需要合并0和2，可以将2下标的值加给0下标的值，然后将2下标的值改为0，也可以反过来，具体谁加到谁上去没有规定，只需要建立链接就可以 leetcode相关题目 -> https://leetcode.cn/problems/number-of-provinces/

[bosthhe1]

下面我们看到有向图和无向图的区别 有向图就是它的边有方向，以微博关注的明星，抖音关注的博主为例子，则为有向图，二叉树就是典型的不带环有向图。

无向图则就是边没有方向的，以微信qq好友为例子

[bosthhe1]

权值是一种将一个关系抽象成一个数据，比如无向图的qq好友的亲密度等。 权值是体现一个无向图的关系图的重要条件，一般我们是以二维矩阵来表示两个顶点之间的权值，以上面无向图为例子： 其中如果没有关系就使用一个特殊符号来代替，无向图的二维矩阵关系图是一个沿着对角线对称的一个二维矩阵 图除了矩阵表示，还有挂表的方式表示：既出边表和入边表，出边表就是该店可以到达的地方，入边表就是什么点可以到达该点的路径 我们可以像哈希桶一样做出边表(入边表)，下面以有向图做出边表为例子 注意这里面的挂表是代表A的出边表所指向的对象有哪些，例如A->B->C，代表A有两个指向一个指向B一个指向C，而不是A指向B，B指向C，这些节点中一般保存着目的地的地址和权值，以及指针，方便A出边的指向

[bosthhe1]

//出边表

template<class W>
struct Edge
{
    size_t _dest;//存目的地
    W _w;//存发源地到目的地的权值
    Edge<W>* next;//方便连接在一条链上
    Edge(size_t dest,const W& w)
        :_dest(dest)
        ,_w(w)
        ,next(nullptr)
    {}
};
template<class V, class W, W Max_w = INT_MAX, bool Direction = false>
class _Graph
{
    typedef Edge<W> Edge;
public:
    _Graph(const V* v, size_t n)//图的外面会给进来一个V类型数组,将数组中的每一个元素都分散开来，存在对应的下标
    {
        _vertexs.resize(n);
        for (int i = 0; i < n; i++)
        {
            _vertexs[i] = v[i];
            _IndexMap[v[i]] = i;
        }
        _table.resize(n, nullptr);
    }
    size_t GetVertexIndex(const V& v)
    {
        auto ret = _IndexMap.find(v);
        if (ret != _IndexMap.end())
        {
            return _IndexMap[v[i]];
        }
        return -1;
    }
    void AddEdge(const V& src, const V& dst, const W& w)
    {
        if (_IndexMap.find(src) != _IndexMap.end() &&
            _IndexMap.find(dst) != _IndexMap.end() &&
            _IndexMap.find(src) != _IndexMap.find(dst))
        {
            int srci = _IndexMap[src];
            int dsti = _IndexMap[dst];
            Edge* Ed = new Edge(dsti, w);
            Ed->next = _table[srci];
            _table[srci] = Ed;
            if (Direction == false)
            {
                Edge* Ed = new Edge(srci, w);
                Ed->next = _table[dsti];
                _table[dsti] = Ed;
            }
        }
    }
    void Print()
    {
        for (int i = 0; i < _table.size(); i++)
        {
            Edge* cur = _table[i];
            cout << "_table" << "[" << i << "] :";
            while (cur)
            {
                cout << "[" << cur->_dest << "]:"<<(_vertexs[cur->_dest].c_str())<<" ->";

                cur = cur->next;
            }
            cout << "nullptr" << endl;
            cout << endl;
        }
    }
private:
    vector<V> _vertexs;//顶点集合
    map<V, int> _IndexMap;//顶点和下标的映射关系
    vector<Edge*> _table;//出边表，使用链表的新式挂起起来
};

[bosthhe1]

二维矩阵表示

//V代表外面数组的类型，W代表权值的类型，一般默认W为int，Direction代表有向图或无向图，为false为无向图，为true为有向图
template<class V,class W,W Max_w = INT_MAX,bool Direction = false>
class Graph
{
    typedef Graph<V, W, INT_MAX, Direction> Self;
public:
    Graph() = default;
    Graph(const V* v,size_t n)//图的外面会给进来一个v类型数组,将数组中的每一个元素都分散开来，存在对应的下标
    {
        _vertexs.resize(n);
        for (int i = 0; i < n; i++)
        {
            _vertexs[i] = v[i];
            _IndexMap[v[i]] = i;
        }
        _matrix.resize(n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                _matrix[i].push_back(INT_MAX);
            }
        }
    }
    size_t GetVertexIndex(const V& v)
    {
        auto ret = _IndexMap.find(v);
        if (ret != _IndexMap.end())
        {
            return _IndexMap[v[i]];
        }
        return -1;
    }
    void _AddEdge(size_t src, size_t dst, const W w)
    {
        _matrix[src][dst] = w;
        if (Direction == false)
            _matrix[src][dst] = w;
    }
    void AddEdge(const V& src, const V& dst, const W& w)
    {
        if (_IndexMap.find(src) != _IndexMap.end()&&
            _IndexMap.find(dst) != _IndexMap.end()&&
            _IndexMap.find(src) != _IndexMap.find(dst))
        {
            int j = _IndexMap[src];
            int k = _IndexMap[dst];
            _matrix[j][k] = w;
            if (Direction == false)
            _matrix[k][j] = w;
        }
    }
    void Print()
    {
        cout << "   ";
        for (int i = 0; i < _matrix.size(); i++)
        {
            cout << i << "    ";
        }
        cout << endl;
        for (int i = 0; i < _matrix.size(); i++)
        {
            cout << i << "  ";
            for (int j = 0; j < _matrix[i].size(); j++)
            {
                if (_matrix[i][j] == INT_MAX)
                {
                    cout << "*" << "    ";
                }
                else
                {
                    cout << _matrix[i][j] << "   ";
                }
            }
            cout << endl;
        }
    }
    void BFS(size_t n)
    {
        //自己想的，还不错
        //queue<vector<W>> q;
        //vector<bool> index(_vertexs.size(),false);
        //q.push(_matrix[n]);
        //int Count = 1;
        //index[n] = true;
        //cout << _vertexs[n].c_str() << endl;
        //while (!q.empty())
        //{
        //  vector<W> vw = (q.front());
        //  q.pop();
        //  Count--;
        //  for (int i = 0; i < vw.size(); i++)
        //  {
        //      if (vw[i] != INT_MAX&&index[i]==false)
        //      {
        //          cout << _vertexs[i].c_str()  << "[" << i << "]:" << " ";
        //          index[i] = true;
        //          q.push(_matrix[i]);
        //      }
        //  }
        //  if (Count == 0)
        //  {
        //      Count = q.size();
        //      cout << endl;
        //  }
        //}
        queue<int> q;
        vector<bool> index(_vertexs.size(), false);
        q.push(n);
        int Count = 1;
        size_t i = _vertexs.size();
        index[n] = true;
        cout << _vertexs[n].c_str() << endl;
        while (!q.empty())
        {
            while (Count--)
            {
                int src = q.front();
                q.pop();
                for (int j = 0; j < i; j++)
                {
                    if (_matrix[src][j] != INT_MAX&&index[j] == false)
                    {
                        cout << _vertexs[j].c_str() << "[" << j << "]:" << " ";
                        index[j] = true;
                        q.push(j);
                    }
                }
            }
            Count = q.size();
            cout << endl;
            if (q.empty())
            {
                for (int j = 0; j < n;j++)
                {
                    q.push(j);
                    break;
                }
            }
        }
    }
    void DFS(size_t i)
    {
        int n = _vertexs.size();
        vector<bool> index(n, false);
        index[i] = true;
        cout << _vertexs[i].c_str() << " ";
        _DFS(i,index);
    }
    struct Edge
    {
        size_t _src;
        size_t _dest;
        W _w;
        Edge(size_t src,size_t dest, const W& w)
            :_src(src)
            ,_dest(dest)
            , _w(w)
        {}
        bool operator>(const Edge& e)const
        {
            return _w > e._w;
        }
    };
    W Kruskal(Self& mintree)//这是计算最小生成树，传进来的mintree是用来存储最小生成树
    {
        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
        size_t n = _vertexs.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (_matrix[i][j] != INT_MAX)
                {
                    Edge ed(i, j, _matrix[i][j]);
                    pq.push(ed);
                }
            }
        }
        W _w =W();
        vector<bool> v(n, false);
        UnioFindSet<int> ufs(n);
        while (!pq.empty())
        {
            Edge e = pq.top();
            pq.pop();
            if (ufs.Union(e._src, e._dest))
            {
                cout << e._src << "->" << e._dest << ":" << e._w << endl;
                mintree._AddEdge(e._src, e._dest, e._w);
                _w += e._w;
                n--;
            }
        }
        if (n == 1)
        {
            return _w;
        }
        return W();
    }
    private:
        void _DFS(size_t src, vector<bool>& index)
        {
            for (int i = 0; i < _vertexs.size();i++)
            {
                if (_matrix[src][i] != INT_MAX&&index[i] == false)
                {
                    cout << _vertexs[i].c_str() << " ";
                    index[i] = true;
                    _DFS(i, index);
                }
            }
            return;
        }
private:
    vector<V> _vertexs;//顶点集合
    map<V, int> _IndexMap;//顶点和下标的映射关系
    vector<vector<W>> _matrix;//顶点和顶点的权值关系
};