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