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