无向图的邻接矩阵和邻接表实现各种操作 -- C++语言描述

一：实现代码

#ifndef _graph_h
#define _graph_h

#include 
#include 
using namespace::std;

///////////////////////////////////////////////////////////////////////////////////////////
//通用图结构
template 
class graph{
public:
	bool is_empty()const;
	bool is_full()const;
	
	int get_numvertices()const;    //当前顶点数
	int get_numedges()const;       //当前边数
public:
	virtual bool insert_vertex(const t&) = 0;            //插入顶点
	virtual bool insert_edge(const t&, const t&) = 0;    //插入边

	virtual bool remove_vertex(const t&) = 0;            //删除定点
	virtual bool remove_edge(const t&, const t&) = 0;    //删除边

	virtual int get_firstneighbor(const t&)const = 0;    //得到第一个邻接顶点
	virtual int get_nextneighbor(const t&, const t&)const = 0;    //某邻接顶点的下一个邻接顶点
	
	virtual void print_graph()const = 0;
	virtual int get_vertex_index(const t&)const = 0;     //得到顶点序号
protected:
	static const int vertices_default_size = 10;         //默认图顶点数
	int max_vertices;
	int num_vertices;
	int num_edges;
};

template 
bool graph::is_empty()const
{
	return num_edges == 0;
}

template 
bool graph::is_full()const
{
	return num_vertices >= max_vertices 
		   || num_edges >= max_vertices*(max_vertices-1)/2;    //判满，分为顶点满和边满
}

template 
int graph::get_numvertices()const
{
	return num_vertices;
}

template 
int graph::get_numedges()const
{
	return num_edges;
}

///////////////////////////////////////////////////////////////////////////////////////////

#define vertices_default_size graph::vertices_default_size //派生类继承父类，若父类为模板，派生类不可直接调用父类保护成员
#define num_vertices          graph::num_vertices            //以宏来代替每个位置写作用域的做法
#define num_edges             graph::num_edges
#define max_vertices          graph::max_vertices //另一种方法派生类内定义自己成员函数，可用using graph::num_edges，在类外则不可

///////////////////////////////////////////////////////////////////////////////////////////
//图的邻接矩阵表示法
template 
class graph_mtx : public graph{
public:
	graph_mtx(int);                   
	graph_mtx(int (*)[4], const int);         //矩阵构造
	
	~graph_mtx();                             
public:
	bool insert_vertex(const t&);
	bool insert_edge(const t&, const t&);  
	
	bool remove_vertex(const t&); 
	bool remove_edge(const t&, const t&); 

	int get_firstneighbor(const t&)const;
	int get_nextneighbor(const t&, const t&)const;
	
	int get_vertex_index(const t&)const;
	void print_graph()const;
private:
	t* vertices_list;                        //顶点线性表
	int **edge;                              //内部矩阵
};

template 
graph_mtx::graph_mtx(int sz = vertices_default_size)
{
	max_vertices = sz > vertices_default_size ? sz 
									: vertices_default_size;
	vertices_list = new t[max_vertices];

	edge = new int*[max_vertices];                    //动态申请二维数组
	for(int i=0; i
graph_mtx::graph_mtx(int (*mt)[4], const int arr_size)
{
	int edge_count = 0;
	max_vertices = arr_size > vertices_default_size ? arr_size 
											: vertices_default_size;
	vertices_list = new t[max_vertices];

	edge = new int*[max_vertices];
	for(int i=0; i
graph_mtx::~graph_mtx()
{
	for(int i=0; i
bool graph_mtx::insert_vertex(const t& vert)
{
	if(this->is_full())                       //派生类函数调用父类函数，用this或加作用域
		return false;
	vertices_list[num_vertices++] = vert;
	return true;
}

template 
bool graph_mtx::insert_edge(const t& vert1, const t& vert2)
{
	if(this->is_full())                       //判满
		return false;

	int index_v1 = get_vertex_index(vert1);   //得到顶点序号
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 == -1 || index_v2 == -1 )
		return false;
	
	edge[index_v1][index_v2] = edge[index_v2][index_v1] = 1;    //无向图
	++num_edges;	
	
	return true;
}

template 
bool graph_mtx::remove_vertex(const t& vert)          //用最后一个节点直接覆盖删除的节点，转化为删除最后一个节点
{
	int edge_count = 0;
	int index = get_vertex_index(vert);

	if(index == -1)
		return false;
	
	for(int i=0; i
bool graph_mtx::remove_edge(const t& vert1, const t& vert2)
{
	int index_v1 = get_vertex_index(vert1);
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 == -1 || index_v2 == -1)
		return false;

	edge[index_v1][index_v2] = edge[index_v2][index_v1] = 0;
	--num_edges;

	return true;
}

template 
int graph_mtx::get_firstneighbor(const t& vert)const
{
	int index = get_vertex_index(vert);

	if(index != -1){
		for(int i=0; i
int graph_mtx::get_nextneighbor(const t& vert1, const t& vert2)const
{
	int index_v1 = get_vertex_index(vert1);
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 != -1 && index_v2 != -1){
		for(int i=index_v2+1; i
int graph_mtx::get_vertex_index(const t& vert)const
{
	for(int i=0; i
void graph_mtx::print_graph()const
{
	if(this->is_empty()){
		cout << "nil graph" << endl;                      //空图输出nil
		return;
	}
	
	for(int i=0; i
struct node{                                              //节点用来存储与它相连接的顶点
	int dest;
	struct node* link;
	node(int d) : dest(d), link(nullptr) {}
};

template 
struct vertex{                                            //顶点结构体
	t vert;                                               //顶点
	struct node* adj;                                  //指向描述其他节点的链表
	vertex() : vert(t()), adj(nullptr) {}
};

template 
class graph_lnk : public graph{
public:
	graph_lnk(int);
	~graph_lnk(); 
public:
	bool insert_vertex(const t& vert);
	bool insert_edge(const t& vert1, const t& vert2);

	bool remove_vertex(const t& vert); 
	bool remove_edge(const t& vert1, const t& vert2); 

	int get_firstneighbor(const t& vert)const; 
	int get_nextneighbor(const t& vert1, const t& vert2)const;
	
	void print_graph()const; 
	int get_vertex_index(const t& vert)const;
protected:
	void remove_point_self(const int, const int);
	void modify_point_self(const int, const int, const int);
private:
	vertex* vertices_table;	
};

template 
graph_lnk::graph_lnk(int sz = vertices_default_size)
{
	max_vertices = sz > max_vertices ? sz : vertices_default_size;
	vertices_table = new vertex[max_vertices];                 //不用再清空，结构体构造函数已清空

	num_vertices = 0;
	num_edges = 0;
}

template 
graph_lnk::~graph_lnk()
{
	for(int i=0; ilink;
			delete tmp;
			tmp = next_tmp;
		}
	}
	delete []vertices_table;            //删除表
}

template 
bool graph_lnk::insert_vertex(const t& vert)
{
	if(this->is_full())
		return false;

	vertices_table[num_vertices++].vert = vert;

	return true;
}

template 
bool graph_lnk::insert_edge(const t& vert1, const t& vert2)
{
	if(this->is_full())
		return false;
	
	int index_v1 = get_vertex_index(vert1);
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 == -1 || index_v2 == -1)
		return false;

	auto tmp = vertices_table[index_v1].adj;
	while(tmp != nullptr){
		if(tmp->dest == index_v2)
			return false;
		tmp = tmp->link;
	}
	
	tmp = new node(index_v2);                    //采用前插法，比尾插法效率高，省事
	tmp->link = vertices_table[index_v1].adj;
	vertices_table[index_v1].adj = tmp;

	tmp = new node(index_v1);
	tmp->link = vertices_table[index_v2].adj;
	vertices_table[index_v2].adj = tmp;

	++num_edges;

	return true;
}

template 
bool graph_lnk::remove_vertex(const t& vert)
{
	int index = get_vertex_index(vert);
	int edge_count = 0;

	if(index == -1)
		return false;

	auto tmp = vertices_table[index].adj;
	auto next_tmp = tmp;
	
	while(tmp != nullptr){
		remove_point_self(index, tmp->dest);       //删除目标顶点指向自己的节点   
		++edge_count;                              //记录边数
		next_tmp = tmp->link;
		delete tmp;
		tmp = next_tmp;	
	}

	if(index != num_vertices-1){
		vertices_table[index].adj = vertices_table[num_vertices-1].adj;     //用最后一个顶点覆盖要删除的顶点
		vertices_table[index].vert = vertices_table[num_vertices-1].vert;
	}

	tmp = vertices_table[index].adj;
	while(tmp != nullptr){
		modify_point_self(tmp->dest, num_vertices-1, index);                //调整原指向最后一个顶点的节点，使其指向新的位置
		tmp = tmp->link;
	}
	
	--num_vertices;
	num_edges -= edge_count;

	return true;
}

template 
bool graph_lnk::remove_edge(const t& vert1, const t& vert2)
{
	int index_v1 = get_vertex_index(vert1);
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 == -1 || index_v2 == -1)
		return false;

	remove_point_self(index_v1, index_v2);                //相互删除指向自己的节点，相当于删除边
	remove_point_self(index_v2, index_v1);

	return true;
}

template 
int graph_lnk::get_firstneighbor(const t& vert)const
{
	int index = get_vertex_index(vert);

	if(index != -1 && vertices_table[index].adj != nullptr){    //第一个结点即为所求
		return vertices_table[index].adj->dest;
	}
	return -1;
}

template 
int graph_lnk::get_nextneighbor(const t& vert1, const t& vert2)const    //目标结点的下一个邻接节点即为所求
{
	int index_v1 = get_vertex_index(vert1);
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 != -1 && index_v2 != -1){
		auto tmp = vertices_table[index_v1].adj;
		
		while(tmp != nullptr && tmp->dest != index_v2)
			tmp = tmp->link;
		
		if(tmp->dest == index_v2 && tmp->link != nullptr)
			return tmp->link->dest;
	}
	return -1;
}

template 
void graph_lnk::remove_point_self(const int self_index, const int other_index)       //删除指向自己的结点
{
	auto tmp = vertices_table[other_index].adj;
	auto pre_tmp = tmp;
	
	while(tmp->dest != self_index){
		pre_tmp = tmp;
		tmp = tmp->link;
	}
	
	if(pre_tmp == tmp)
		vertices_table[other_index].adj = tmp->link;
	else
		pre_tmp->link = tmp->link;

	delete tmp;
}

template 
void graph_lnk::modify_point_self(const int other_index, 
								     const int old_index, const int new_index)         //调整原指向最后一个顶点的节点，使其指向新的位置
{
	auto tmp = vertices_table[other_index].adj;

	while(tmp->dest != old_index){
		tmp = tmp->link;
	}
	tmp->dest = new_index;
}

template 
int graph_lnk::get_vertex_index(const t& vert)const
{
	for(int i=0; i
void graph_lnk::print_graph()const
{
	if(this->is_empty()){
		cout << "nil graph" << endl;
		return ;
	}
	
	for(int i=0; idest << "-->";
			tmp = tmp->link;
		}
		cout << "nil" << endl;
	}
}

#endif

二：相关测试代码

1.邻接矩阵测试代码

#include "graph.h"

#define vertex_size 4

int main()
{
    int mtx[][vertex_size] = {{0,1,0,1},
                              {1,0,1,0},
                              {0,1,0,1},
                              {1,0,1,0}};
	//graph_mtx gm(mtx, vertex_size);
	
	graph_mtx gm;
	gm.insert_vertex('a');
	gm.insert_vertex('b');
	gm.insert_vertex('c');
	gm.insert_vertex('d');

	gm.insert_edge('a', 'b');
	gm.insert_edge('a', 'd');
	gm.insert_edge('b', 'c');
	gm.insert_edge('c', 'd');

	//cout << gm.get_firstneighbor('a') << endl;
	//cout << gm.get_nextneighbor('a', 'b') << endl;
	
	//gm.remove_vertex('b');
	gm.remove_edge('a', 'b');

	gm.print_graph();

	return 0;
}*/

部分测试结果：

2.邻接表测试代码

#include "graph.h"

#define vertex_size 4

int main()
{
    graph_lnk gl;

    gl.insert_vertex('a');
    gl.insert_vertex('b');
    gl.insert_vertex('c');
    gl.insert_vertex('d');

    gl.insert_edge('a','b');
    gl.insert_edge('a','c');
    gl.insert_edge('b','d');
	gl.print_graph();

	cout << "-------------after remove-------------" << endl;
	gl.remove_vertex('a');
	gl.print_graph();
	
	//gl.remove_edge('a', 'b');
	//gl.print_graph();

	cout << gl.get_firstneighbor('a') << endl;
	cout << gl.get_nextneighbor('a', 'c') << endl;

	return 0;
}

部分测试结果：

上文所有代码均经过测试，图中并未给全。