其实你不是真的很有趣，你只是太孤独。这个你，就是我。 —— 食不知味 《食不知味》
0.序
你可能会好奇社交网络中人与人之间的好友关系是如何存储的，地图上城市与城市之间交通网络是如何建模的，实际上他们都利用了图结构，本文让我们走进基础图论,去了解图。
1.图的基础概念
1.1 图的定义
图是对若干对象之间成对关系建模的数据结构。由节点或节点（Vertex简称v），边（Edge简称e）组成。
节点集合表示:
V={v1，v2，v3,...，v7}
边集合表示:
E={e1,2，e1,3，e1,4，...，e6,7}
例如边e1,2表示连接节点v1，v2的边
图表示:
G=(V，E)
图是节点和边组成的二元组
2.图的分类
2.1无向图
无向指图中边是没有方向的，如下图e1,2可以表示节点v1到节点v2，也可以表示节点v2到节点v1。
在无向图中用“度”表示一个节点有多少条边，例如节点v1有3条边，它的度为3。
2.2 有向图
有向指图中的边是有方向且单向的，如下图e1,2表示节点v1到节点v2，从节点v2到达不了节点v1。
在有向图中将度分为了入度和出度
入度：节点的入度表示有多少条边指向这个节点。
出度：节点的出度表示有多少条边是以这个节点为起点指向其它节点。
2.3 无权图
无权图中，所有边的权重都是一样的。
2.4 带权图
在带权图中，每条边都有一个权重，权重大小各不相同
权重：
图应用不同的场景，权重的意义则不一样。
例如在城市地图中，城市和城市可以看做节点，城市和城市之间的公路可以看做边，边的权重可以是城市和城市之间的距离，距离越远权重越大。如果两地没有边则权重记作无穷大。
3.图的存储方式
图只是逻辑上的概念，将实体的关系映射到一张图上，实际存储操作本质还是数组+链表。
3.1 邻接矩阵
邻接矩阵底层依赖一个二维数组。
以无向无权图为例
如图中有7个节点，所以邻接矩阵的大小为7*7，第i行和第j列对应节点vi，例如下图圈出第6列第6行对应图节点v6，二维数组中的值表示权重。如果两个节点有边则权重为1，无边则权重为0或正无穷。
可以发现v3节点到v6节点，由于是无向图，有相反两个方向，所以对应邻接矩阵中两个元素，表示2个权重，权重相同都为1，这里可以发现无向图都是对称的。
再或者以有向无权图为例
邻接矩阵如下
以无向有权图为例
边的权重不相同
可以发现临街矩阵存储方式缺点比较浪费空间，优点是查询效率高，方便矩阵运算。
3.2 邻接表
针对邻接矩阵比较浪费内存空间的问题，来看另一种图的存储方式，邻接表。
类似散列表，每个节点对应一条链表，链表中存储和这个节点相连接的其它节点。
以无向无权图为例
如上图中
v3节点与v1，v4，v6节点相连，所以v3节点对应的链表关联v1，v4，v6节点，记为1，4，6。
v5节点和任何节点都不想连，所以记为空。
邻接表存储虽然比较节省空间，但是使用相对会比较耗时间，例如我想确定是否有一条节点v1到节点v4的边，就需要遍历节点v1的链表，找到链表中是否存在节点v4。
如果链表过长为提高效率，可以将链表换成其它高效的数据结构，例如平衡二叉树，红黑树，跳表等。
4.图存储代码事例
4.1 邻接矩阵事例代码
public class AdjacencyMatrix {
/**
* 矩阵
*/
private final int[][] matrix = new int[20][20];
/**
* 城市节点
*/
private final City[] cityVertexList = new City[20];
/**
* 当前节点下标
*/
private int currentVertIndex;
/**
* 是否为有向图
*/
private final boolean directed;
public AdjacencyMatrix(boolean directed) {
this.currentVertIndex = 0;
this.directed = directed;
}
/**
* 增加城市节点
*
* @param city
*/
public void addVertex(City city) {
cityVertexList[currentVertIndex++] = city;
}
/**
* 城市和城市之间添加边
*
* @param cityNameStart
* @param cityNameEnd
*/
public void addEdge(String cityNameStart, String cityNameEnd) {
int startIndex = findCityIndexByName(cityNameStart);
int endIndex = findCityIndexByName(cityNameEnd);
if (startIndex == endIndex) {
return;
}
matrix[startIndex][endIndex] = 1;
if(!directed){
matrix[endIndex][startIndex] = 1;
}
}
private int findCityIndexByName(String cityName) {
for (int i = 0; i < cityVertexList.length; i++) {
if (cityVertexList[i] == null) {
throw new IllegalStateException("未找到该城市节点");
}
if (cityVertexList[i].getCityName().equals(cityName)) {
return i;
}
}
throw new IllegalStateException("未找到该城市节点");
}
/**
* 打印矩阵
*/
public void printMatrix() {
for (int i = 0; i < currentVertIndex; i++) {
for (int j = 0; j < currentVertIndex; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
AdjacencyMatrix matrix = new AdjacencyMatrix(true);
matrix.addVertex(new City("成都"));//0
matrix.addVertex(new City("北京"));//1
matrix.addVertex(new City("吉林"));//2
matrix.addVertex(new City("杭州"));//3
matrix.addEdge("成都", "吉林");//02
matrix.addEdge("吉林", "杭州");//23
matrix.addEdge("杭州", "北京");//31
matrix.addEdge("北京", "成都");//10
matrix.printMatrix();
}
}4.2 邻接表代码
/**
* @description： 图-邻接表
* @Author MRyan
* @Date 2022/10/15 22:14
* @Version 1.0
*/
public class AdjacencyList {
/**
* 节点集合
*/
private final Node[] nodes;
/**
* 邻接表中表对应的链表的节点
*/
private static class ENode {
/**
* 该边所指向的节点的位置
*/
ENode nextEdge;
/**
* 指向下一条弧的指针
*/
int iVex;
}
/**
* 邻接表中表的节点
*/
private static class Node {
/**
* 节点信息
*/
ENode firstEdge;
/**
* 指向第一条依附该节点的弧
*/
String data;
}
/**
* 创建图(用已提供的矩阵)
*
* @param vertex 节点数组
* @param edges 边数组
* @param directed 是否是有向图
*/
public AdjacencyList(String[] vertex, String[][] edges, boolean directed) {
// 初始化"节点数"和"边数"
int vLen = vertex.length;
// 初始化"节点"
nodes = new Node[vLen];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node();
nodes[i].data = vertex[i];
nodes[i].firstEdge = null;
}
// 初始化"边"
for (String[] edge : edges) {
// 读取边的起始节点和结束节点
int p1 = getPosition(edge[0]);
// 读取边的起始节点和结束节点
int p2 = getPosition(edge[1]);
// 初始化node1
ENode node1 = new ENode();
node1.iVex = p2;
// 将node1链接到"p1所在链表的末尾"
if (nodes[p1].firstEdge == null) nodes[p1].firstEdge = node1;
else linkLast(nodes[p1].firstEdge, node1);
if (!directed) {
// 初始化node2
ENode node2 = new ENode();
node2.iVex = p1;
// 将node2链接到"p2所在链表的末尾"
if (nodes[p2].firstEdge == null) nodes[p2].firstEdge = node2;
else linkLast(nodes[p2].firstEdge, node2);
}
}
}
/*
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while (p.nextEdge != null) p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回节点位置
*/
private int getPosition(String ch) {
for (int i = 0; i < nodes.length; i++)
if (Objects.equals(nodes[i].data, ch)) return i;
return -1;
}
/*
* 打印矩阵队列图
*/
public void print() {
for (int i = 0; i < nodes.length; i++) {
System.out.printf("%d(%s): ", i, nodes[i].data);
ENode node = nodes[i].firstEdge;
while (node != null) {
System.out.printf("%d(%s) ", node.iVex, nodes[node.iVex].data);
node = node.nextEdge;
}
System.out.println();
}
}
public static void main(String[] args) {
String[] vertex = {"成都", "北京", "吉林", "杭州", "乌鲁木齐", "重庆", "呼和浩特"};
String[][] edges = new String[][]{{"成都", "吉林"}, {"吉林", "杭州"}, {"杭州", "北京"}, {"北京", "成都"},};
// 采用已有的"图"
AdjacencyList pG = new AdjacencyList(vertex, edges, true);
// 打印图
pG.print();
}
}
5.图的应用
简单的介绍了图的基础概念，以及图结构，下面回到我们开头的问题：如何存储社交网络中的好友关系。
最基本需要支持如下几种场景：
- 某个用户的粉丝有哪些用户
- 某个用户关注了哪些用户
因为社交网络是一张稀疏图，使用邻接矩阵存储相对比较浪费存储空间，所以使用邻接表来存储。
通过邻接表存储有向图可以很轻松的查找某个用户关注了哪些用户，如下图：
邻接表表示如下：
基于邻接表可以轻松的查找某个用户关注了哪些用户。
那如何查找某个用户被哪些用户关注呢，可以从逆邻接表中查找。
邻接表存储的是用户的关注关系，而逆邻接表存储用户的被关注关系。
对于小规模的数据，可以将整个社交关系模型存储在内存中，但数据规模太大，无法全部存储到内存中，可以通过哈希算法等数据分配技术，将邻接表存储在不同机器上，当查询节点和节点之间的关系时，可以通过同样的哈希算法，先定位到节点所在的机器，然后再对应机器上查找。
当然也可以持久化到外部存储上。
参考
作者：MRyan
本文采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
转载时请注明本文出处及文章链接。本文链接：https://wormholestack.com/archives/607/