【数据结构-图】万能构图模板

前言

图的存储表示方式多种多样，实现方式也各不相同，那么，现将要介绍一种万能构图法。

存储结构

点，边，图，三种类，不论是那种图无向图也好有向图也好，都可以用这种统一的结构来表示。

//存储结构----------------------------class Edge;//声明//一个节点信息有：值，出度，入读，下一个节点，指向下一个节点的边class Node {public:int value;int in;//入度int out;//出度vector<Node*> nexts;//该点的终端节点集（即以该点发出指向的点集）vector<Edge*> edges;//属于“我”的边，即以此节点为起点（发出）的边Node(int v) :value(v), in(0), out(0) {}//构造函数};class Edge {//边的信息有:权重，起点，终点public:int weight;//权重Node* from;//边的起点Node* to;//边的终点Edge(int w,Node* from,Node* to):weight(w),from(from),to(to){}//构造函数};//图的信息有：点集,nodes节点编号和其节点信息映射，边信息集class Graph {public:map<int, Node*> nodes;//点集set<Edge*> edges;//边集Graph() {}~Graph() {//析构//释放空间for (auto& kv : nodes) {if (kv.second) {delete(kv.second);kv.second = nullptr;}}for (auto v : edges) {if (v) {delete(v);}}}};

createGraph

无论题目给什么图信息，都可以提炼出来三个信息，起点，权重，终点。如果题目是无向图，那一条无向边，可以看成两条有向边，依然可以用上图结构，如果图中的边没有权重，可以将权重设置为一默认值。

//N*3的矩阵，[from节点上的值，weight,to节点上的值]//流程：遍历矩阵，一次提出起点，终点，权重信息，向图点集中添加起点终点信息，提炼出起点Node 、终点Node信息 ,new边Edge,//对起点终点进行信息完善，将new出的边加入到边集中Graph* createGraph(vector<vector<int>> matrix) {Graph* graph = new Graph;//建图int len = matrix.size();for (int i = 0; i < len; ++i) {int from = matrix[i][0];int weight = matrix[i][1];//提炼出 边的权重，起点，终点int to = matrix[i][2];if (graph->nodes.find(from) == graph->nodes.end()) {//map中找是否有起点的信息,无则添加graph->nodes[from] = new Node(from);}if (graph->nodes.find(to) == graph->nodes.end()) {//map中找是否有终点的信息,无则添加graph->nodes[to] = new Node(to);}Node* fromNode = graph->nodes[from];//找出边的起点节点和终点节点Node* toNode = graph->nodes[to];Edge* newEdge = new Edge(weight, fromNode, toNode);//构造边fromNode->nexts.push_back(toNode);//给起点节点的next添加终点节点fromNode->out++;//出度++；toNode->in++;//终点节点入度++fromNode->edges.push_back(newEdge);//给起点添加边信息graph->edges.insert(newEdge);//边信息添加到边集}return graph;}

总结

上述createGraph函数中的参数matrix,往往需要你自己手动构造提炼出来。有了这么一套万能的构图法后，之后无论遇到什么图，都可以用此通一表示，而根据此图结构又可以打造各种自己图算法模板。

读书笔记网