引言
大家都玩过微博和微信吧，微博的互关和微信互相添加好友，你知道如何存储这些关系吗？没错，就是我们今天要聊的数据结构“图”。
如何理解图
图跟二叉树一样是一种非线性的数据结构，但是比二叉树要复杂。二叉树中的元素我们称为节点，图中的元素我们称为“顶点”，如下图，图中的每个顶点都可以与其他顶点建立关系，我们把这种关系称为“边”。
我们以微信举例，每个用户可以就可以看做一个顶点。如果两个用户添加好友，就建立一条边。每个用户有多少好友，该用户节点就有多少条边，对应图中的概念就是“度”。这种关系跟微博中互相关注一样，但是，微博还允许单向关注，也就是A关注了B，但是B没有关注A。这种关系用有向图描述，如果用户A关注了用户B，我们就在图中画一条从A指向B的边，我们把这种有方向的图叫做“有向图”，类似，没有方向的叫“无向图”。
前面提到的“度”的概念，在有向图中，对应“入度”和“出度”。顶点的入度表示有多少个顶点指向它，顶点的出度表示有多少条从该顶点指出到其他顶点的边。对应到微博，入度就是你有多少粉丝，出度就是你关注了多少人。
不知道大家有没有留意过，QQ如果两个人聊天频繁，就会有个友谊的巨轮标识，QQ空间的亲密度同理，这种关系用“带权图”描述。带权图中的每条边都有一个权重，可以通过权重来标识两个用户的亲密度。
关于图的概念还有很多，这篇文章就先介绍这几个。对于图有了基本的认识之后，我们来看看，如何存储这种数据结构呢？
二、图的存储
2.1 领接矩阵
领接矩阵的顶层实际上是个二维数组。对于无向图来说，如果顶点A和顶点B有边，那么A[i][j]和A[j][i]都需要置为1；对于有向图，如果是顶点A指向顶点B，那么只需要将A[i][j]置为1。如果是带权图，对应的位置保存的是权重值。
领接矩阵的优点是直观、设计简单，基于数组，获取两个顶点的关系非常高效；其次，由于是基于二维数组，可以将图的很多运算转为矩阵之间的运算。缺点是浪费空间。对于无向图来说，如果顶点A和顶点B有边，那么A[i][j]和A[j][i]都需要置为1，实际上只需要让A[i][j]置为1就可以描述这个关系了，对角线的另一半空间就浪费了。而且大部分图都是稀疏图，空间浪费会更严重。
2.2 领接表
下图是一张有向图的领接表。领接表乍一看有点像哈希表，每个顶点对应数组的下标元素，每个元素对应一个链表，链表里存储的是这个顶点指向的其他的顶点的集合。
优点：节省空间，但是，确定顶点之间的关系就比较耗时。比如，想查看顶点2和顶点4是否存在一条边，就需要遍历顶点2对应的链表。
只使用领接表存储是不够的，因为查找某个用户关注了那些用户非常容易，但是，想要知道这个用户被那些用户关注，就没哪么容易了，此时需要逆领接表。
三、代码实现
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <time.h> #define MAX_GRAPH_VERTEX (1 << 8) struct vertex; struct vertex_adjs { struct vertex *v; struct vertex_adjs *next; }; struct vertex { int data; struct vertex_adjs *adj; }; struct graph { struct vertex *vxs[MAX_GRAPH_VERTEX]; }; void InitGraph(struct graph *graph) { for (int i = 0; i < MAX_GRAPH_VERTEX; i++){ graph->vxs[i] = NULL; } return; } struct vertex* CreateVertex(int data) { struct vertex *vtx; vtx = malloc(sizeof(struct vertex)); if (!vtx) { printf("malloc struct vertex failed!\n"); return NULL; } vtx->data = data; vtx->adj = NULL; return vtx; } struct vertex_adjs *CreateVertexAdj(struct vertex *v) { struct vertex_adjs *v_adj; v_adj = malloc(sizeof(struct vertex_adjs)); if (!v_adj){ printf("malloc struct vertex_adjs failed!\n"); return NULL; } v_adj->v = v; v_adj->next = NULL; return v_adj; } void InsertAdj(struct vertex *v, struct vertex *adj) { struct vertex_adjs **v_adj; v_adj = &v->adj; while (*v_adj){ v_adj = &(*v_adj)->next; } *v_adj = CreateVertexAdj(adj); } void printGraph(struct graph *graph) { for (int i = 0; i < MAX_GRAPH_VERTEX; i++) { struct vertex *v = graph->vxs[i]; struct vertex_adjs *adj; if (v == NULL) continue; printf("Vertex[%02d]: %4d --->", i, v->data); adj = v->adj; while (adj) { printf(" [%2d] ", adj->v->data); adj = adj->next; } printf("\n"); } return ; } void test_graph(struct graph *graph) { InitGraph(graph); for (int i = 0; i < 5; i++){ graph->vxs[i] = CreateVertex(i+1); } /* connect 1 -> 2, 1 -> 4 */ InsertAdj(graph->vxs[0], graph->vxs[1]); InsertAdj(graph->vxs[0], graph->vxs[3]); /* connect 2 -> 1, 2 -> 3, 2 -> 5, 2 -> 4 */ InsertAdj(graph->vxs[1], graph->vxs[0]); InsertAdj(graph->vxs[1], graph->vxs[2]); InsertAdj(graph->vxs[1], graph->vxs[4]); InsertAdj(graph->vxs[1], graph->vxs[3]); /* connect 3 -> 2, 3 -> 5 */ InsertAdj(graph->vxs[2], graph->vxs[1]); InsertAdj(graph->vxs[2], graph->vxs[4]); /* connect 4 -> 1, 4 -> 2, 4 -> 5 */ InsertAdj(graph->vxs[3], graph->vxs[0]); InsertAdj(graph->vxs[3], graph->vxs[1]); InsertAdj(graph->vxs[3], graph->vxs[4]); /* connect 5 -> 4, 5 -> 2, 5 -> 3 */ InsertAdj(graph->vxs[4], graph->vxs[3]); InsertAdj(graph->vxs[4], graph->vxs[1]); InsertAdj(graph->vxs[4], graph->vxs[3]); return ; } int main() { struct graph *tg = (struct graph*)malloc(sizeof(struct graph)); if (!tg){ printf("malloc struct graph failed!\n"); return -1; } test_graph(tg); printGraph(tg); return 0; }
运行结果：
