您的位置:首页 > 娱乐 > 八卦 > 浅谈【数据结构】图-图的存储

浅谈【数据结构】图-图的存储

2024/12/23 11:31:53 来源:https://blog.csdn.net/weixin_67526434/article/details/141568420  浏览:    关键词:浅谈【数据结构】图-图的存储

目录

1、图的存储

2、邻接表

3、十字链表


谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错,说的就是你,不用再怀疑!!!

希望我的文章内容能对你有帮助,一起努力吧!!!


1、图的存储

  • 邻接矩阵:数组表示法
    • 优势:存储/设计比较简单
    • 劣势:浪费空间。遍历出度比较费时间
  • 邻接表:通过数组+链表的形式来存储顶点出度关系
    • 优势:节省空间,遍历出度关系比较快
    • 劣势:操作相对邻接矩阵来说比较繁琐

2、邻接表

构建图类型

上述方式可以但是不够简洁

***领接表代码示例***

#include <iostream>
#include <cstring>// 关系类型
typedef struct relation
{int index; // 下标int weight; // 权值struct relation *next; // 下一个关系的顶点的下标指针
}Relation_t;// 顶点类型
typedef struct 
{std::string data; // 顶点数据Relation_t *first; // 该顶点的关系集
}Vertex_t;// 当前顶点数
int current_count = 0;/*@brief  创建一个图:邻接表@param  count 该图的最大顶点数量 @return 成功返回创建好的图指针
*/
Vertex_t *creatGraph(int count)
{// 申请空间Vertex_t *graph = new Vertex_t[count];// 初始化memset(graph,0,sizeof(Vertex_t)*count);std::cout << "请输入顶点数据空格分开(“结束”输入):";// 接受顶点while(1){std::string data = "结束";std::cin >> data;if(data == "结束")break;if(current_count == count)break;// 新增顶点位置graph[current_count].data  = data;graph[current_count].first = nullptr;current_count++;}// 增加关系while(1){std::cout << "请输入顶点关系(结束 结束 -1):";// 出发顶点和终止顶点 权值std::string start;std::string end;int data;std::cin >> start >> end >> data;if(start=="结束"||end=="结束"||data == -1)break;// 存储关系// 获取start和end在图数组的什么位置int index_s = 0,index_e = 0;for(;index_s < current_count;index_s++)if(graph[index_s].data == start)break;for(;index_e < current_count;index_e++)if(graph[index_e].data == end)break;// 两个顶点的下标找到了if(index_s == current_count||index_e == current_count)continue;// 添加关系Relation_t *rt = new Relation_t;rt->index = index_e;rt->weight = data;rt->next = nullptr;// 当至少存在出度顶点的时候if(graph[index_s].first){Relation_t *rt_ptr = graph[index_s].first;while(rt_ptr->next)rt_ptr = rt_ptr->next;// 存进关系链表rt_ptr->next = rt;}else{ // 一个出度结点都没有的时候graph[index_s].first = rt;}}return graph;
}void printrelation(Vertex_t *graph)
{if(!graph)std::cout << "空图" << std::endl;for(int count_v = 0;count_v < current_count;count_v++){std::cout << "顶点<"<< graph[count_v].data <<">:";Relation_t *rt_ptr = graph[count_v].first;while(rt_ptr){std::cout<< "<"<< graph[count_v].data <<","<< graph[rt_ptr->index].data <<">" << "("<<rt_ptr->weight<<")";rt_ptr = rt_ptr->next;}std::cout << std::endl;}
}int main()
{Vertex_t *graph = creatGraph(10);printrelation(graph);delete []graph;return 0;
}

逆邻接表:通过数组+链表的形式来存储顶点入度关系

3、十字链表

  • 十字链表:通过邻接表+逆邻接表形式实现,用来存储一个顶点的入度出度
    • 更方便的遍历一个顶点的入度和出度顶点

***十字链表示例代码***

#include <iostream>
#include <list>
#include <vector>using std::list;
using std::vector;template <typename _v_type_,typename _r_type_>
class OrthogonalList
{// 关系结构体typedef struct {int      index; // 下标_r_type_ weight;// 权值}Relation_t;// 顶点结构体typedef struct {_v_type_ data; // 顶点list<Relation_t> enter_r; // 入度集list<Relation_t> out_r;   // 出度集}Vertex_t;// 顶点集vector<Vertex_t> vertex;// 计算下标int getIndex(_v_type_ vertex_v){for(int index = 0;index < vertex.size();index++){if(vertex_v == vertex[index].data)return index;}return -1;}
public:OrthogonalList() // 构造函数: vertex(0){}~OrthogonalList() // 析构函数{}void addVertex(_v_type_ vertex_v) // 增加顶点{Vertex_t vt;vt.data = vertex_v;vertex.push_back(vt);}void addRelation(_v_type_ vertex_s,_v_type_ vertex_e,_r_type_ relation) // 增加弧{// 获取顶点下标int vt_start = getIndex(vertex_s);int vt_end   = getIndex(vertex_e);if(vt_start==-1||vt_end==-1)return;// 出度Relation_t rt_o;rt_o.index = vt_end;rt_o.weight = relation;vertex[vt_start].out_r.push_back(rt_o);// 入度Relation_t rt_e;rt_e.index = vt_start;rt_e.weight = relation;vertex[vt_end].enter_r.push_back(rt_e);}void print(){std::cout << "顶点关系集" << std::endl;for(auto v : vertex){std::cout << v.data << ":" << std::endl;std::cout << "入弧集:"; for(auto r : v.enter_r)std::cout << vertex[r.index].data << ":" << r.weight << "  ";std::cout << std::endl;std::cout << "出弧集:";for(auto r : v.out_r)std::cout << vertex[r.index].data << ":" << r.weight << "  ";std::cout << std::endl;}}
};int main()
{OrthogonalList<std::string,int> graph;std::cout <<"请输入顶点:";while(1){std::string vertex = "结束";std::cin >> vertex;if(vertex == "结束")break;graph.addVertex(vertex);}while(1){std::cout <<"请输入关系:";std::string vertex_s = "结束";std::string vertex_e = "结束";int data = -1;std::cin >> vertex_s >> vertex_e >> data;if(vertex_s == "结束"||vertex_e == "结束"||data == -1)break;graph.addRelation(vertex_s,vertex_e,data);}graph.print();return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com