• 数据结构-难点突破（C++实现图的基本操作（邻接矩阵，邻接表，十字链表法储存代码））

    关于图的数据结构，我曾经自己学过一部分，图论专栏，但是学习本就是重复的过程，这里打算系统的学习一下图。第一步当然是图的储存和基本操作的实现。

    要用C++实现图的基本操作

    1. Adjacent(x，y)：判断图是否存在边或(x,y)
    2. InsertVertex(x)：在图中插入节点x
    3. DeleteVertex(x)：在图中删除节点x
    4. AddEdge(x，y)：添加边或(x，y)
    5. RemoveEdge(x，y)：删除边或(x，y)
    6. SetEdgeValue(x，y，z)：设置边的权值（添加边）
    7. GetNeighborsPoint(x)：获取图中顶点x的邻节点
    8. PrintGraph()：打印保存图的邻接矩阵

    文章目录

    1. 邻接矩阵存储图，并实现基本操作

    简单的来讲就是二维数组保存图基本信息：

    每一行代表一个顶点，依次从 a 到 b ，每一列也是如此。比如 _matrix[0][1] = weight ，表示 a 和 b 之间有边存在；而 arcs[0][2] = MAX，说明 V1 和 V3 之间没有边。

    对于有向图，这个二位数组不是对称的，对于无向图，这个二维数组就是对称的，可以仅仅保留一半。

    //邻接矩阵法存储图结构

#include 
#include 
#include 
#include 
#include 

// v:图顶点保存的值。w:边的权值 max:最大权值，代表无穷。flag=true代表有向图。否则就是无向图
template <class v, class w, w max = INT_MAX, bool flag = false>
class graph
{
private:
    std::vector<v> _verPoint;            //顶点集合
    std::map<v, int> _indexMap;          //顶点与下标的映射
    std::vector<std::vector<w>> _matrix; //邻接矩阵

    int _getPosPoint(const v &point)
    {
        if (_indexMap.find(point) != _indexMap.end())
        {
            return _indexMap[point];
        }
        else
        {
            std::cout << point << " not found" << std::endl;
            return -1;
        }
    }

public:
    //根据数组来开辟邻接矩阵
    graph(const std::vector<v> &src)
    {
        _verPoint.resize(src.size());
        for (int i = 0; i < src.size(); i++)
        {
            _verPoint[i] = src[i];
            _indexMap[src[i]] = i;
        }

        //初始化邻接矩阵
        _matrix.resize(src.size());
        for (int i = 0; i < src.size(); i++)
        {
            _matrix[i].resize(src.size(), max);
        }
    }

    //添加边的关系,输入两个点，以及这两个点连线边的权值。
    void AddEdge(const v &pointA, const v &pointB, const w &weight)
    {
        //获取这个顶点在邻接矩阵中的下标
        int posA = _getPosPoint(pointA);
        int posB = _getPosPoint(pointB);
        _matrix[posA][posB] = weight;
        if (!flag)
        {
            //无向图,邻接矩阵对称
            _matrix[posB][posA] = weight;
        }
    }

    //打印邻接矩阵
    void PrintGraph()
    {
        //打印顶点对应的坐标
        typename std::map<v, int>::iterator pos = _indexMap.begin();
        while (pos != _indexMap.end())
        {
            std::cout << pos->first << ":" << pos->second << std::endl;
            pos++;
        }
        std::cout << std::endl;

        //打印边
        printf("  ");
        for (int i = 0; i < _verPoint.size(); i++)
        {
            std::cout << _verPoint[i] << " ";
        }
        printf("\n");

        for (int i = 0; i < _matrix.size(); i++)
        {
            std::cout << _verPoint[i] << " ";
            for (int j = 0; j < _matrix[i].size(); j++)
            {
                if (_matrix[i][j] == max)
                {
                    //这条边不通
                    printf("∞ ");
                }
                else
                {
                    std::cout << _matrix[i][j] << " ";
                }
            }
            printf("\n");
        }
        printf("\n");
    }

    //判断图是否存在边或(x,y)
    bool Adjacent(const v &x, const v &y)
    {
        return _matrix[_indexMap[x]][_indexMap[y]] != max;
    }

    //列出图中x相邻的边
    std::vector<v> GetNeighborsPoint(const v &x)
    {
        int index = _indexMap[x];
        assert(index >= 0);
        std::vector<v> result;
        for (int i = 0; i < _matrix[index].size(); i++)
        {
            if (_matrix[index][i] != max)
            {
                // std::cout << x << "->" << _verPoint[i] << std::endl;
                result.push_back(_verPoint[i]);
            }
        }
        return result;
    }

    // 在图中插入节点x
    void InsertVertex(const v &x)
    {
        _verPoint.push_back(x);
        _indexMap[x] = _verPoint.size() - 1;
        for (int i = 0; i < _matrix.size(); i++)
        {
            _matrix[i].push_back(max);
        }
        std::vector<w> newLine(_verPoint.size(), max);
        _matrix.push_back(newLine);
    }

    //在图中删除节点x
    void DeleteVertex(const v &x)
    {
        int pos = _indexMap[x];
        assert(pos >= 0);
        _verPoint.erase(_verPoint.begin() + pos);
        _indexMap.erase(x);
        _matrix.erase(_matrix.begin() + pos);
        for (int i = 0; i < _matrix.size(); i++)
        {
            _matrix[i].erase(_matrix[i].begin() + pos);
        }
    }

    //删除边或(x，y)
    void RemoveEdge(const v &x, const v &y)
    {
        //假定x,y存在，减少代码量
        _matrix[_indexMap[x]][_indexMap[y]] = max;
        if (!flag)
        {
            //无向图
            _matrix[_indexMap[y]][_indexMap[x]] = max;
        }
    }

    //设置边的权值（添加边）
    void SetEdgeValue(const v &x, const v &y, const w &z)
    {
        //假定x,y存在，减少代码量
        _matrix[_indexMap[x]][_indexMap[y]] = z;
        if (!flag)
        {
            //无向图
            _matrix[_indexMap[y]][_indexMap[x]] = z;
        }
    }
};

    • 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
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177

    测试代码：

    #include "matrix.h"

using namespace std;

int main(int argc, char const *argv[])
{
    vector<char> vet = {'a', 'b', 'c', 'd'};
    graph<char, int> graph(vet);
    graph.AddEdge('a', 'd', 1);
    graph.AddEdge('c', 'b', 1);
    graph.AddEdge('c', 'd', 1);
    graph.PrintGraph();
    std::cout << graph.Adjacent('a', 'd') << " " << graph.Adjacent('a', 'b') << endl;
    vector<char> ret = graph.GetNeighborsPoint('c');
    for (int i = 0; i < ret.size(); i++)
    {
        std::cout << 'c' << "->" << ret[i] << std::endl;
    }
    graph.InsertVertex('e');
    graph.PrintGraph();

    // graph.DeleteVertex('a');
    // graph.PrintGraph();
    graph.RemoveEdge('a', 'd');
    graph.PrintGraph();
    return 0;
}


    • 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

    在这里插入图片描述

    2. 邻接表存储图

    邻接表存储图的核心思想是：将图中的所有顶点存储到顺序表中（也可以是链表）。
    同时为各个顶点配备一个单链表，用来存储和当前顶点有直接关联的边或者弧（边的一端是该顶点或者弧的弧尾是该顶点）。

    eg：
    在这里插入图片描述
    邻接表的优点：

    1. 适合保存稀疏的边关系。
    2. 适合查找一个顶点连接出的边

    不足：

    1. 不适合确定两个顶点是否相连，判断权值。

    链表节点内的值中保存边执向节点在数组的下标，和这条权值数据。

    #include 
#include 
#include 
#include 

template <class w>
struct Edge
{
    int dstPos = -1;
    w weight; //权值
    Edge<w> *next;
    Edge(int _dstPos, const w &_weight) : dstPos(_dstPos), weight(_weight), next(nullptr) {}
};

// v:节点的值，w节点的权值 flag==false为无向图
template <class v, class w, bool flag = false>
class linkTable
{
    typedef Edge<w> Edge;

private:
    std::vector<Edge *> _matrix;          //邻接表
    std::unordered_map<v, int> _indexMap; //保存图节点对应邻接表数组的下标
    std::vector<v> _points;               //顶点集合

    int _getPointPos(const v &point)
    {
        typename std::unordered_map<v, int>::iterator pos = _indexMap.find(point);
        if (pos == _indexMap.end())
            return -1; //没找到
        return pos->second;
    }

public:
    linkTable(const std::vector<v> &src)
    {
        int size = src.size();
        assert(size > 0);
        _points.resize(size);
        for (int i = 0; i < size; i++)
        {
            _points[i] = src[i];
            _indexMap[src[i]] = i;
        }
        _matrix.resize(size, nullptr);
    }

    //添加边的关系
    void AddEdge(const v &src, const v &dst, const w &weight)
    {
        int posSrc = _getPointPos(src);
        int posDst = _getPointPos(dst);
        assert(posSrc >= 0 && posSrc >= 0);

        //构建Edge，头插到数组上
        Edge *edge = new Edge(posDst, weight);
        edge->next = _matrix[posSrc];
        _matrix[posSrc] = edge;

        if (!flag)
        {
            //无向图,两条边都要构建
            edge = new Edge(posSrc, weight);
            edge->next = _matrix[posDst];
            _matrix[posDst] = edge;
        }
    }

    //打印邻接表信息
    void PrintGraph()
    {
        for (int i = 0; i < _matrix.size(); i++)
        {
            Edge *edge = _matrix[i];
            while (edge != nullptr)
            {
                std::cout << _points[i] << "->";
                std::cout << _points[edge->dstPos] << "权值:" << edge->weight << std::endl;
                edge = edge->next;
            }
            std::cout << "--------------------------------" << std::endl;
        }
    }
};

    • 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
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    测试代码：

    #include "linkTable.h"

int main(int argc, char const *argv[])
{
    std::cout << "无向图" << std::endl;
    linkTable<char, int> graph({'a', 'b', 'c', 'd'});
    graph.AddEdge('a', 'd', 4);
    graph.AddEdge('c', 'd', 2);
    graph.AddEdge('c', 'b', 4);
    graph.PrintGraph();

    std::cout << "+++++++++++++++++++++++++++++++++" << std::endl;
    std::cout << "有向图" << std::endl;
    linkTable<char, int, true> graph2({'a', 'b', 'c', 'd'});
    graph2.AddEdge('a', 'd', 4);
    graph2.AddEdge('c', 'd', 2);
    graph2.AddEdge('c', 'b', 4);
    graph2.PrintGraph();
    return 0;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    在这里插入图片描述

    3. 十字链表法储存（储存有向图）

    用邻接表存储有向图（网），可以快速计算出某个顶点的出度，但计算入度的效率不高。反之，用逆邻接表存储有向图（网），可以快速计算出某个顶点的入度，但计算出度的效率不高。

    为了解决快速计算有向图（网）中某个顶点的入度和出度，这里采用十字链表这种种存储结构。

    十字链表（Orthogonal List）是一种专门存储有向图（网）的结构，它的核心思想是：
    将图中的所有顶点存储到顺序表（也可以是链表）中，同时为每个顶点配备两个链表，一个链表记录以当前顶点为弧头的弧，另一个链表记录以当前顶点为弧尾的弧。

    eg：
    在这里插入图片描述

    顺序表节点数据定义：图片来源
    在这里插入图片描述

    这份代码处理了有向图和无向图的情况，需要记住十字链表法一般储存有向图.

    具体的代码处理：如果是无向图，重新递归调用AddEdge函数只不过原节点和目的节点参数调换即可。

    #include 
#include 
#include 
#include 

struct Data
{
    int tailpos = -1; //弧尾在顺序表的位置下标
    int headpos = -1; //弧头在顺序表的位置下标
    Data *head_link = nullptr;
    Data *tail_link = nullptr;
    // head_lik指向下一个以当前顶点为弧头的弧结点；(指入这个节点)
    // tail_link 指向下一个以当前顶点为弧尾的弧结点；(指出这个节点)

    int weight; //保存弧权值
};

struct TableNode
{
    char val = 0; //图节点的值
    Data *in = nullptr;
    Data *out = nullptr;
    //指向以该顶点为弧头(指入这个节点)和弧尾(指出这个节点)的链表首个结点
};

class FrontTailList
{
private:
    std::vector<TableNode> _verPoint;        //顶点集合
    std::unordered_map<char, int> _indexMap; //顶点与下标的映射
    std::vector<std::vector<int>> _matrix;   //邻接矩阵

    bool flag = false; //标记这个图是有向还是无向,false默认无向
    bool isDel = false;

    int _getPosPoint(const char point)
    {
        if (_indexMap.find(point) != _indexMap.end())
        {
            return _indexMap[point];
        }
        else
        {
            std::cout << point << " not found" << std::endl;
            return -1;
        }
    }

public:
    FrontTailList(const std::vector<char> &src, bool flag)
    {
        this->flag = flag;
        _verPoint.resize(src.size());
        _matrix.resize(src.size());
        for (int i = 0; i < src.size(); i++)
        {
            _indexMap[src[i]] = i;
            _matrix[i].resize(src.size(), INT_MAX);
        }
    }

    void AddEdge(const char pointA, const char pointB, int weight)
    {
        int indexA = _getPosPoint(pointA);
        int indexB = _getPosPoint(pointB);
        assert(indexA >= 0 && indexB >= 0);
        _matrix[indexA][indexB] = weight;

        Data *link = new Data;
        link->headpos = indexB;
        link->tailpos = indexA;
        link->weight = weight;
        //采用头插法插入新的节点

        // indexB的入度节点就是pointA这个节点，这里选择头插法插入。
        link->head_link = _verPoint[indexB].in;
        link->tail_link = _verPoint[indexA].out;

        _verPoint[indexB].in = link;
        _verPoint[indexA].out = link;

        if (!flag && !isDel)
        {
            //无向图
            isDel = true; //记录这次的无向图，两条边已经处理过了。
            AddEdge(pointB, pointA, weight);
        }
        //退出条件后说明这条边添加完毕，为了下次添加边的时候还可以解决无向图问题，这里将isDel恢复原状
        isDel = false;
    }

    //打印邻接矩阵
    void PrintGraph()
    {
        //打印顶点对应的坐标
        typename std::unordered_map<char, int>::iterator pos = _indexMap.begin();
        while (pos != _indexMap.end())
        {
            std::cout << pos->first << ":" << pos->second << std::endl;
            pos++;
        }
        std::cout << std::endl;

        //打印边
        printf("  ");
        for (int i = 0; i < _verPoint.size(); i++)
        {
            std::cout << _verPoint[i].val << " ";
        }
        printf("\n");

        for (int i = 0; i < _matrix.size(); i++)
        {
            std::cout << _verPoint[i].val << " ";
            for (int j = 0; j < _matrix[i].size(); j++)
            {
                if (_matrix[i][j] == INT_MAX)
                {
                    //这条边不通
                    printf("∞ ");
                }
                else
                {
                    std::cout << _matrix[i][j] << " ";
                }
            }
            printf("\n");
        }
        printf("\n");
    }

    //计算某个点的出度和入度
    int InDegree(const char point)
    {
        int pos = _getPosPoint(point);
        if (pos < 0)
        {
            std::cout << "图中没有这个节点" << std::endl;
            return -1;
        }
        int ret = 0;
        Data *node = _verPoint[pos].in;
        while (node != nullptr)
        {
            ret += 1;
            node = node->head_link;
        }
        return ret;
    }

    int OutDegree(const char point)
    {
        int pos = _getPosPoint(point);
        if (pos < 0)
        {
            std::cout << "图中没有这个节点" << std::endl;
            return -1;
        }
        int ret = 0;

        Data *node = _verPoint[pos].out;
        while (node != nullptr)
        {
            ret += 1;
            node = node->tail_link;
        }
        return ret;
    }
};


    • 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
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    #include "FrontTailList.h"

using namespace std;

int main(int argc, char const *argv[])
{
    FrontTailList graph({'a', 'b', 'c', 'd'}, false);
    graph.AddEdge('a', 'd', 1);
    graph.AddEdge('c', 'd', 2);
    graph.AddEdge('c', 'b', 3);

    graph.PrintGraph();
    cout << graph.InDegree('d') << endl;
    cout << graph.OutDegree('d') << endl;

    FrontTailList graph2({'a', 'b', 'c', 'd'}, true);
    graph2.AddEdge('a', 'd', 1);
    graph2.AddEdge('c', 'd', 2);
    graph2.AddEdge('c', 'b', 3);

    graph2.PrintGraph();

    cout << graph2.InDegree('d') << endl;
    cout << graph2.OutDegree('d') << endl;

    return 0;
}


    • 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

    在这里插入图片描述

    4. 邻接多重表（储存无向图）

    图片来源

    邻接多重表是一种专门存储无向图（网）的结构。

    邻接多重表存储无向图的方式，可以看作是邻接表和十字链表的结合体。

    具体来讲就是：将图中的所有顶点存储到顺序表（也可以用链表）中，同时为每个顶点配备一个链表，链表的各个结点中存储的都是和当前顶点有直接关联的边。
    在这里插入图片描述

    在邻接多重表中，每一条边是同过节点来表示的。
    这个节点有6个成员
    在这里插入图片描述

    1. mark：标记域，标记这条边是否被搜索过，例如遍历无向图中的所有边，借助 mark 标志域可以避免重复访问同一条边；
2. ivex，jvex：为该边依附的两个顶点在循序表的位置
3. ilink：指向下一条依附于ivex的边
4. jink：指向下一条依附于jvex的边
5. info：存储当前边的其它信息，可以用 info 指针域存储边的权值。

    • 1
    • 2
    • 3
    • 4
    • 5

    无向图中的每一个节点中包含两部分1. 这个节点的值 2. 保存边关系的结构体

    #include 
#include 
#include 
#include 

typedef char ValueType;

struct Data
{
    bool mark = false;     // 标记域，标记这条边是否被搜索过
    size_t ivex = -1;      // 为该边依附的两个顶点在循序表的位置
    Data *ilink = nullptr; // 指向下一条依附于ivex的边
    size_t jvex = -1;
    Data *jlink = nullptr;
    int info = INT_MAX; // 权值，默认为无穷
};

struct MatrixNode
{
    ValueType value = ValueType(); // 初始化节点类型int和char型为0,其他类型调用其默认构造函数
    Data *list = nullptr;
};

class AdjacencyMultilist
{
private:
    std::vector<MatrixNode> _matrix;
    // 图节点和在_matrix下标的映射
    std::unordered_map<ValueType, size_t> _hashMap;

    size_t _getValeTypePos(const ValueType &dst)
    {
        auto pos = _hashMap.find(dst);
        if (pos == _hashMap.end())
        {
            std::cout << "dst point not found" << std::endl;
            assert(pos != _hashMap.end());
        }
        return pos->second;
    }

public:
    AdjacencyMultilist(const std::vector<ValueType> &vet)
    {
        _matrix.resize(vet.size()); // 先开辟内存
        for (int i = 0; i < vet.size(); i++)
        {
            _matrix[i].value = vet[i];
            _hashMap[vet[i]] = i;
        }
    }

    /**
     * @brief 向无向图中添加边关系
     *
     * @param src 边起点
     * @param dst 边终点
     * @param info 边权值
     */
    void AddEdge(const ValueType &src, const ValueType &dst, int info)
    {
        // 找到这两个点在_matrix顺序表的位置
        size_t posSrc = _getValeTypePos(src);
        size_t posDst = _getValeTypePos(dst);

        // 创建边节点
        Data *edge = new Data;
        edge->ivex = posSrc;
        edge->jvex = posDst;
        edge->info = info;

        // 头插法插入
        edge->ilink = _matrix[posSrc].list;
        _matrix[posSrc].list = edge;

        edge->jlink = _matrix[posDst].list;
        _matrix[posDst].list = edge;
    }

    // /*
    //  * 删除(src,dst) 或者(dst,src)
    //  * 实现思路：
    //  * 1、从 src 顶点的链表出发，找到目标结点的直接前驱结点；
    //  * 2、从 dst 顶点的链表触发，找到目标结点的直接前驱结点；
    //  * 3、将目标结点从 src 顶点的链表中摘除，从 dst 顶点的链表中摘除
    //  * 4、删除目标结点
    //  */

    // void DelEdge(const ValueType &src, const ValueType &dst)
    // {
    //     size_t posSrc = _getValeTypePos(src);
    //     size_t posDst = _getValeTypePos(dst);
    //     Data *srcPrev = nullptr;
    //     Data *dstPrev = nullptr;
    //     Data *node = _matrix[posSrc].list;
    //     // 找src点的直接前驱
    //     while (node != nullptr && ((node->ivex == posSrc && node->jvex == posDst) || (node->ivex == posDst && node->jvex == posSrc)))
    //     {
    //         // 因为邻接多重表只能保存有向图，删除边，这两个方向都需要删除
    //         srcPrev = node;
    //         if (node->ivex == posSrc)
    //         {
    //             node = node->ilink;
    //         }
    //         else
    //         {
    //             node = node->jlink;
    //         }
    //     }
    //     // 找dst点前驱
    //     Data *jnode = _matrix[posDst].list;
    //     while (jnode != nullptr && ((jnode->ivex == posSrc && jnode->jvex == posDst) || (jnode->ivex == posDst && jnode->jvex == posSrc)))
    //     {
    //         dstPrev = jnode;
    //         if (jnode->ivex == posDst)
    //         {
    //             jnode = jnode->ilink;
    //         }
    //         else
    //         {
    //             jnode = jnode->jlink;
    //         }
    //     }

    //     if (node == nullptr || jnode == nullptr)
    //     {
    //         std::cout << "edge not exit" << std::endl;
    //         return;
    //     }

    //     // 将目标结点从 src 顶点的链表中摘除，从 dst 顶点的链表中摘除
    //     if (srcPrev == nullptr)
    //     {
    //         // 头删
    //         if (_matrix[posSrc].list->ivex == posSrc)
    //         {
    //             _matrix[posSrc].list = node->ilink;
    //         }
    //         else
    //         {
    //             _matrix[posSrc].list = node->ilink;
    //         }
    //     }
    //     else
    //     {
    //         if (srcPrev->ivex == posSrc)
    //         {
    //             if (node->ivex == posSrc)
    //             {
    //                 srcPrev->ilink = node->ilink;
    //             }
    //             else
    //             {
    //                 srcPrev->ilink = node->jlink;
    //             }
    //         }
    //         else
    //         {
    //             if (node->ivex == posSrc)
    //             {
    //                 srcPrev->jlink = node->ilink;
    //             }
    //             else
    //             {
    //                 srcPrev->jlink = node->jlink;
    //             }
    //         }
    //     }

    //     // 从 dst 顶点的链表中摘除
    //     if (dstPrev == nullptr)
    //     {
    //         // 头删
    //         if (_matrix[posDst].list->ivex == posDst)
    //         {
    //             _matrix[posDst].list = node->ilink;
    //         }
    //         else
    //         {
    //             _matrix[posDst].list = node->ilink;
    //         }
    //     }
    //     else
    //     {
    //         if (dstPrev->ivex == posDst)
    //         {
    //             if (jnode->ivex == posDst)
    //             {
    //                 dstPrev->ilink = node->ilink;
    //             }
    //             else
    //             {
    //                 dstPrev->ilink = node->jlink;
    //             }
    //         }
    //         else
    //         {
    //             if (jnode->ivex == posDst)
    //             {
    //                 dstPrev->jlink = jnode->ilink;
    //             }
    //             else
    //             {
    //                 dstPrev->jlink = jnode->jlink;
    //             }
    //         }
    //     }

    //     // 删除边
    //     delete node;
    //     _matrix[posSrc].list = nullptr;
    // }

    // 输出邻接多重表中包含的所有边
    void PrintGraph()
    {
        for (int i = 0; i < _matrix.size(); i++)
        {
            // 如果当前结点存在，且标志域为 0
            Data *p = _matrix[i].list;
            while (p && (p->mark == false))
            {
                // 输出该边，并将标志域置为 1
                printf("%c-%c 权值%d ", _matrix[p->ivex].value, _matrix[p->jvex].value, p->info);
                p->mark = true;
                if (p->ivex == i)
                {
                    p = p->ilink;
                }
                else
                {
                    p = p->jlink;
                }
            }
        }
        printf("\n");
    }
};

    • 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
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    #include "./AdjacencyMultilist.h"

int main(int argc, char const *argv[])
{
    AdjacencyMultilist graph({'a', 'b', 'c', 'd'});

    graph.AddEdge('a', 'b', 10);
    graph.AddEdge('c', 'b', 1);
    graph.AddEdge('c', 'd', 5);
    graph.PrintGraph();

    // graph.DelEdge('c', 'b');
    // graph.PrintGraph();
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    在这里插入图片描述

  • 相关阅读:
    Redis的持久化机制
    企业落地数字化转型，战略规划应该放在首要位置
    WEB攻防-ASP安全-ASP后门植入连接
    【分享一个实用帖，带视频】教你用RPA高效进行软件测试
    理解和熟悉递归中的尝试
    微信视频号打造带货闭环：主播叫苦连天
    数据库可视化工具分享 （DBeaver）
    计算机管理服务中找不到mysql的服务
    拓扑排序算法
    Pandas+Matplotlib 数据分析
  • 原文地址：https://blog.csdn.net/dodamce/article/details/128041066