目录

1. 排序

2.并查集

3.图

1.排序:

1.1 概念:

        排序就是将数据按照某种规则进行排列, 具有某种顺序. 分为内排序和外排序.

内排序就是: 将数据放在内存中的排序; 外排序是: 数据太多无法在内存中排序的.

 1.2 插入排序:

        插入排序包含: 直接插入排序和希尔排序.

(1) 直接插入排序:

        (这里图是借用其他博主的), 直接插入排序就是将第i个数值进行和前i数值依次比较, i数值小就一直放到前面, 直到值比他更小或者比完. 时间复杂度是O(N^2). 稳定性: 稳定.

 

void InsertSort(int* a, int n){    for(int i = 0; i < n - 1; i++)    {        int end = i;        int tmp = a[end+1];        while(end >= 0)        {            if(tmp < a[end])            {                a[end + 1] = a[end];                end--;            }            else            {                break;            }        }        a[end + 1] = tmp;    }}

 (2) 希尔排序:

        是采用gap进行分割前后数, 第i个数和i+gap个数进行比较如果a[i+gap]小于a[i]就交换.

gap算一趟, gap每次缩小1/2;  进行每趟调整. 时间复杂度是:O(NlogN); 稳定性: 不稳定.

void ShellSort(int* a, int n){    int gap = n;    while(gap > 1)    {        gap = gap / 2;        for(int i = 0; i < n - gap; i++)        {            int end = i;            int tmp = a[end + gap];            while(end >= 0)            {                if(tmp < a[end])                {                    a[end + gap] = a[end];                    end -= gap;                 }                else                {                    break;                }            }            a[end + gap] = tmp;        }    }}

1.3 选择排序:

选择排序包括选择排序和堆排序:

(1) 选择排序:

                每趟找到比最小的数, 遍历全数列的那种, 然后进行交换i和最小数值的位置. 时间复杂度是O(N^2); 稳定性: 不稳定.

        还可以依次选两个数, 最大和最小, 放在左边和右边, 进行遍历选择.

void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}void SelectSort(int* a, int n){    for(int i = 0; i < n; i++)    {        int start = i;        int min = start;        while(start < n)        {            if(a[start] < a[min])                min = start;            start++;        }        Swap(&a[i], &a[min]);    }}void SelectSort(int* a, int n){    int left = 0;    int right = n - 1;    while(left < right)    {        int minIndex = left;        int maxIndex = left;        for(int i = left; i <= right; i++)        {            if(a[i] < a[minIndex])                minIndex = i;            if(a[i] > a[maxIndex])                maxIndex = i;        }        Swap(&a[minIndex], &a[left]);        if(left == maxIndex)        {            maxIndex = minIndex;        }        Swap(&a[maxIndex], &a[right]);        left++;        right--;    }}

(2) 堆排序:

        具体看上一篇博客:数据结构(二)

void AdjustDown(int* a, int n, int parent){    int child = parent * 2 + 1;    while(child < n)    {        if(child + 1 < n && a[child + 1] < a[child])        {            child++;        }        if(a[child] < a[parent])        {            Swap(&a[child], &a[parent]);            parent = child;            child = parent * 2 + 1;        }        else        {            break;        }    }}void StackSort(int* a, int n){    for(int i = (n-1-1) / 2; i >= 0; i--)    {        AdjustDown(a, n, i);    }    int end = n - 1;    while(end)    {        Swap(&a[0], &a[end]);        AdjustDown(a, end, 0);        end--;    }}

 1.4 交换排序:

        交换排序包含冒泡排序和快速排序:

(1) 冒泡排序:

        相邻两个数进行比较, 大的就交换,这样到最后的就一定是最大的数, 下一次只要遍历到这个最大数前一个即可. 时间复杂度是: O(N^2); 稳定性: 稳定;

void BubbleSort(int* a, int n){    int end = 0;    for(end = n - 1; end >= 0; end--)    {        int exchange = 0;        for(int i = 0; i < end; i++)        {            if(a[i] > a[i+1])            {                Swap(&a[i], &a[i+1]);                exchange = 1;            }        }        if(exchange = 0)            break;    }}

 (2) 快速排序:

        时间复杂度就是O(NlogN), 稳定性: 不稳定.

 a.hoare版本

        最左边作为key进行比较的值, 其次就是left和right不断往中间走, right找到小于key的, left找到大于key的, 然后交换right和left; 将left和right相遇的点在进行分治法使用快速排序.

        

void QuickSort1(int* a, int begin, int end){    if(begin >= end)        return;        int left = begin;    int right = end;    int keyi = left;    while(left < right)    {        while(left < right && a[right] >= a[keyi])        {            right--;        }        while(left < right && a[left] <= a[keyi])        {            left++;        }        if(left < right)        {            Swap(&a[left], &a[right]);        }    }    int meeti = left;    Swap(&a[keyi], &a[meeti]);    QuickSort1(a, begin, meeti-1);    QuickSort1(a,  meeti+1, end);}

b.挖坑法:

        和上面差别就是把key下标的值取出来了, 但是过程还是和上面一样.

void QuickSort2(int* a, int begin, int end){    if(begin >= end)        return;    int left = begin;    int right = end;    int key = a[left];    while(left < right)    {        while(left < right && a[right] >= key)        {            right--;        }         a[left] = a[right];                while(left < right && a[left] <= key)        {            left++;        }        a[right] = a[left];    }    int meeti = left;    a[meeti] = key;    QuickSort2(a, begin, meeti - 1);    QuickSort2(a, meeti + 1, end);}

 c. 前后指针法:

//三数取中;int GetMidIndex(int* a, int left, int right){    int mid = left + (right - left) / 2;    if(a[mid] > a[left])    {        if(a[mid] < a[right])            return mid;        else if(a[left] > a[right])            return left;        else            return right;    }}void QuickSort3(int* a, int begin, int end){    if(begin >= end)        return;    int minIndex = GetMidIndex(a, begin, end);    Swap(&a[begin], &a[minIndex]);    int prev = begin;    int cur = begin + 1;    int keyi = begin;    while(cur <= end)    {        if(a[cur] < a[keyi] && ++prev != cur)        {            Swap(&a[prev], &a[cur]);        }        cur++;    }    int meeti = prev;    Swap(&a[keyi], &a[meeti]);    QuickSort3(a, begin, meeti-1);    QuickSort3(a, meeti + 1, end);}

1.5 归并排序:

        归并排序是采用分治的方法, 将数据对半分开, 使用额外的空间进行收集对半开的数组之间的比较大小的数据. 时间复杂度是O(NlogN);稳定性: 不稳定.

void _MergeSort(int* a, int left, int right, int* tmp){    if(left >= right)        return;        int mid = left + (right - left) / 2;    _MergeSort(a, left, mid, tmp);    _MergeSort(a, mid+1, right, tmp);    int begin1 = left, end1 = mid;    int begin2 = mid + 1, end2 = right;    int i = left;    while(begin1 <= end1 && begin2 <= end2)    {        if(a[begin1] < a[begin2])            tmp[i++] = a[begin1++];        else            tmp[i++] = a[begin2++];    }    while(begin1 <= end1)        tmp[i++] = a[begin1++];        while(begin2 <= end2)        tmp[i++] = a[begin2++];        for(int j = left; j <= right; j++)        a[j] = tmp[j];}void MergeSort(int* a, int n){    int* tmp = (int*)malloc(sizeof(int) * n);    if(tmp == nullptr)    {        printf("malloc fail\n");        exit(-1);    }    _MergeSort(a, 0, n - 1, tmp);    free(tmp);}

 1.6 计数排序:

        采用计数每个元素出现的次数, 以及最小值和最大值记录, 利用额外空间记录每个元素出现次数, 然后再将原来数组进行额外数组的替换.

void CountSort(int* a, int n){    int min = a[0];    int max = a[0];    for(int i = 0; i < n; i++)    {        if(a[i] < min)            min = a[i];        if(a[i] > max)            max = a[i];    }    int range = max - min + 1;    int* count = (int*)calloc(range, sizeof(int));    if(count == nullptr)    {        printf("malloc fail!");        exit(-1);    }    for(int i = 0; i < n; i++)    {        count[a[i] - min]++;    }    int i = 0;    for(int j = 0; j < range; j++)    {        while(count[j]--)        {            a[i++] = j + min;        }    }    free(count);}

2. 并查集:

2.1 概念:

        由于不同元素但是又属于某种集合的数据, 存储使用到并查集合. 元素属于某种集合是按照某种规则来分类的. 需要查询某个元素, 需要找到对应集合去寻找.

        下标对应的就是集合编号, 里面的值对应这个元素属于哪个集合里的. 如果值为负数代表这个集合|拥有的元素数目|-1.

 2.2 并查集实现:

(1) 并查集结构:

        就是采用数组即可.

private:    vector<int> _ufs;

(2) 初始化并查集:

        刚开始每个元素都是-1, 为根结点.

//初始化并查集:刚开始都是-1.    UnionFindSet(int n)        :_ufs(n, -1)    {}

(3) 查找元素的集合结点:

        遍历到负数的结点就是集合结点. 返回下标即可.

//查找元素所在集合:    int FindRoot(int x)    {        int parent = x;        //遍历到值为负数就是根结点.        while(_ufs[parent] >= 0)        {            //不停迭代下标查询.            parent = _ufs[parent];        }        return parent;    } //递归方法查找;    int _FindRoot(int x)    {        return _ufs[x] < 0 ? x : _FindRoot(_ufs[x]);    }

(4) 检查两个元素是否在一个集合:

        只要检查两个结点是否是同一个集合结点即可.

//判断两个元素是否在同一个集合中.    bool InSameSet(int x1, int x2)    {        //检查两个元素根结点是否同一个即可.        return FindRoot(x1)  == FindRoot(x2);     }

(5) 两个结点合并:

        首先找到两个元素结点的集合结点, 如果在一个集合里面就不用插入了, 不是的话, 将parent1作为元素个数大的集合, parent2进行合并到parent1里面. 然后改变parent1值的个数以及parent2集合的新集合结点.

//合并两个元素所在集合.    bool UnionSet(int x1, int x2)    {        int parent1 = FindRoot(x1); int parent2 = FindRoot(x2);        if(parent1 == parent2)            return false;                if(_ufs[parent1] > _ufs[parent2])        {            swap(parent1, parent2);        }        _ufs[parent1] += _ufs[parent2];        _ufs[parent2] = parent1;        return true;    }

(6) 计算集合个数:

//查询集合里面的个数:    int GetNum()    {        int count = 0;        for(const int& val : _ufs)        {            if(val < 0)                count++;        }        return count;    }

(7) 压缩路径:

        在查找数据的时候就进行压缩路径, 找到该元素的集合结点, 以及它的父结点, 然后进行将这个结点一条路的元素都直接插入到集合结点里面. 而且一般使用于数据量比较大的时候.

//查找元素所在集合:    //在查找集合结点的时候进行压缩.    //+压缩路径:    int FindRoot(int x)    {        int root = x;        //遍历到值为负数就是根结点.        while(_ufs[root] >= 0)        {            //不停迭代下标查询.            root = _ufs[root];        }        while(_ufs[x] >= 0)        {            int parent = _ufs[x];            _ufs[x] = root;            x = parent;        }        return root;    }//递归方法查找 + 压缩;    int _FindRoot(int x)    {        //return _ufs[x] < 0 ? x : _FindRoot(_ufs[x]);        int parent = x;        if(_ufs[x] >= 0)        {            parent = _FindRoot(_ufs[x]);            _ufs[x] = parent;        }    }

(8) 元素编号和用户输入问题:

        用户一般不会输入数字编号, 可能会输入关键词, 这时候模板函数解决. 以及使用关键词和集合进行互相关联的方法, 就可以解决了.

#include <iostream>#include <string>#include <vector>#include <utility>#include <unordered_map>using namespace std;template<class T>class UnionFindSet{public:    //初始化并查集:刚开始都是-1.    UnionFindSet(const vector<T>& v)        :_ufs(v.size(), -1)    {        for (int i = 0; i < v.size(); i++)        {            _indexMap[v[i]] = i;        }    }    //查找元素所在集合:    //在查找集合结点的时候进行压缩.    //+压缩路径:    int FindRoot(const T& x)    {        int root = _indexMap[x];        //遍历到值为负数就是根结点.        while (_ufs[root] >= 0)        {            //不停迭代下标查询.            root = _ufs[root];        }        //一般数据量少不需要压缩.        // while(_ufs[x] >= 0)        // {        //     int parent = _ufs[x];        //     _ufs[x] = root;        //     x = parent;        // }        return root;    }    //递归方法查找 + 压缩;    // int _FindRoot(int x)    // {    //     //return _ufs[x] < 0 ? x : _FindRoot(_ufs[x]);    //     int parent = x;    //     if(_ufs[x] >= 0)    //     {    //         parent = _FindRoot(_ufs[x]);    //         _ufs[x] = parent;    //     }    // }    //判断两个元素是否在同一个集合中.    bool InSameSet(const T& x1, const T& x2)    {        //检查两个元素根结点是否同一个即可.        return FindRoot(x1) == FindRoot(x2);    }    //合并两个元素所在集合.    bool UnionSet(const T& x1, const T& x2)    {        int parent1 = FindRoot(x1); int parent2 = FindRoot(x2);        if (parent1 == parent2)            return false;        if (_ufs[parent1] > _ufs[parent2])        {            swap(parent1, parent2);        }        _ufs[parent1] += _ufs[parent2];        _ufs[parent2] = parent1;        return true;    }    //查询集合里面的个数:    int GetNum()    {        int count = 0;        for (const int& val : _ufs)        {            if (val < 0)                count++;        }        return count;    }private:    vector<int> _ufs;    //原来标记数据T的处于哪个集合里面.    unordered_map<T, int> _indexMap;};int main() {    vector<string> v = { "张三", "李四", "王五", "赵六", "田七", "周八", "吴九" };    UnionFindSet<string> ufs(v);    cout << ufs.GetNum() << endl; //7    ufs.UnionSet("张三", "李四");    ufs.UnionSet("王五", "赵六");    cout << ufs.GetNum() << endl; //5    ufs.UnionSet("张三", "赵六");    cout << ufs.GetNum() << endl; //4    return 0;}

3. 图

3.1 概念:

        由顶点的集合与顶点之间的关系数据结构,  G = (V， E); V就是顶点集合, E是边的集合.

图分为有向图和无向图, 边是有方向的就是有向图.

概念:

       (1) 完全图: 无向完全图: 任意两个顶点之间有且只要一条边,  那么n个顶点就一共有

n*(n-1)/2; 有向完全图: 任意两个顶点之间有且仅有方向相反的边, n个顶点就是n*(n-1)条边.

       (2) 领接顶点: 一条边的两个相关连的顶点. 

       (3) 顶点的度: 与顶点相连的边的个数. 包含有入度(指向顶点的边)和出度(指出顶点的边).

       (4) 路径: 从顶点i到顶点j的一组边的集合.

       (5) 路径的长度: 不带权重的就是边的个数, 带权重就是边的权重的总和.

       (6) 简单路径和回路: 路径的结点都不会重复就是简单路径, 回路就是第一个顶点和最后一个结点重合就是回路.

       (8) 子图: 顶点和边包含于原图:

        (9) 连通图: 在无向图中任意一个结点都是相连的.

        (10) 强连通图: 在有向图中, 如果顶点i到顶点j有一条路径, 那么j到i也有.

        (11) 生成树: 连通图的最小连接子图. n个顶点那么就有n-1条边.

 3.2 图的结构:

        图由于只要描述顶点以及顶点之间的边即可, 保持顶点用数组即可, 但是边就需要临界矩阵了.

 3.3 邻接矩阵:

        表示两个顶点是否相连, 用0/1表示的. 邻接矩阵是二维数组. 先用一个一维数组进行保存顶点, 然后用二维数组进行保存边. 可以发现无向图的邻接矩阵是对称边界线的. 但是有向图就是不一定是对称的. 如果边有权重就用权重代替, 没有就是无穷代表.

 3.4 邻接矩阵实现:

(1) 邻接矩阵结构:

        使用_vertexs数组填写顶点的集合, V代表结点的关键词(没有具体类型使用到模板),  _vIndexMap填写的是顶点映射的下标(方便进行边关系的处理), _matrix就是一个二维的邻接矩阵(0/1表示关系).

namespace Matrix{    //V是记录结点关键词, W是记录结点关系, 邻接矩阵边初始都是最大值. Direction标志有向无向.    template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>    class Graph    {    private:        vector<V> _vertexs;//顶点集合;        unordered_map<V, int> _vIndexMap; //顶点映射的下标;        vector<vector<W>> _matrix; //邻界矩阵.    };}

(2) 初始化:

        _vertexs初始化将传递来的顶点信息进行插入, _matrix是矩阵的大小的初始化. 以及_vIndexMap将顶点进行对应映射.

Graph(const V* vertexs, int n)            //初始化顶点集合以及邻接矩阵.            :_vertexs(vertexs, vertexs + n)            ,_matrix(n, vector<int>(n, MAX_W))        {            //建立顶点映射.s            for(int i = 0; i < n; i++)            {                _vIndexMap[vertexs[i]] = i;            }        }

(3) 获取顶点下标:

        顶点的对应关系都是存储在_vIndexMap里面使用顶点关键词进行查询即可找到对应下标. 如果没有就是不存在这个结点.

int getVertexIndex(const V& v)        {            auto iter = _vIndexMap.find(v);            if(iter != _vIndexMap.end())            {                return iter->second;            }            else            {                throw invalid_argument("不存在的结点");                return -1;            }        }

(4) 连接顶点:

        首先要获得两个顶点的下标, 然后将这两个下标在_matrix邻接表中填写对应权重即可.

//src和dest进行连接.        void addEdge(const V& src, const V& dest, const W& weight)        {            //先获取两个顶点的下标.            int srci = getVertexIndex(src);            int desti = getVertexIndex(dest);            if(Direction == false)            {                _matrix[desti][srci] = weight;            }        }

(5) 打印:

        首先打印顶点以及对应的下标信息, 其次就是打印邻接表_matrix的数据, 没有连接的用*表示, 连接打印其中权重.

void print()        {            //记录结点数:            int n = _vertexs.size();            //先打印结点关键词对应映射关系:            for(int i = 0; i < n; i++)            {                cout << "[" << i "]->" << _vertexs[i] << endl;            }            cout << endl;            cout << " ";            for(int i = 0; i < 0; i++)            {                printf("%4d", i);            }            cout << endl;            for(int i = 0; i < n; i++)            {                cout << i << " ";                for(int j = 0; j < n; j++)                {                    //如果没有顶点相连接.打印*                    if(_matrix[i][j] == MAX_W)                    {                        printf("%4c", '*');                    }                    else                    {                        //打印顶点之间的权重.                        printf("%4d", _matrix[i][j]);                    }                }                cout << endl;            }            cout << endl;        }

(6) 邻接矩阵的优缺点:

        邻接矩阵可以很清楚看到两个顶点的连接情况, 但是不好统计一个顶的路径. 而且在边比较少的情况还有点浪费空间.

 3.5 邻接表:

        使用数组表示顶点集合, 链表表示边.

 3.6 邻接表实现:

(1) 结构:

        实现每个边需要存放目标顶点下标, 以及权重还有下个顶点指针. 图中包含顶点信息, 顶点映射, 以及邻接表(就是将顶点下标, 权重, 下一个顶点指针的指针数组).

namespace LinkTable{    template<class W>    struct Edge    {        //int _srci; //源顶点下标;        int _desti;//目标顶点下标.        W _weight; //边权重;        Edge<W>* _next; // 连接指针;        Edge(int desti, const W& weight)            :_desti(desti)            ,_weight(weight)            ,_next(nullptr)        {}};    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>    class Graph    {        typedef Edge<W> Edge;    private:        vector<V> _vertexs;        unordered_map<V, int> _vIndexMap;        vector<Edge*> _LinkTable;    };} 

 (2) 初始化:

        将顶点数据进行拷贝以及初始化邻接表, 以及对应顶点映射关系.

Graph(const V* vertexs, int n)            :_vertexs(vertexs, vertexs + n)            ,_LinkTable(n, nullptr)        {            for(int i = 0; i < n; i++)            {                _vIndexMap[vertexs[i]] = i;            }        }

(3) 找到顶点的下标:

        和邻接矩阵查找方式一样.

int getVertexIndex(const V &v)        {            auto iter = _vIndexMap.find(v);            if (iter != _vIndexMap.end())            {                return iter->second;            }            else            {                throw invalid_argument("不存在的结点");                return -1;            }        }

(4) 顶点连接:

        首先找到两个顶点的下标, new一个新结点, 这个邻接表对应srci对应下标赋值给下标, 以及也要给邻接表挂结点. 如果是无向图还需要将目标顶点进行挂在对应邻接表中.

int addEdge(const V& src, const V& dest, const W& weight)        {            int srci = getVertexIndex(src);            int desti = getVertexIndex(dest);            Edge* sdEdge = new Edge(desti, weight);            sdEdge->_next = _LinkTable[srci];            _LinkTable[srci] = sdEdge;            if(Direction == false)            {                Edge* dsEdge = new Edge(srci, weight);                dsEdge->_next = _LinkTable[desti];                _LinkTable[desti] = dsEdge;            }        }

(5) 打印:

        先打印顶点下标和顶点, 然后取出邻接表的元素进行结点的遍历查询打印.

void print()        {            int n = _vertexs.size();            for (int i = 0; i < n; i++)            {                cout << "[" << i << "]->" << _vertexs[i];                cout << endl;            }            cout << endl << endl;            for (int i = 0; i < n; i++)            {                Edge* cur = _LinkTable[i];                cout << "[" << i << ":" << _vertexs[i] << "]->";                while (cur)                {                    //先打印目标顶点下标, 目标顶点, 还有权重.                     cout << "[" << cur->_desti << ":" << _vertexs[cur->_desti] << ":" << cur->_weight << "]->";                    cur = cur->_next;                }                cout << "nullptr";                cout << endl;            }        }

 3.7 图的遍历:

(1) 广度优先遍历:

        根据图的一层层进行遍历查询.

        先找到对应顶点的下标, 创建队列, 和数组标记遍历的顶点, 然后遍历顶点队列, 如果邻接矩阵相连并且没有遍历过就进行查询.

void bfs(const V& src)        {            //先找到对应的下标;            int srci = getVertexIndex(src);            queue<int> q;            //原来标记是否遍历过的顶点.            vector<bool> visited(_vertexs.size(), false);            q.push(srci);            visited[srci] = true;            while(!q.empty())            {                int front = q.front();                q.pop();                cout << _vertexs[front] << " ";                for(int i = 0; i < _vertexs.size(); i++)                {                    //判断相连并且没有遍历过.                    if(_matrix[front][i] != MAX_W && visited[i] == false)                    {                        q.push(i);                        visited[i] = true;                    }                }                cout << endl;            }        }

 (2) 深度优先遍历:

        

void _dfs(int srci, vector<bool>& visited)        {            cout << _vertexs[srci] << " ";            visited[srci] = true;            for(int i = 0; i < _vertexs.size(); i++)            {                if(_matrix[srci][i] != MAX_W && visited[i]== false)                {                    _dfs(i, visited);                }            }        }        void dfs(const V& src)        {            int srci = getVertexIndex(src);            vector<bool> visited(_vertexs.size(), false);            _dfs(srci, visited);            cout << endl;        }

3.8 最小生成树:

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

(1) Kruskal算法（克鲁斯卡尔算法)

        使用贪心算法, 先选择最短的路径进行连接顶点, 然后也要判断不能成环.

        记录边使用Edge来记录源顶点和目的顶点, 然后就是使用优先级队列将所有边插入, 进行建立小堆. 还要借助并查集进行检查是否为环, 首先两个边不在同一个集合, 其次将边顶点进行合并, 增加最小生成树的边, 以及最后是否选择边为n-1来判断可以成最小生成树不.

struct Edge        {            int _srci;            int _desti;            W _weight;            Edge(int srci, int desti, const W& weight)                :_srci(srci)                ,_desti(desti)                ,_weight(weight)            {}            bool operator>(const Edge& edge) const            {                return _weight > edge._weight;            }        };        //强制生成默认构造;        Graph() = default;        //最小生成树, 最后返回权重.        W Kruskal(Graph<V, W, MAX_W, Direction>& minTree)        {            int n = _vertexs.size();            //设置最小生成树的顶点集合;            minTree._vertexs = _vertexs;            //设置最小生成树的顶点映射;            minTree._vIndexMap = _vIndexMap;            //设置最小生成树邻接矩阵的大小.            minTree._matrix.resize(n, vector<W>(n, MAX_W));            priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;            //将所有边放到优先级队列中;            for(int i = 0; i < n; i++)            {                //只用遍历一般矩阵, 因为无向图的对称.                for(int j = 0; j < i; j++)                {                    if(_matrix[i][j] != MAX_W)                    {                        minHeap.push(Edge(i, j, _matrix[i][j]));                    }                }            }            n个顶点的并查集;            UnionFindSet ufs(n);            int count = 0;//选择边的个数;            W totalWeight = W();//总权重;            while(!minHeap.empty() && count < n-1)            {                //取出优先级队列的最小的边;                Edge minEdge = minHeap.top();                minHeap.pop();                int srci = minEdge._srci;                int desti = minEdge._desti;                W weight = minEdge._weight;                //两个边不属于一个集合.                if(!ufs.InSameSet(srci, desti))                {                    minTree.addEdge(srci, desti, weight);                    //合并两个顶点.                    ufs.UnionSet(srci, desti);                    count++;                    totalWeight += weight;                    cout << "选边: " << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;                }                else                {                    cout << "成环: " << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;                }            }            if(count == n - 1)            {                cout << "构建最小生成树成功" << endl;                return totalWeight;            }            else            {                cout << "无法构成最小生成树" << endl;                return W();            }        }

 (2) Prim算法（普里姆算法）

        先选顶点在进行贪心遍历.

        首先设置最小生成树的顶点集合, 顶点映射, 邻接矩阵. 找到开始start顶点的下标, 使用forest进行记录顶点使用情况, 优先级队列minheap进行记录边的使用, 将所有边插入minHeap; 遍历优先级队列的边, 以及将顶点srci和desti进行连接, 标志一下这个位置以及选过了,, 接着就是判断是否进行使用n-1条边.

W Prim(Graph<V, W, MAX_W, Direction>& minTree, const V& start)        {            int n = _vertexs.size();            //设置最小生成树的顶点集合;            minTree._vertexs = _vertexs;            //设置最小生成树的顶点映射;            minTree._vIndexMap = _vIndexMap;            //设置最小生成树邻接矩阵的大小.            minTree._matrix.resize(n, vector<W>(n, MAX_W));            int starti = getVertexIndex(start);            vector<bool> forest(n, false);            forest[starti] = true;            priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;            for(int i = 0; i < n; i++)            {                if(_matrix[starti][i] != MAX_W)                {                    minHeap.push(Edge(starti, i, _matrix[starti][i]));                }            }            int count = 0;            W totalWeight = W();            while(!minHeap.empty() && count < n - 1)            {                Edge minEdge = minEdge.top();                minHeap.pop();                int srci = minEdge._srci, desti = minEdge._desti;                W weight = minEdge._weight;                if(forest[desti] == false)                {                    for(int i = 0; i < n; i++)                    {                        if(_matrix[desti][i] != MAX_W && forest[i] == false)                        {                            minHeap.push(Edge(desti, i, _matrix[desti][i]));                        }                    }                    minTree._addEdge(srci, desti, weight);                    forest[desti] = true;                    totalWeight += weight;                    cout << "选边: " << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;                }                else                {                    cout << "成环" << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;                }            }            if(count == n - 1)            {                cout << "构建最小生成树成功" << endl;                return totalWeight;            }            else            {                cout << "无法构建最小生成树" << endl;                return W();            }        }

3.9 最短路径:

(1) Dijkstra算法（迪杰斯特拉算法）

void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)        {            int n = _vertexs.size();            int srci = getVertexIndex(src);            //各个顶点权重初始化;            dist.resize(n, MAX_W);            //顶点的前驱初始值.            parentPath.resize(n, -1);            dist[srci] = W();//源顶点权重设置;            vector<bool> S(n, false);//使用过顶点数组;            for(int i = 0; i < n; i++)            {                //最小权重;                W minW = MAX_W;                //最小权重的顶点;                int u = -1;                for(int j = 0; j < n; j++)                {                    //顶点没有使用过并且它的权重小于最小权重;                    if(S[j] == false && dist[j] < minW)                    {                        //改变最小权重和最小权重的结点;                        minW = dist[j];                        u = j;                    }                }                S[u] = true;                //对连接出去的顶点进行松弛更新;                for(int b = 0; v < n; v++)                {                    //如果u顶点到v顶点相连, 并且v顶点没有使用过, 其次就是最小权重数组dist的u顶点+权重u到v小于最小权重dist的v顶点;                    //就改变dist的v顶点的最小权重, 并且建立一下上一个顶点.                    if(S[v] == false && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v])                    {                        dist[v] = dist[u] + _matrix[u][v];                        parentPath[v] = u;                    }                }            }        }        void printShortPath(const V& src, const vector<W>& dist, const vector<int>& parentPath)        {            int n = _vertexs.size();            int srci = getVertexIndex(src);            for(int i = 0; i < n; i++)            {                vector<int> path;                int cur = i;                //cur从结点开始向前遍历找上一个顶点.                while(cur != -1)                {                    path.push_back(cur);                    cur = parentPath[cur];                }                revese(path.begin(), path.end());                //打印顶点元素, 以及路径的权重.                for(int j = 0; j < path.size(); j++)                {                    cout << _vertexs[path[j]] << "->";                }                cout << "路径的权重: " << dist[i] << " " <<endl;            }        }

(2) Bellman-Ford算法（贝尔曼福特算法）

        先获得src顶点的下标, 将权重数组dist以及前结点数组parentpath进行初始化. 如果顶点i与顶点i和j之间的权重之和小于dist[i,j]就更新权重数组.以及前结点数组. 如果继续更新还可以找到最小路径就是负权重, 无法进行计算最小路径.

void BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)        {            int n = _vertexs.size();            int srci = getVertexIndex(src);            dist.resize(n, MAX_W);            parentPath.resize(n, -1);            dist[srci] = W();            for(int k = 0; k < n - 1; k++)            {                bool update = false;                for(int i = 0; i < n; i++)                {                    for(int j = 0; j < n; j++)                    {                        if(_matrix[i][j] != MAX_W && dist[i] != MAX_W && dist[i] + _matrix[i][j] < dist[j])                        {                            dist[j] = dist[i] + _matrix[i][j];                            parentPath[j] = i;                            update = true;                        }                    }                }                if(update == false)                {                    break;                }            }            //如果n-1轮还可以更新就是带有负权重.            for(int i = 0; i < n; i++)            {                for(int j = 0; j < n; j++)                {                    if(_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])                    {                        //带负权重无法计算出最小路径.                        return false;                    }                }            }            return true;        }

(3) Floyd-Warshall算法（弗洛伊德算法）

        vvDist进行顶点i到顶点j的二维数组, vvparentPath记录前一个顶点. 首先将顶点相连的权重全部插入vvDist里面, 其次就是当i==j就是顶点到自己的. 然后如果顶点i到顶点k以及顶点k到顶点j的权重小于顶点i到j就进行更新vvDist以及vvparentPath.

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvparentPath)        {            int n = _vertexs.size();            vvDist.resize(n, vector<W>(n, MAX_W));            vvparentPath.resize(n, vector<int>(n, -1));            for(int i = 0; i < n; i++)            {                for(int j = 0; j < n; j++)                {                    if(_matrix[i][j] != MAX_W)                    {                        vvDist[i][j] = _matrix[i][j];                        vvparentPath[i][j] = i;                    }                    if(i == j)                    {                        vvDist[i][j] = W();                    }                }            }            for(int k = 0; k < n; k++)            {                for(int i = 0; i < n; i++)                {                    for(int j = 0; j < n; j++)                    {                        if(vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W                         && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])                        {                            vvDist[i][j]= vvDist[i][k] + vvDist[k][j];                            vvparentPath[i][j] = vvparentPath[k][j];                        }                    }                }            }        }