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

要用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. 邻接矩阵存储图，并实现基本操作
• 2. 邻接表存储图
• 3. 十字链表法储存

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

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

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

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

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

测试代码：

#include "matrix.h"using namespace std;int main(int argc, char const *argv[])
{vector vet = {'a', 'b', 'c', 'd'};graph 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 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;
}

2. 邻接表存储图

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

eg：

邻接表的优点：

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

不足：

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

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

#include 
#include 
#include 
#include template 
struct Edge
{int dstPos = -1;w weight; //权值Edge *next;Edge(int _dstPos, const w &_weight) : dstPos(_dstPos), weight(_weight), next(nullptr) {}
};// v:节点的值，w节点的权值 flag==false为无向图
template 
class linkTable
{typedef Edge Edge;private:std::vector _matrix;          //邻接表std::unordered_map _indexMap; //保存图节点对应邻接表数组的下标std::vector _points;               //顶点集合int _getPointPos(const v &point){typename std::unordered_map::iterator pos = _indexMap.find(point);if (pos == _indexMap.end())return -1; //没找到return pos->second;}public:linkTable(const std::vector &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;}}
};

测试代码：

#include "linkTable.h"int main(int argc, char const *argv[])
{std::cout << "无向图" << std::endl;linkTable 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 graph2({'a', 'b', 'c', 'd'});graph2.AddEdge('a', 'd', 4);graph2.AddEdge('c', 'd', 2);graph2.AddEdge('c', 'b', 4);graph2.PrintGraph();return 0;
}

3. 十字链表法储存

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

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

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

eg：

顺序表节点数据定义：图片来源

#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 _verPoint;        //顶点集合std::unordered_map _indexMap; //顶点与下标的映射std::vector> _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 &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::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;}
};

#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;
}