邻接多重表是一种比较重要的无向简单图存储结构鉴于无向图在数据结构课程中的重要性邻接表多重操作实现必须要予以解决。图论及其算法在编译原理中具有很重要的地位图着色的寄存器分配就要用到无向简单图所以自己尝试实现一下邻接多重表的操作。一开始很天真的以为邻接多重表的实现难度和十字链表应该相差不大十字链表能够实现邻接多重表应该也不成问题但实际开始动手后才发现情况并非如此邻接多重表实现比十字链表更为复杂。不得不承认自己实在太笨问题没考虑全面就急匆匆敲代码结果运行后不是发现这里没考虑到就是那里存在错误于是就反反复复修改编译修改编译真是被折磨死了。图结构及其算法确实是数据结构中最难的部分之一我已经深有体会了。用了整整两天时间总算正确实现了邻接多重表的操作实现了添加边删除边删除顶点复制合并销毁添加顶点这些重要的API其他接口应该没有那么重要需要的话以后还可以添加。C代码清单#include pch.h #include iostream #include vector #include set using namespace std; template typename V, typename E class Graph //无向简单图类存储结构为多重邻接表 { friend vectorvectorint *convertToAdjaMatrix(Graphsize_t, size_t *undigraph); public: struct VertexNode; struct EdgeNode //边节点类型 { E *edge_data_field nullptr; //边节点数据域 typename vectorVertexNode *::size_type left 0; //边一端对应顶点 typename vectorVertexNode *::size_type right 0; //边另一端对应顶点 EdgeNode *same_left_ptr nullptr; //指向一端仍为left的下一个边节点的指针 EdgeNode *same_right_ptr nullptr; //指向另一端仍为right的下一个边节点的指针 EdgeNode() default; EdgeNode(typename vectorVertexNode *::size_type l, typename vectorVertexNode *::size_type r, E *e) :left(l), right(r), edge_data_field(e) {} ~EdgeNode() { delete edge_data_field; } }; struct VertexNode //顶点节点 { V *vertex_data_field nullptr; //顶点数据域 typename vectorVertexNode *::size_type number 0; //顶点编号 EdgeNode *first_ptr nullptr; //指向和该顶点关联的第一条边的指针 VertexNode *seilring nullptr; //指向当前顶点表示存在自环 E *Edgeseilring nullptr; //自环边 VertexNode() default; VertexNode(typename vectorVertexNode *::size_type n, V *v) :number(n), vertex_data_field(v) {} ~VertexNode() { delete vertex_data_field; delete Edgeseilring; } }; Graph() default; Graph(typename vectorVertexNode *::size_type n) :set_of_vertex(n, nullptr) {} virtual ~Graph(); //释放多重邻接表并销毁图 GraphV, E *copy(); //拷贝当前无向图并返回指向副本的指针 typename vectortypename VertexNode *::size_type addVertex(V *vertex); //添加顶点,vertex为顶点数据域 bool addEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right, E *edge); //添加边(left, right),edge为边数据域 void deleteVertex(typename vectorVertexNode *::size_type vertex); //删除顶点vertex bool deleteEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right); //删除边(left, right) GraphV, E *merge(GraphV, E Bemerged, bool copyOrNot); //将Bemerged和当前无向图合并,copyOrNottrue拷贝当前图返回合并后得到的新的无向图的指针,false直接合并至当前图返回空指针 typename vectorVertexNode *::size_type getVertexNum() { return set_of_vertex.size(); } //获取无向图中顶点数目 protected: vectorVertexNode * set_of_vertex; //无向图顶点集 }; template typename V, typename E typename vectortypename GraphV, E::VertexNode *::size_type GraphV, E::addVertex(V *vertex) { set_of_vertex.push_back(new VertexNode(set_of_vertex.size(), vertex)); return set_of_vertex.size() - 1; } template typename V, typename E bool GraphV, E::addEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right, E *edge) //从left和right顶点节点开始检索插入位置并插入该过程会保持和left或right关联的边节点的另一端顶点的编号的有序性(从小到大) { if (left set_of_vertex.size() || right set_of_vertex.size()) { throw new out_of_range(无效的顶点参数\\n); } if (left right) { set_of_vertex[left]-seilring set_of_vertex[left]; set_of_vertex[left]-Edgeseilring new E(*edge); return true; } EdgeNode *start set_of_vertex[left]-first_ptr; EdgeNode *pre nullptr; if (start nullptr) { set_of_vertex[left]-first_ptr new EdgeNode(left, right, edge); if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr set_of_vertex[left]-first_ptr; return true; } } else { for (; start ! nullptr; ) { if ((start-left left ? start-right : start-left) right) return false; else if ((start-left left ? start-right : start-left) right) { pre start; if (start-left left) { start start-same_left_ptr; } else { start start-same_right_ptr; } } else { if (pre nullptr) { pre set_of_vertex[left]-first_ptr; set_of_vertex[left]-first_ptr new EdgeNode(left, right, edge); set_of_vertex[left]-first_ptr-same_left_ptr pre; if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr set_of_vertex[left]-first_ptr; return true; } pre set_of_vertex[left]-first_ptr; } else { if (pre-left left) { pre-same_left_ptr new EdgeNode(left, right, edge); pre-same_left_ptr-same_left_ptr start; if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_left_ptr; return true; } pre pre-same_left_ptr; } else { pre-same_right_ptr new EdgeNode(left, right, edge); pre-same_right_ptr-same_left_ptr start; if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_right_ptr; return true; } pre pre-same_right_ptr; } } break; } } if (start nullptr) { if (pre-left left) { if (pre-right right) return false; pre-same_left_ptr new EdgeNode(left, right, edge); if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_left_ptr; return true; } pre pre-same_left_ptr; } else { if (pre-left right) return false; pre-same_right_ptr new EdgeNode(left, right, edge); if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_right_ptr; return true; } pre pre-same_right_ptr; } } } if (pre nullptr) { pre set_of_vertex[left]-first_ptr; } EdgeNode *p nullptr; for (EdgeNode *start set_of_vertex[right]-first_ptr; start ! nullptr; ) { if ((start-right right ? start-left : start-right) left) { p start; if (start-right right) { start start-same_right_ptr; } else { start start-same_left_ptr; } } else { if (p nullptr) { p set_of_vertex[right]-first_ptr; set_of_vertex[right]-first_ptr pre; pre-same_right_ptr p; } else { if (p-right right) { p-same_right_ptr pre; } else { p-same_left_ptr pre; } pre-same_right_ptr start; } return true; } } if (p-right right) { p-same_right_ptr pre; } else { p-same_left_ptr pre; } return true; } template typename V, typename E GraphV, E::~Graph() //删除算法较为简洁原因是和顶点关联的所有边另一端的顶点编号保持有序,这样我们只需从小到大考察每个顶点,如果和顶点关联的边全部删除,first_ptr指针为空算法会自动跳过否则依次分离出和顶点关联的每一条边从该边关联的非当前顶点的另一 { //顶点处对分离出的边节点进行摘链(根据删除算法的执行顺序被摘链的边节点一定是和另一顶点关联的边链表中的第一个节点),然后释放分离出的边节点所有顶点处理完后销毁set_of_vertex for (typename vectorVertexNode *::size_type run 0; run set_of_vertex.size(); run) { EdgeNode *ptr nullptr; while (set_of_vertex[run]-first_ptr ! nullptr) { ptr set_of_vertex[run]-first_ptr; if (ptr-left run) { set_of_vertex[run]-first_ptr ptr-same_left_ptr; set_of_vertex[ptr-right]-first_ptr ptr-same_right_ptr; } else { set_of_vertex[run]-first_ptr ptr-same_right_ptr; set_of_vertex[ptr-left]-first_ptr ptr-same_left_ptr; } delete ptr; } } while (set_of_vertex.empty() false) { delete set_of_vertex.back(); set_of_vertex.pop_back(); } } template typename V, typename E GraphV, E *GraphV, E::copy() //依次考察原图每一个顶点对每一个顶点依次考察关联的每一边节点如果该边节点副本已在尚未拷贝完成的图副本中则将边节点副本链接至图副本对应顶点副本的边链表的尾部否则创建新节点(为当前边节点副本)链接至图副本对应顶点副本的边链表的尾部 { //同时搜索图副本中已部分形成的通过和新边节点关联的另一端顶点(非原图中当前遍历到的顶点)对应的链接指针链接形成的边链表的第一个边节点由该边节点循链找到部分形成的边链表尾部将新节点链接至尾部即可 GraphV, E *temp new GraphV, E(set_of_vertex.size()); for (typename vectorVertexNode *::size_type run 0; run set_of_vertex.size(); run) { temp-set_of_vertex[run] new VertexNode(set_of_vertex[run]-number, new V(*(set_of_vertex[run]-vertex_data_field))); if (set_of_vertex[run]-seilring ! nullptr) { temp-set_of_vertex[run]-seilring temp-set_of_vertex[run]; temp-set_of_vertex[run]-Edgeseilring new E(*(set_of_vertex[run]-Edgeseilring)); } if (set_of_vertex[run]-first_ptr nullptr) continue; EdgeNode *p nullptr; for (EdgeNode *start set_of_vertex[run]-first_ptr; start ! nullptr; ) { if ((start-left run ? start-right : start-left) run) { EdgeNode *q nullptr; if (start-left run) { q temp-set_of_vertex[start-right]-first_ptr; for (; q ! nullptr; ) { if (q-left start-right) { if (q-right run) break; q q-same_left_ptr; } else { if (q-left run) break; q q-same_right_ptr; } } } else { q temp-set_of_vertex[start-left]-first_ptr; for (; q ! nullptr; ) { if (q-left start-left) { if (q-right run) break; q q-same_left_ptr; } else { if (q-left run) break; q q-same_right_ptr; } } } if (p nullptr) { p temp-set_of_vertex[run]-first_ptr q; } else { if (p-left run) { p p-same_left_ptr q; } else { p p-same_right_ptr q; } } } else { if (p nullptr) { p temp-set_of_vertex[run]-first_ptr new EdgeNode(start-left, start-right, new E(*(start-edge_data_field))); } else { if (p-left run) { p p-same_left_ptr new EdgeNode(start-left, start-right, new E(*(start-edge_data_field))); } else { p p-same_right_ptr new EdgeNode(start-left, start-right, new E(*(start-edge_data_field))); } } if (start-left run) { EdgeNode *m nullptr; typename vectorVertexNode *::size_type i 0; for ( ; i run; i) { for (m temp-set_of_vertex[i]-first_ptr; m ! nullptr;) { if (m-left i) { if (m-right start-right) break; m m-same_left_ptr; } else { if (m-left start-right) break; m m-same_right_ptr; } } if (m ! nullptr) break; } if (i ! run) { while (true) { if (m-right start-right) { if (m-same_right_ptr nullptr) break; m m-same_right_ptr; } else { if (m-same_left_ptr nullptr) break; m m-same_left_ptr; } } if (m-right start-right) { m-same_right_ptr p; } else { m-same_left_ptr p; } } } else { EdgeNode *m nullptr; typename vectorVertexNode *::size_type i 0; for (; i run; i) { for (m temp-set_of_vertex[i]-first_ptr; m ! nullptr;) { if (m-left i) { if (m-right start-left) break; m m-same_left_ptr; } else { if (m-left start-left) break; m m-same_right_ptr; } } if (m ! nullptr) break; } if (i ! run) { while (true) { if (m-right start-left) { if (m-same_right_ptr nullptr) break; m m-same_right_ptr; } else { if (m-same_left_ptr nullptr) break; m m-same_left_ptr; } } if (m-right start-left) { m-same_right_ptr p; } else { m-same_left_ptr p; } } } } if (start-left run) { start start-same_left_ptr; } else { start start-same_right_ptr; } } } return temp; } template typename V, typename E bool GraphV, E::deleteEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right) //从顶点left,right处搜索边节点摘链并释放边节点 { if (left set_of_vertex.size() || right set_of_vertex.size()) { throw new out_of_range(无效的顶点参数\\n); } if (left right) { set_of_vertex[left]-seilring nullptr; delete set_of_vertex[left]-Edgeseilring; set_of_vertex[left]-Edgeseilring nullptr; return true; } if (set_of_vertex[left]-first_ptr nullptr) return false; EdgeNode *q nullptr; EdgeNode *p set_of_vertex[left]-first_ptr; for (; p ! nullptr; ) { if (p-left left) { if (p-right right) { break; } else if (p-right right) { q p; p p-same_left_ptr; } else { return false; } } else { if (p-left right) { break; } else if (p-left right) { q p; p p-same_right_ptr; } else { return false; } } } if (p nullptr) { return false; } else { if (q nullptr) { if (p-left left) { set_of_vertex[left]-first_ptr p-same_left_ptr; } else { set_of_vertex[left]-first_ptr p-same_right_ptr; } } else { if (q-left left p-left left) { q-same_left_ptr p-same_left_ptr; } else if (q-left ! left) { if (p-left ! left) { q-same_right_ptr p-same_right_ptr; } else { q-same_right_ptr p-same_left_ptr; } } else { q-same_left_ptr p-same_right_ptr; } } } EdgeNode *q2 nullptr; while (true) { if (q2 nullptr) { if (set_of_vertex[right]-first_ptr-left left || set_of_vertex[right]-first_ptr-right left) break; q2 set_of_vertex[right]-first_ptr; continue; } else { if (q2-right right) { if (q2-same_right_ptr-left left || q2-same_right_ptr-right left) break; q2 q2-same_right_ptr; } else { if (q2-same_left_ptr-left left || q2-same_left_ptr-right left) break; q2 q2-same_left_ptr; } } } if (q2 nullptr) { if (p-left left) { set_of_vertex[right]-first_ptr p-same_right_ptr; } else { set_of_vertex[right]-first_ptr p-same_left_ptr; } } else { if (q2-left right p-left left) { q2-same_left_ptr p-same_left_ptr; } else if (q2-left ! right) { if (p-left ! left) { q2-same_right_ptr p-same_right_ptr; } else { q2-same_right_ptr p-same_left_ptr; } } else { q2-same_left_ptr p-same_right_ptr; } } delete p; } template typename V, typename E void GraphV, E::deleteVertex(typename vectorVertexNode *::size_type vertex) //分离出和vertex关联的每一边节点,从该边节点另一端顶点(和vertex相对应)出搜索边节点摘链并释放边节点 { //随后从set_of_vertex中删去vertex并调整图中顶点编号和边节点中顶点编号 if (vertex set_of_vertex.size()) { throw new out_of_range(无效的顶点参数\\n); } EdgeNode *ptr nullptr; while (set_of_vertex[vertex]-first_ptr ! nullptr) { ptr set_of_vertex[vertex]-first_ptr; if (ptr-left vertex) { set_of_vertex[vertex]-first_ptr ptr-same_left_ptr; EdgeNode *q2 nullptr; while (true) { if (q2 nullptr) { if (set_of_vertex[ptr-right]-first_ptr-left vertex || set_of_vertex[ptr-right]-first_ptr-right vertex) break; q2 set_of_vertex[ptr-right]-first_ptr; continue; } else { if (q2-right ptr-right) { if (q2-same_right_ptr-left vertex || q2-same_right_ptr-right vertex) break; q2 q2-same_right_ptr; } else { if (q2-same_left_ptr-left vertex || q2-same_left_ptr-right vertex) break; q2 q2-same_left_ptr; } } } if (q2 nullptr) { set_of_vertex[ptr-right]-first_ptr ptr-same_right_ptr; } else { if (q2-left ptr-right) { q2-same_left_ptr ptr-same_right_ptr; } else { q2-same_right_ptr ptr-same_right_ptr; } } } else { set_of_vertex[vertex]-first_ptr ptr-same_right_ptr; EdgeNode *q2 nullptr; while (true) { if (q2 nullptr) { if (set_of_vertex[ptr-left]-first_ptr-left vertex || set_of_vertex[ptr-left]-first_ptr-right vertex) break; q2 set_of_vertex[ptr-left]-first_ptr; continue; } else { if (q2-right ptr-left) { if (q2-same_right_ptr-left vertex || q2-same_right_ptr-right vertex) break; q2 q2-same_right_ptr; } else { if (q2-same_left_ptr-left vertex || q2-same_left_ptr-right vertex) break; q2 q2-same_left_ptr; } } } if (q2 nullptr) { set_of_vertex[ptr-left]-first_ptr ptr-same_left_ptr; } else { if (q2-left ! ptr-left) { q2-same_right_ptr ptr-same_left_ptr; } else { q2-same_left_ptr ptr-same_left_ptr; } } } delete ptr; } delete set_of_vertex[vertex]; for (typename vectorVertexNode *::size_type i vertex; i set_of_vertex.size() - 1; i) { set_of_vertex[i] set_of_vertex[i 1]; --set_of_vertex[i]-number; } set_of_vertex.pop_back(); setEdgeNode * visited; for (typename vectorVertexNode *::size_type i 0; i set_of_vertex.size(); i) { for (EdgeNode *q set_of_vertex[i]-first_ptr; q ! nullptr; ) { if (visited.find(q) visited.end()) { if (q-left vertex) { q-left q-left - 1; } if (q-right vertex) { q-right q-right - 1; } visited.insert(q); } if (q-left i) { q q-same_left_ptr; } else { q q-same_right_ptr; } } } } template typename V, typename E GraphV, E *GraphV, E::merge(GraphV, E Bemerged, bool copyOrNot) //合并函数比较简单可以参考我在LALR(1)语法分析表生成程序中对十字链表的实现 { GraphV, E *temp1 nullptr; typename vectorVertexNode *::size_type Ca1 0; if (copyOrNot) { temp1 copy(); Ca1 temp1-set_of_vertex.size(); } else { Ca1 set_of_vertex.size(); } { GraphV, E *temp2 Bemerged.copy(); for (typename vectorVertexNode *::size_type p 0; p temp2-set_of_vertex.size(); p) { if (copyOrNot) { temp1-set_of_vertex.push_back(temp2-set_of_vertex[p]); } else { set_of_vertex.push_back(temp2-set_of_vertex[p]); } } while (temp2-set_of_vertex.empty() false) { temp2-set_of_vertex.pop_back(); } delete temp2; } setEdgeNode * visited; for (typename vectorVertexNode *::size_type p Ca1; ; p) { EdgeNode *q nullptr; if (copyOrNot) { if (p temp1-set_of_vertex.size()) break; temp1-set_of_vertex[p]-number p; q temp1-set_of_vertex[p]-first_ptr; } else { if (p set_of_vertex.size()) break; set_of_vertex[p]-number p; q set_of_vertex[p]-first_ptr; } for (; q ! nullptr; ) { if (visited.find(q) visited.end()) { q-left q-left Ca1; q-right q-right Ca1; visited.insert(q); } if (q-left p) { q q-same_left_ptr; } else { q q-same_right_ptr; } } } if (copyOrNot) return temp1; else return nullptr; } Graphsize_t, size_t *convertToGraph(vectorvectorint adjacency_matrix) //由邻接矩阵构造基于邻接多重表的有向图并返回该图的指针 { vectorvectorint::size_type size adjacency_matrix.size(); Graphsize_t, size_t *temp new Graphsize_t, size_t(); for (size_t i 0; i size; i) { temp-addVertex(new size_t(i)); } for (size_t i 0; i size; i) { for (size_t j i; j size; j) { if (adjacency_matrix[i][j] 1) { temp-addEdge(i, j, new size_t(j)); } } } return temp; } vectorvectorint *convertToAdjaMatrix(Graphsize_t, size_t *undigraph) //由基于邻接多重表无向图构造邻接矩阵并返回邻接矩阵 { vectorvectorint *temp new vectorvectorint(undigraph-getVertexNum(), vectorint(undigraph-getVertexNum(), 0)); for (size_t i 0; i undigraph-set_of_vertex.size(); i) { if (undigraph-set_of_vertex[i]-seilring ! nullptr) (*temp)[i][i] 1; for (Graphsize_t, size_t::EdgeNode *p undigraph-set_of_vertex[i]-first_ptr; p ! nullptr;) { if (p-left i) { (*temp)[p-left][p-right] 1; p p-same_left_ptr; } else { (*temp)[p-right][p-left] 1; p p-same_right_ptr; } } } delete undigraph; return temp; } int main() { vectorvectorint test { {1, 0, 1, 1, 0, 1, 0}, {0, 1, 0, 1, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1}, {0, 1, 1, 0, 1, 1, 0} }; //测试用邻接矩阵 vectorvectorint *test2 convertToAdjaMatrix(convertToGraph(test)); //测试addEdge函数 for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } delete test2; /*Graphsize_t, size_t *temp convertToGraph(test); //测试copy函数 Graphsize_t, size_t *temp2 temp-copy(); vectorvectorint *test2 convertToAdjaMatrix(temp2); for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } */ /*Graphsize_t, size_t *temp convertToGraph(test); //测试deleteEdge函数 for (size_t i 0; i test.size(); i) { for (size_t j i; j test.size(); j) { if (test[i][j] 1) { cout 删除边(i, j ) endl; temp-deleteEdge(i, j); } } } vectorvectorint *test2 convertToAdjaMatrix(temp); for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } */ /*Graphsize_t, size_t *temp convertToGraph(test); //测试deleteVertex函数 size_t num temp-getVertexNum(); for (size_t i 0; i num; i) { cout 删除顶点 i endl; temp-deleteVertex(0); } vectorvectorint *test2 convertToAdjaMatrix(temp); if (test2-empty()) { cout 图为空 endl; } else { cout 错误! endl; } */ /*Graphsize_t, size_t *temp1 convertToGraph(test); //测试merge函数 Graphsize_t, size_t *temp2 convertToGraph(test); temp1-merge(*temp2, false); vectorvectorint *test2 convertToAdjaMatrix(temp1); for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } */ return 0; }2018.11.12日更新优化了deleteEdge函数第一个for循环搜索待删除边时搜索的边链表上每一个边节点的与边链表上所有边节点共同关联的顶点对应的边节点一端相对的一端的顶点的编号严格递增所以如果发现被删除边的前述一端的顶点编号夹在边链表上俩边节点前述一端的顶点编号之间或小于边链表上前述一端的顶点编号最小的边节点的顶点编号则函数直接退出没有必要继续搜索 邻接多重表 操作实现
邻接多重表是一种比较重要的无向简单图存储结构鉴于无向图在数据结构课程中的重要性邻接表多重操作实现必须要予以解决。图论及其算法在编译原理中具有很重要的地位图着色的寄存器分配就要用到无向简单图所以自己尝试实现一下邻接多重表的操作。一开始很天真的以为邻接多重表的实现难度和十字链表应该相差不大十字链表能够实现邻接多重表应该也不成问题但实际开始动手后才发现情况并非如此邻接多重表实现比十字链表更为复杂。不得不承认自己实在太笨问题没考虑全面就急匆匆敲代码结果运行后不是发现这里没考虑到就是那里存在错误于是就反反复复修改编译修改编译真是被折磨死了。图结构及其算法确实是数据结构中最难的部分之一我已经深有体会了。用了整整两天时间总算正确实现了邻接多重表的操作实现了添加边删除边删除顶点复制合并销毁添加顶点这些重要的API其他接口应该没有那么重要需要的话以后还可以添加。C代码清单#include pch.h #include iostream #include vector #include set using namespace std; template typename V, typename E class Graph //无向简单图类存储结构为多重邻接表 { friend vectorvectorint *convertToAdjaMatrix(Graphsize_t, size_t *undigraph); public: struct VertexNode; struct EdgeNode //边节点类型 { E *edge_data_field nullptr; //边节点数据域 typename vectorVertexNode *::size_type left 0; //边一端对应顶点 typename vectorVertexNode *::size_type right 0; //边另一端对应顶点 EdgeNode *same_left_ptr nullptr; //指向一端仍为left的下一个边节点的指针 EdgeNode *same_right_ptr nullptr; //指向另一端仍为right的下一个边节点的指针 EdgeNode() default; EdgeNode(typename vectorVertexNode *::size_type l, typename vectorVertexNode *::size_type r, E *e) :left(l), right(r), edge_data_field(e) {} ~EdgeNode() { delete edge_data_field; } }; struct VertexNode //顶点节点 { V *vertex_data_field nullptr; //顶点数据域 typename vectorVertexNode *::size_type number 0; //顶点编号 EdgeNode *first_ptr nullptr; //指向和该顶点关联的第一条边的指针 VertexNode *seilring nullptr; //指向当前顶点表示存在自环 E *Edgeseilring nullptr; //自环边 VertexNode() default; VertexNode(typename vectorVertexNode *::size_type n, V *v) :number(n), vertex_data_field(v) {} ~VertexNode() { delete vertex_data_field; delete Edgeseilring; } }; Graph() default; Graph(typename vectorVertexNode *::size_type n) :set_of_vertex(n, nullptr) {} virtual ~Graph(); //释放多重邻接表并销毁图 GraphV, E *copy(); //拷贝当前无向图并返回指向副本的指针 typename vectortypename VertexNode *::size_type addVertex(V *vertex); //添加顶点,vertex为顶点数据域 bool addEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right, E *edge); //添加边(left, right),edge为边数据域 void deleteVertex(typename vectorVertexNode *::size_type vertex); //删除顶点vertex bool deleteEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right); //删除边(left, right) GraphV, E *merge(GraphV, E Bemerged, bool copyOrNot); //将Bemerged和当前无向图合并,copyOrNottrue拷贝当前图返回合并后得到的新的无向图的指针,false直接合并至当前图返回空指针 typename vectorVertexNode *::size_type getVertexNum() { return set_of_vertex.size(); } //获取无向图中顶点数目 protected: vectorVertexNode * set_of_vertex; //无向图顶点集 }; template typename V, typename E typename vectortypename GraphV, E::VertexNode *::size_type GraphV, E::addVertex(V *vertex) { set_of_vertex.push_back(new VertexNode(set_of_vertex.size(), vertex)); return set_of_vertex.size() - 1; } template typename V, typename E bool GraphV, E::addEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right, E *edge) //从left和right顶点节点开始检索插入位置并插入该过程会保持和left或right关联的边节点的另一端顶点的编号的有序性(从小到大) { if (left set_of_vertex.size() || right set_of_vertex.size()) { throw new out_of_range(无效的顶点参数\\n); } if (left right) { set_of_vertex[left]-seilring set_of_vertex[left]; set_of_vertex[left]-Edgeseilring new E(*edge); return true; } EdgeNode *start set_of_vertex[left]-first_ptr; EdgeNode *pre nullptr; if (start nullptr) { set_of_vertex[left]-first_ptr new EdgeNode(left, right, edge); if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr set_of_vertex[left]-first_ptr; return true; } } else { for (; start ! nullptr; ) { if ((start-left left ? start-right : start-left) right) return false; else if ((start-left left ? start-right : start-left) right) { pre start; if (start-left left) { start start-same_left_ptr; } else { start start-same_right_ptr; } } else { if (pre nullptr) { pre set_of_vertex[left]-first_ptr; set_of_vertex[left]-first_ptr new EdgeNode(left, right, edge); set_of_vertex[left]-first_ptr-same_left_ptr pre; if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr set_of_vertex[left]-first_ptr; return true; } pre set_of_vertex[left]-first_ptr; } else { if (pre-left left) { pre-same_left_ptr new EdgeNode(left, right, edge); pre-same_left_ptr-same_left_ptr start; if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_left_ptr; return true; } pre pre-same_left_ptr; } else { pre-same_right_ptr new EdgeNode(left, right, edge); pre-same_right_ptr-same_left_ptr start; if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_right_ptr; return true; } pre pre-same_right_ptr; } } break; } } if (start nullptr) { if (pre-left left) { if (pre-right right) return false; pre-same_left_ptr new EdgeNode(left, right, edge); if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_left_ptr; return true; } pre pre-same_left_ptr; } else { if (pre-left right) return false; pre-same_right_ptr new EdgeNode(left, right, edge); if (set_of_vertex[right]-first_ptr nullptr) { set_of_vertex[right]-first_ptr pre-same_right_ptr; return true; } pre pre-same_right_ptr; } } } if (pre nullptr) { pre set_of_vertex[left]-first_ptr; } EdgeNode *p nullptr; for (EdgeNode *start set_of_vertex[right]-first_ptr; start ! nullptr; ) { if ((start-right right ? start-left : start-right) left) { p start; if (start-right right) { start start-same_right_ptr; } else { start start-same_left_ptr; } } else { if (p nullptr) { p set_of_vertex[right]-first_ptr; set_of_vertex[right]-first_ptr pre; pre-same_right_ptr p; } else { if (p-right right) { p-same_right_ptr pre; } else { p-same_left_ptr pre; } pre-same_right_ptr start; } return true; } } if (p-right right) { p-same_right_ptr pre; } else { p-same_left_ptr pre; } return true; } template typename V, typename E GraphV, E::~Graph() //删除算法较为简洁原因是和顶点关联的所有边另一端的顶点编号保持有序,这样我们只需从小到大考察每个顶点,如果和顶点关联的边全部删除,first_ptr指针为空算法会自动跳过否则依次分离出和顶点关联的每一条边从该边关联的非当前顶点的另一 { //顶点处对分离出的边节点进行摘链(根据删除算法的执行顺序被摘链的边节点一定是和另一顶点关联的边链表中的第一个节点),然后释放分离出的边节点所有顶点处理完后销毁set_of_vertex for (typename vectorVertexNode *::size_type run 0; run set_of_vertex.size(); run) { EdgeNode *ptr nullptr; while (set_of_vertex[run]-first_ptr ! nullptr) { ptr set_of_vertex[run]-first_ptr; if (ptr-left run) { set_of_vertex[run]-first_ptr ptr-same_left_ptr; set_of_vertex[ptr-right]-first_ptr ptr-same_right_ptr; } else { set_of_vertex[run]-first_ptr ptr-same_right_ptr; set_of_vertex[ptr-left]-first_ptr ptr-same_left_ptr; } delete ptr; } } while (set_of_vertex.empty() false) { delete set_of_vertex.back(); set_of_vertex.pop_back(); } } template typename V, typename E GraphV, E *GraphV, E::copy() //依次考察原图每一个顶点对每一个顶点依次考察关联的每一边节点如果该边节点副本已在尚未拷贝完成的图副本中则将边节点副本链接至图副本对应顶点副本的边链表的尾部否则创建新节点(为当前边节点副本)链接至图副本对应顶点副本的边链表的尾部 { //同时搜索图副本中已部分形成的通过和新边节点关联的另一端顶点(非原图中当前遍历到的顶点)对应的链接指针链接形成的边链表的第一个边节点由该边节点循链找到部分形成的边链表尾部将新节点链接至尾部即可 GraphV, E *temp new GraphV, E(set_of_vertex.size()); for (typename vectorVertexNode *::size_type run 0; run set_of_vertex.size(); run) { temp-set_of_vertex[run] new VertexNode(set_of_vertex[run]-number, new V(*(set_of_vertex[run]-vertex_data_field))); if (set_of_vertex[run]-seilring ! nullptr) { temp-set_of_vertex[run]-seilring temp-set_of_vertex[run]; temp-set_of_vertex[run]-Edgeseilring new E(*(set_of_vertex[run]-Edgeseilring)); } if (set_of_vertex[run]-first_ptr nullptr) continue; EdgeNode *p nullptr; for (EdgeNode *start set_of_vertex[run]-first_ptr; start ! nullptr; ) { if ((start-left run ? start-right : start-left) run) { EdgeNode *q nullptr; if (start-left run) { q temp-set_of_vertex[start-right]-first_ptr; for (; q ! nullptr; ) { if (q-left start-right) { if (q-right run) break; q q-same_left_ptr; } else { if (q-left run) break; q q-same_right_ptr; } } } else { q temp-set_of_vertex[start-left]-first_ptr; for (; q ! nullptr; ) { if (q-left start-left) { if (q-right run) break; q q-same_left_ptr; } else { if (q-left run) break; q q-same_right_ptr; } } } if (p nullptr) { p temp-set_of_vertex[run]-first_ptr q; } else { if (p-left run) { p p-same_left_ptr q; } else { p p-same_right_ptr q; } } } else { if (p nullptr) { p temp-set_of_vertex[run]-first_ptr new EdgeNode(start-left, start-right, new E(*(start-edge_data_field))); } else { if (p-left run) { p p-same_left_ptr new EdgeNode(start-left, start-right, new E(*(start-edge_data_field))); } else { p p-same_right_ptr new EdgeNode(start-left, start-right, new E(*(start-edge_data_field))); } } if (start-left run) { EdgeNode *m nullptr; typename vectorVertexNode *::size_type i 0; for ( ; i run; i) { for (m temp-set_of_vertex[i]-first_ptr; m ! nullptr;) { if (m-left i) { if (m-right start-right) break; m m-same_left_ptr; } else { if (m-left start-right) break; m m-same_right_ptr; } } if (m ! nullptr) break; } if (i ! run) { while (true) { if (m-right start-right) { if (m-same_right_ptr nullptr) break; m m-same_right_ptr; } else { if (m-same_left_ptr nullptr) break; m m-same_left_ptr; } } if (m-right start-right) { m-same_right_ptr p; } else { m-same_left_ptr p; } } } else { EdgeNode *m nullptr; typename vectorVertexNode *::size_type i 0; for (; i run; i) { for (m temp-set_of_vertex[i]-first_ptr; m ! nullptr;) { if (m-left i) { if (m-right start-left) break; m m-same_left_ptr; } else { if (m-left start-left) break; m m-same_right_ptr; } } if (m ! nullptr) break; } if (i ! run) { while (true) { if (m-right start-left) { if (m-same_right_ptr nullptr) break; m m-same_right_ptr; } else { if (m-same_left_ptr nullptr) break; m m-same_left_ptr; } } if (m-right start-left) { m-same_right_ptr p; } else { m-same_left_ptr p; } } } } if (start-left run) { start start-same_left_ptr; } else { start start-same_right_ptr; } } } return temp; } template typename V, typename E bool GraphV, E::deleteEdge(typename vectorVertexNode *::size_type left, typename vectorVertexNode *::size_type right) //从顶点left,right处搜索边节点摘链并释放边节点 { if (left set_of_vertex.size() || right set_of_vertex.size()) { throw new out_of_range(无效的顶点参数\\n); } if (left right) { set_of_vertex[left]-seilring nullptr; delete set_of_vertex[left]-Edgeseilring; set_of_vertex[left]-Edgeseilring nullptr; return true; } if (set_of_vertex[left]-first_ptr nullptr) return false; EdgeNode *q nullptr; EdgeNode *p set_of_vertex[left]-first_ptr; for (; p ! nullptr; ) { if (p-left left) { if (p-right right) { break; } else if (p-right right) { q p; p p-same_left_ptr; } else { return false; } } else { if (p-left right) { break; } else if (p-left right) { q p; p p-same_right_ptr; } else { return false; } } } if (p nullptr) { return false; } else { if (q nullptr) { if (p-left left) { set_of_vertex[left]-first_ptr p-same_left_ptr; } else { set_of_vertex[left]-first_ptr p-same_right_ptr; } } else { if (q-left left p-left left) { q-same_left_ptr p-same_left_ptr; } else if (q-left ! left) { if (p-left ! left) { q-same_right_ptr p-same_right_ptr; } else { q-same_right_ptr p-same_left_ptr; } } else { q-same_left_ptr p-same_right_ptr; } } } EdgeNode *q2 nullptr; while (true) { if (q2 nullptr) { if (set_of_vertex[right]-first_ptr-left left || set_of_vertex[right]-first_ptr-right left) break; q2 set_of_vertex[right]-first_ptr; continue; } else { if (q2-right right) { if (q2-same_right_ptr-left left || q2-same_right_ptr-right left) break; q2 q2-same_right_ptr; } else { if (q2-same_left_ptr-left left || q2-same_left_ptr-right left) break; q2 q2-same_left_ptr; } } } if (q2 nullptr) { if (p-left left) { set_of_vertex[right]-first_ptr p-same_right_ptr; } else { set_of_vertex[right]-first_ptr p-same_left_ptr; } } else { if (q2-left right p-left left) { q2-same_left_ptr p-same_left_ptr; } else if (q2-left ! right) { if (p-left ! left) { q2-same_right_ptr p-same_right_ptr; } else { q2-same_right_ptr p-same_left_ptr; } } else { q2-same_left_ptr p-same_right_ptr; } } delete p; } template typename V, typename E void GraphV, E::deleteVertex(typename vectorVertexNode *::size_type vertex) //分离出和vertex关联的每一边节点,从该边节点另一端顶点(和vertex相对应)出搜索边节点摘链并释放边节点 { //随后从set_of_vertex中删去vertex并调整图中顶点编号和边节点中顶点编号 if (vertex set_of_vertex.size()) { throw new out_of_range(无效的顶点参数\\n); } EdgeNode *ptr nullptr; while (set_of_vertex[vertex]-first_ptr ! nullptr) { ptr set_of_vertex[vertex]-first_ptr; if (ptr-left vertex) { set_of_vertex[vertex]-first_ptr ptr-same_left_ptr; EdgeNode *q2 nullptr; while (true) { if (q2 nullptr) { if (set_of_vertex[ptr-right]-first_ptr-left vertex || set_of_vertex[ptr-right]-first_ptr-right vertex) break; q2 set_of_vertex[ptr-right]-first_ptr; continue; } else { if (q2-right ptr-right) { if (q2-same_right_ptr-left vertex || q2-same_right_ptr-right vertex) break; q2 q2-same_right_ptr; } else { if (q2-same_left_ptr-left vertex || q2-same_left_ptr-right vertex) break; q2 q2-same_left_ptr; } } } if (q2 nullptr) { set_of_vertex[ptr-right]-first_ptr ptr-same_right_ptr; } else { if (q2-left ptr-right) { q2-same_left_ptr ptr-same_right_ptr; } else { q2-same_right_ptr ptr-same_right_ptr; } } } else { set_of_vertex[vertex]-first_ptr ptr-same_right_ptr; EdgeNode *q2 nullptr; while (true) { if (q2 nullptr) { if (set_of_vertex[ptr-left]-first_ptr-left vertex || set_of_vertex[ptr-left]-first_ptr-right vertex) break; q2 set_of_vertex[ptr-left]-first_ptr; continue; } else { if (q2-right ptr-left) { if (q2-same_right_ptr-left vertex || q2-same_right_ptr-right vertex) break; q2 q2-same_right_ptr; } else { if (q2-same_left_ptr-left vertex || q2-same_left_ptr-right vertex) break; q2 q2-same_left_ptr; } } } if (q2 nullptr) { set_of_vertex[ptr-left]-first_ptr ptr-same_left_ptr; } else { if (q2-left ! ptr-left) { q2-same_right_ptr ptr-same_left_ptr; } else { q2-same_left_ptr ptr-same_left_ptr; } } } delete ptr; } delete set_of_vertex[vertex]; for (typename vectorVertexNode *::size_type i vertex; i set_of_vertex.size() - 1; i) { set_of_vertex[i] set_of_vertex[i 1]; --set_of_vertex[i]-number; } set_of_vertex.pop_back(); setEdgeNode * visited; for (typename vectorVertexNode *::size_type i 0; i set_of_vertex.size(); i) { for (EdgeNode *q set_of_vertex[i]-first_ptr; q ! nullptr; ) { if (visited.find(q) visited.end()) { if (q-left vertex) { q-left q-left - 1; } if (q-right vertex) { q-right q-right - 1; } visited.insert(q); } if (q-left i) { q q-same_left_ptr; } else { q q-same_right_ptr; } } } } template typename V, typename E GraphV, E *GraphV, E::merge(GraphV, E Bemerged, bool copyOrNot) //合并函数比较简单可以参考我在LALR(1)语法分析表生成程序中对十字链表的实现 { GraphV, E *temp1 nullptr; typename vectorVertexNode *::size_type Ca1 0; if (copyOrNot) { temp1 copy(); Ca1 temp1-set_of_vertex.size(); } else { Ca1 set_of_vertex.size(); } { GraphV, E *temp2 Bemerged.copy(); for (typename vectorVertexNode *::size_type p 0; p temp2-set_of_vertex.size(); p) { if (copyOrNot) { temp1-set_of_vertex.push_back(temp2-set_of_vertex[p]); } else { set_of_vertex.push_back(temp2-set_of_vertex[p]); } } while (temp2-set_of_vertex.empty() false) { temp2-set_of_vertex.pop_back(); } delete temp2; } setEdgeNode * visited; for (typename vectorVertexNode *::size_type p Ca1; ; p) { EdgeNode *q nullptr; if (copyOrNot) { if (p temp1-set_of_vertex.size()) break; temp1-set_of_vertex[p]-number p; q temp1-set_of_vertex[p]-first_ptr; } else { if (p set_of_vertex.size()) break; set_of_vertex[p]-number p; q set_of_vertex[p]-first_ptr; } for (; q ! nullptr; ) { if (visited.find(q) visited.end()) { q-left q-left Ca1; q-right q-right Ca1; visited.insert(q); } if (q-left p) { q q-same_left_ptr; } else { q q-same_right_ptr; } } } if (copyOrNot) return temp1; else return nullptr; } Graphsize_t, size_t *convertToGraph(vectorvectorint adjacency_matrix) //由邻接矩阵构造基于邻接多重表的有向图并返回该图的指针 { vectorvectorint::size_type size adjacency_matrix.size(); Graphsize_t, size_t *temp new Graphsize_t, size_t(); for (size_t i 0; i size; i) { temp-addVertex(new size_t(i)); } for (size_t i 0; i size; i) { for (size_t j i; j size; j) { if (adjacency_matrix[i][j] 1) { temp-addEdge(i, j, new size_t(j)); } } } return temp; } vectorvectorint *convertToAdjaMatrix(Graphsize_t, size_t *undigraph) //由基于邻接多重表无向图构造邻接矩阵并返回邻接矩阵 { vectorvectorint *temp new vectorvectorint(undigraph-getVertexNum(), vectorint(undigraph-getVertexNum(), 0)); for (size_t i 0; i undigraph-set_of_vertex.size(); i) { if (undigraph-set_of_vertex[i]-seilring ! nullptr) (*temp)[i][i] 1; for (Graphsize_t, size_t::EdgeNode *p undigraph-set_of_vertex[i]-first_ptr; p ! nullptr;) { if (p-left i) { (*temp)[p-left][p-right] 1; p p-same_left_ptr; } else { (*temp)[p-right][p-left] 1; p p-same_right_ptr; } } } delete undigraph; return temp; } int main() { vectorvectorint test { {1, 0, 1, 1, 0, 1, 0}, {0, 1, 0, 1, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1}, {0, 1, 1, 0, 1, 1, 0} }; //测试用邻接矩阵 vectorvectorint *test2 convertToAdjaMatrix(convertToGraph(test)); //测试addEdge函数 for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } delete test2; /*Graphsize_t, size_t *temp convertToGraph(test); //测试copy函数 Graphsize_t, size_t *temp2 temp-copy(); vectorvectorint *test2 convertToAdjaMatrix(temp2); for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } */ /*Graphsize_t, size_t *temp convertToGraph(test); //测试deleteEdge函数 for (size_t i 0; i test.size(); i) { for (size_t j i; j test.size(); j) { if (test[i][j] 1) { cout 删除边(i, j ) endl; temp-deleteEdge(i, j); } } } vectorvectorint *test2 convertToAdjaMatrix(temp); for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } */ /*Graphsize_t, size_t *temp convertToGraph(test); //测试deleteVertex函数 size_t num temp-getVertexNum(); for (size_t i 0; i num; i) { cout 删除顶点 i endl; temp-deleteVertex(0); } vectorvectorint *test2 convertToAdjaMatrix(temp); if (test2-empty()) { cout 图为空 endl; } else { cout 错误! endl; } */ /*Graphsize_t, size_t *temp1 convertToGraph(test); //测试merge函数 Graphsize_t, size_t *temp2 convertToGraph(test); temp1-merge(*temp2, false); vectorvectorint *test2 convertToAdjaMatrix(temp1); for (const auto i : *test2) { for (const auto j : i) { cout j ; } cout endl; } */ return 0; }2018.11.12日更新优化了deleteEdge函数第一个for循环搜索待删除边时搜索的边链表上每一个边节点的与边链表上所有边节点共同关联的顶点对应的边节点一端相对的一端的顶点的编号严格递增所以如果发现被删除边的前述一端的顶点编号夹在边链表上俩边节点前述一端的顶点编号之间或小于边链表上前述一端的顶点编号最小的边节点的顶点编号则函数直接退出没有必要继续搜索