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