欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-08 12:17:33
一:实现代码 #ifndef _graph_h #define _graph_h #include #include using namespace::std; /////...

一:实现代码

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

部分测试结果:

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

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

部分测试结果:

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

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