当前位置：首页 > 编程日记 > 正文

数据结构 -- 图与图存储

编程日记 2024-04-05 20:00:00

我们在使用像QQ ，微信，微博，快手，抖音等社交软件的过程中经常需要添加好友，关注好友和被好友关注。这个过程中这样的社交网络中的好友关系就需要被存储下来，存储在各个公司的后台服务器之上，都会作为每个公司的数据资产来进行自己核心业务的开发（视频推荐、好友推荐。。。）

这个用来保存好友关系的数据结构就是图，接下来探索一下这个非线性数据结构的基本实现。
在这里插入图片描述
图的一些基本概念如上导图，已经描述的很清楚了，这里重点说的是图的图存储方式。
基本的存储方式有两种：

邻接矩阵
邻接表

邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点i与顶点j之间有边，我们就将A[i][j]和A[j][i]
标记为1;对于有向图来说，如果顶点i到顶点j之间，有一条箭头从顶点i指向顶点j的边，那我们就将A[i][j]标记为1。同理，如果有一条箭头从顶点j指向顶点i的边，我们就将A[j][i]标记为1。对于带权图，数组中就存储相应的权重。
在这里插入图片描述
用数组表示的底层数据结构能够提供高效的查找能力，但是缺点也很明显，就是浪费空间过于严重，针对无向图的存储中只需要保存一个A[i][j]即可。

邻接表底层依赖链表进行数据存储，能够解决邻接矩阵浪费空间严重的问题，链表只有添加了新节点才会分配空间。整体的实现有点像散列表。
对于无向图来说，每一个顶点表示一个链表，与该顶点相连的其他顶点依次添加到该顶点的链表之上，类似如下：
在这里插入图片描述
有向图也是类似的，链表上仅保存该顶点指向的顶点

链表本身的查找效率比较低，需要顺链访问，在邻接表中可以将底层的链表存储结构用更加高效的动态查找数据结构来代替（链表和红黑树）。

以上数据结构都是存放在内存中的，但是实际的线上环境社交关系数据量以TB级别进行存储，这个时候数据量远超内存，便需要有持久化能力，需要对图的内存数据结构进行编码。
以邻接表距离，遍历邻接表，将顶点和对应链接顶点别编码为(user_id, follower_id)，后续的关系依次追加。像常见的分布式图存储，大体也是类似的方式进行存储，只不过底层磁盘的编码格式更为复杂一点。可以类似与sst中的data_block,index block,footer 依次索引到datablock中，datablock保存实际的user_id和follower_id信息。

在这里插入图片描述

同时图存储系统也希望将依赖于图的众多查找算法（bfs,dfs,djs,djkstra,A*,启发式搜索等）下沉到存储层，从而节省计算层的CPU开销。这时候，一个高效的分布式图存储系统的雏形边有了（只是单机的，分布式能力还是一大部分工作量），当然为用户提供可以访问的图语言也是完善系统的一部分。

接下来简单实现一下邻接表和邻接矩阵的图存储功能：

邻接表
graph_list.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct Graph_vertex vertex;typedef struct Graph_edge { // 边struct Graph_vertex *v; // 该边链接的顶点struct Graph_edge *next; // 用链表管理的链接同一顶点的下一条边
}edge;typedef struct Graph_vertex { // 顶点int data;   // 顶点的值edge *e; // 顶点的边 链表管理的相连接的边
}vertex;#define MAX_GRAPH (1 << 8)
typedef struct Graph{vertex *vxs[MAX_GRAPH];
}graph;void init_graph(graph *g){int i = 0;for (;i < MAX_GRAPH; i++) {g->vxs[i] = NULL;}
}/* 创建顶点 */
vertex *create_vertex(int data) {if(data < 0) {return NULL;}vertex * v = NULL;v = (vertex *)malloc(sizeof(vertex));if(v == NULL) {return NULL;}v->data = data+1;v->e = NULL;return v;
}/* 创建边 */
edge *create_edge(vertex *v){if(v == NULL) {return NULL;}edge *e;e = (edge *)malloc(sizeof(edge));if(e == NULL) {return NULL;}e->v = v;e->next = NULL;return e; 
}/* 为顶点v1 插入边 */
void insert_edge(vertex *v1, vertex *v2) {if (v1 == NULL || v2 == NULL) {return;}edge **e;e = &v1->e;while(*e) {e = &(*e)->next;}*e = create_edge(v2);
}/* 打印邻接表 */
void dump_graph(graph *g) {int i;for(i = 0;i < MAX_GRAPH; ++i) {vertex *v = g->vxs[i];edge *e;if(v == NULL) {continue; }printf("Vertex[%d]:%2d->",i+1, v->data);e = v->e;while(e) {if(e->next != NULL) {printf("%2d->", e->v->data);}else {printf("%2d", e->v->data);}e = e->next; }printf("\n");}
}/* 1 ----- 2 ----- 3|     / |     /|    /  |    / |   /   |   /  |  /    |  /   | /     | /    4 ----- 5
*/
void create_graph(graph *g) {int i = 0;init_graph(g);for (;i < 5; ++i) {g->vxs[i] = create_vertex(i);}// 链接1--2, 1--4insert_edge(g->vxs[0],g->vxs[1]);insert_edge(g->vxs[0],g->vxs[3]);// 链接2--1,2--3,2--4,2--5insert_edge(g->vxs[1],g->vxs[0]);insert_edge(g->vxs[1],g->vxs[2]);insert_edge(g->vxs[1],g->vxs[3]);insert_edge(g->vxs[1],g->vxs[4]);// 链接3--2,3--5insert_edge(g->vxs[2],g->vxs[2]);insert_edge(g->vxs[2],g->vxs[4]);// 链接4--1,4--2,4--5insert_edge(g->vxs[3],g->vxs[0]);insert_edge(g->vxs[3],g->vxs[1]);insert_edge(g->vxs[3],g->vxs[5]);// 链接5--2,5--3,5--4insert_edge(g->vxs[4],g->vxs[1]);insert_edge(g->vxs[4],g->vxs[2]);insert_edge(g->vxs[4],g->vxs[3]);
}int main() {graph g;create_graph(&g);dump_graph(&g);return 0;
}

邻接矩阵
graph_matrix.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_GRAPH (1 << 8)int *graph[MAX_GRAPH];void init_graph(int size) {if (size > MAX_GRAPH) {return ;}int i = 0;int j = 0;for (; i < size; ++i) {graph[i] = (int*)malloc(size*sizeof(int));for (;j < size; ++j){graph[i][j] = 0;}}
}void add_edge(int v1, int v2) {graph[v1][v2] = 1;graph[v2][v1] = 1;
}void print_graph(int size) {int i = 0;int j = 0;for (; i < size; ++i) {for (; j < size; ++j)  {printf("%d ", graph[i][j]);}printf("\n");}
}/* 1 ----- 2 ----- 3|     / |     /|    /  |    / |   /   |   /  |  /    |  /   | /     | /    4 ----- 5
*/
void create_graph(int size) {init_graph(size);add_edge(0,1);add_edge(0,3);add_edge(1,0);add_edge(1,2);add_edge(1,3);add_edge(1,4);add_edge(2,1);add_edge(2,4);add_edge(3,0);add_edge(3,1);add_edge(3,4);add_edge(4,1);add_edge(4,2);add_edge(4,3);
}int main() {create_graph(6);print_graph(6);return 0;
}

https://www.dkcj.cn/info/4237.html

数据结构 -- 图与图存储

相关文章：

Struts2 验证规则配置文件

c语言中手机系统,一种手机课堂C语言编程系统的制作方法

cpp中sizeof与指针

利用Python制作简单的小程序：IP查看器

一文带你看透 GDB 的实现原理 -- ptrace真香

线程使用 c语言,如何用C语言实现多线程

eclipse设置保护色非原创

markdown 使用

python第九章：面向对象--小白博客

分布式一致性（共识）算法(Paxos,raft,ZAB)的一些总结

dedecms 财付通接口

r语言手动算两个C指数p值,如何用R语言进行Pvalue显著性标记？

linux yum命令详解

OpenCV编译viz模块

vim 成“神“之路（一）

android 添加头参数,Retrofit添加header参数的几种方法

redis下载地址

Ubuntu 13.10 安装软件失败后出现的问题——已安装 post-installation 脚本返回了错误号 1...

C. Edgy Trees Codeforces Round #548 (Div. 2) 【连通块】

设计模式之美 -- 策略模式

Good Bye 2014 B. New Year Permutation（floyd ）

android数据库查找一个字符,Android - 如何在Firebase数据库中对字符串进行简单搜索？_android_开发99编程知识库...

料酒有什么用？

jmeter对自身性能的优化

站在历史的长河中做农活

html 基本用法

ecliplse 调试android 断点,如何在Github maven项目上开始调试

Linux认证体系

python2.7 Cheetah You don't have the C version of NameMapper installed

C++ 从双重检查锁定问题到内存屏障的一些思考