【数据结构】图的邻接表表示(GNU C++实现)

前端之家收集整理的这篇文章主要介绍了【数据结构】图的邻接表表示(GNU C++实现)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

图G=(V,E)有两种标准的方法,即邻接表和邻接矩阵,它们即可以表示有向图,又可以表示无向图;其中邻接表,通常表示的是稀疏图;稠密图通常用邻接矩阵表示;


复杂度分析

(1)邻接矩阵的空间复杂度为O(V*V),针对有向图;

(2)邻接表的空间复杂度为O(E),针对有向图;


本实验的图为稀疏的有环有向带权图;随机产生;

方案:

(1)一般我们用自己的C语言的指针和动态内存来构建邻接表,但是还是有所弊端,动态内存,如果用户一直不显示释放,将会一直驻留内存,无法释放;

(2)如果使用C++语言中的智能指针,对本场景也会有问题;

(2.1)动态内存使用智能指针来管理,节点的内部指向仍旧使用普通指针来管理,那么当使用的动态内存没有计数指向(use_count为0)时,就会自动释放,造,普通指针指向错误

(2.2)动态内存使用智能指针来管理,节点的内部指向也使用智能指针来管理;由于内部的智能指针代表的是一个新的指向计数,失去了普通指针操作内存的作用;

(3)虽然(1)可以实现,但是是自己造轮子,效率和可靠性不够,因此采用STL标准库的vector来管理智能指针;


程序实现:

Directed_Graph.h

#include <vector>
#include <random>
#include <memory>
#include <iostream>
#include <ctime>
using namespace std;

struct V_Nodes{				//循环链表表示
	unsigned id;			//顶点的编号,从0开始到vertex_nums-1;
	unsigned weight;		//权值
};

class Directed_Graph
{
private:
	unsigned vertex_nums;		//顶点的个数
	vector<vector<shared_ptr<V_Nodes>>> vnodes_arrays;	//存放邻接表的顶点表向量,vnodes_arrays中存放每一个顶点的双向循环链表,使用list速度较慢;

	/*
		本函数主要是构造邻接表的边的过程,成功返回true,失败返回false
	*/
	bool insert_edge(unsigned source,unsigned dest,unsigned weight)	
	{
		vector<shared_ptr<V_Nodes>>& vs = vnodes_arrays[source];
		
		auto iter = vs.cbegin();
		for(; iter != vs.cend(); iter++){
			if((*iter)->id == dest){		//看是否已经构造过该边了
				return false;
			}else if((*iter)->id > dest){		//找到插入节点的后节点
				break;
			}
		}
		
		shared_ptr<V_Nodes> p = make_shared<V_Nodes>();	//构造该边
		p->id = dest;
		p->weight = weight; 
		
		vs.insert(iter,p);				//在iter之前插入新的节点,即边
		
		return true;
	}
public:
	Directed_Graph()			//构造函数初始化时将会随机建立有向有环带权有向图
	{
		default_random_engine e(time(0));		//设置种子			
		uniform_int_distribution<unsigned> u(5,9);	//均匀分布,u为随机数源
		vertex_nums = u(e);				//产生顶点数目
	
		for(size_t i = 0; i < vertex_nums; i++){
			vector<shared_ptr<V_Nodes>> vectors;			
			vnodes_arrays.push_back(vectors);		//放入循环链表
		}

		uniform_int_distribution<unsigned> u2(0,vertex_nums-1);	//顶点的随机
		uniform_int_distribution<unsigned> u3(3,15);			//边值的随机
		
		unsigned source,dest,weight;			//源顶点,目的顶点,权值
		unsigned max_edges_nums	= vertex_nums * vertex_nums;	//由于有环,故打印的总边数并不是无环有向图的vertex_nums * (vertex_nums  - 1);
		unsigned count = 0;
		unsigned total_count = 0;

		while(count < max_edges_nums / 3){		//当边数小于一半时就继续产生
			source = u2(e);				//产生随机边
			dest = u2(e);
			weight = u3(e);
			if(insert_edge(source,weight)){	
				count++;
			}		
			total_count++;
		}

		//cout<<vertex_nums<<" "<<max_edges_nums<<" "<<count<<" "<<total_count<<endl;
	}

	void printf_graph()		//打印图
	{
		int count = 0;
		int counts = 0;
		for(auto vs : vnodes_arrays){
			for(auto r : vs){
				cout<<"<"<<count<<","<<r->id<<">("<<r->weight<<") ";
				counts++;			
			}
			cout<<endl;
			count++;
		}
	}
};

main.cpp

#include "Directed_Graph.h"

int main(void)
{
	Directed_Graph directed_graph;

	cout<<"---------------------------------------------------------\n";
	cout<<"随机产生的有向有环带权图如下:\n";
	directed_graph.printf_graph();
	cout<<"---------------------------------------------------------\n";
	return 0;
}

程序输出



注,方案1的实现;由于内存释放得自己实现,后续图的操作将不会使用此方案,因为我们要实现动态内存的自动管理;

Directed_Graph.h

#include <vector>
#include <random>
#include <memory>
#include <iostream>
#include <ctime>
using namespace std;

struct V_Nodes{ //循环链表表示
	unsigned id; //顶点的编号,从0开始到vertex_nums-1;
	unsigned weight; //权值
	V_Nodes *p_next; //邻接表指向下一个顶点
	V_Nodes *p_pre; //邻接表指向上一个顶点
};


class Directed_Graph
{
private:
	unsigned vertex_nums; //顶点的个数
	vector<V_Nodes *> vnodes_lists; //存放邻接表的顶点表向量,只是存放指针

	/*
	本函数主要是构造邻接表的边的过程,成功返回true,失败返回false
	*/
	bool insert_edge(unsigned source,unsigned weight) 
	{
		V_Nodes* temp = vnodes_lists[source]; //如果不是引用,也就是拷贝,获得顶点向量
		if(dest == source) //源顶点等于目的顶点时
		{
			if(temp->weight == 0){
				temp->weight = weight; //自身到自身也有全值,有环
				return true;
			}else{
			return false;
			}
 		}


		V_Nodes *p_next = temp->p_next; //指向下一个节点 

		while(p_next != temp->p_next->p_pre){ //当到了队列头时
			if(p_next->id == dest){ //已经生成过该条边了,返回flase
	 			return false;
		 	}else if(p_next->id > dest){ //邻接表中,邻接的边数递增
				break; //没有找到 
			}
 
			p_next = p_next->p_next;
		};
 
		//在一个顶点的后面插入一个节点,只能有两种情况,初始化的时候会行不通
		V_Nodes* current = new V_Nodes(); //创建新节点,使前节点指向新节点
		current->id = dest; //改变新节点的值
		current->weight = weight; 

		current->p_next = p_next; //改变新节点的next
 		current->p_pre = p_next->p_pre; //改变新节点的pre
 		p_next->p_pre->p_next = current; //改变前节点的p_next
 		p_next->p_pre = current; //改变后节点的pre


 		return true;
	}
public:
 	Directed_Graph() //构造函数初始化时将会随机建立有向有环带权有向图
 	{
		default_random_engine e(time(0)); //设置种子 
		uniform_int_distribution<unsigned> u(7,12); //均匀分布,u为随机数源
		vertex_nums = u(e); //产生顶点数目
 
		for(size_t i = 0; i < vertex_nums; i++){
			V_Nodes* v_nodes = new V_Nodes(); 
 			v_nodes->id = i;
 			v_nodes->weight = 0; //初始化,权重为0
 			v_nodes->p_next = v_nodes;
 			v_nodes->p_pre = v_nodes; 
 			//cout<<i<<" "<<v_nodes<<endl;
 			vnodes_lists.push_back(v_nodes); //copy,p_next内部指针指向仍是以前的内存,存放这几个顶点的邻接表向量
 		}


 		uniform_int_distribution<unsigned> u2(0,vertex_nums-1); //顶点的随机
		uniform_int_distribution<unsigned> u3(3,15); //边值的随机
 
 		unsigned source,weight; //源顶点,目的顶点,权值
 		unsigned max_edges_nums = vertex_nums * vertex_nums; //由于有环,故打印的总边数并不是无环有向图的vertex_nums * (vertex_nums  - 1);
 		unsigned count = 0;
 		unsigned total_count = 0;
 		while(count < max_edges_nums / 3){ //当边数小于一半时就继续产生
 			source = u2(e); //产生随机边
 			dest = u2(e);
 			weight = u3(e);
 			if(insert_edge(source,weight)){ 
 				count++;
 			} 
 			total_count++;
 		}
 	}


	void printf_graph()
 	{
		for(auto iter = vnodes_lists.cbegin(); iter != vnodes_lists.cend(); iter++){
			V_Nodes *p_next = (*iter)->p_next;
			if((*iter)->weight > 0){ //打印有环的顶点
 				cout<<"<"<<(*iter)->id<<","<<(*iter)->id<<">("<<(*iter)->weight<<") ";
 			}
 
 			while(p_next != (*iter)->p_next->p_pre){ //打印邻接的顶点和边
 				cout<<"<"<<(*iter)->id<<","<<p_next->id<<">("<<p_next->weight<<") "; //打印
				p_next = p_next->p_next; 
		 	}
 			cout<<endl;
 		}
 	}
};
原文链接:https://www.f2er.com/datastructure/383025.html

猜你在找的数据结构相关文章