前言
前面我们介绍了线性表和树这两大类数据结构，线性表局限于一个直接前驱和一个直接后继，树也只能有一个直接前驱也就是父节点，当我们需要表示多对多的关系时就需要用到图这种数据结构，比如微博，微信互相关注，互加好友的社交关系就用图来表示。
1.概述
图(Graph)是一种数据结构，由结点和边组成，通常表示为G(V,E),其中G表示一个图，V是图G中结点的集合，结点也称顶点，可以具有零个或多个相邻元素，E是图G中边的集合，两个结点之间的连接称为边。
举个栗子：就拿微信加好友来举例把，我们可以把每个用户看做一个顶点，如果两个用户互加好友，就在两者之间建立一条边。所以整个微信好友的关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中，就是顶点的度（degree），就是和顶点相连接的边的条数。
再拿微博的好友关注举个栗子，我们都知道微博是允许单向关注的，即A关注了B，B可以不关注A。表示这种关系，我们引入了方向的概念，如果A关注了B，我们就在图中画一条从A到B的带箭头的边，如果B也关注了A，我们再画一条从B到A带箭头的边。我们把这种边有方向的图叫做有向图，把边没有方向的图叫做无向图
图一
刚刚介绍过，无向图中“度”表示一个顶点有多少条边。有向图中我们把度分为入度（in-degree）和出度（out-degree）。
顶点的入度表示有多少条边指向这个顶点，顶点的出度表示有多少条边是以这个顶点为起点指向其他顶点，对应到微博的栗子，人度表示有多少粉丝，出度就表示关注了多少人。
前面举了微信，微博的栗子，再来举个QQ的栗子：
QQ中的社交关系就要稍微复杂一点。QQ不仅记录了两个用户之间的好友关系，还记录了两个好友之间的亲密度，如果两个好友经常聊天，亲密度就高，不经常聊天，亲密度就比较低。这种关系表示到图中，就是带权图（Weighted Graph），在带权图中，每条边都有一个权重值（weight），我们可以用这个权重值来表示好友的亲密度。
图二
带权图还可以表示交通图中两个城市之间的距离。
图三
2.图的表示
图的常用表示方式有两种：一种是邻接矩阵（可以用二维数组存储），一种是邻接表（可以用链表存储）
- 邻接矩阵： 邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点i与顶点j之间有边，我们就将A[i][j]和A[j][i]标记为1；1表示两个顶点有连接，0表示两个顶点时间没有连接。对于有向图来说，如果顶点i到顶点j之间，有一条箭头从顶点i指向顶点j的边，那我们就将A[i][j]标记为1。同理，如果有一条箭从顶点j指向顶点i的边，我们就将A[j][i]标记为1。对于带权图，数组中就存储相应的权重。
图四
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在的，会造成一定的空间浪费。如果我们存储的是稀疏图（Sparse graph），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法是很浪费空间的。比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。所以邻接矩阵比较适合存储稠密图（Dense graph）。
针对上面邻接矩阵比较浪费内存空间的问题，我们来看另外一种图的存储方法， 邻接表（Adjacency List）
- 邻接表：邻接表只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表可以用数组存储，也可以由数组+链表组成。每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
用数组存储的邻接表：
图五
用数组+链表组成的邻接表：
图六
邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。
3.代码实现
完成如下图的一个图的基本代码实现
图七
public class Graph {
private ArrayList<String> vertexList; //存储顶点集合
private int[][] edges; //存储图所对应的邻接矩阵
private int numOfEdges; //表示边个数
private boolean directed; //是否是有向图
public Graph(int n,boolean directed){
vertexList = new ArrayList<>();
edges = new int[n][n];
numOfEdges = 0;
this.directed = directed;
}
//添加顶点
public void insertVertex(String vertex){
vertexList.add(vertex);
}
//添加边
public void insertEdges(int v1,int v2,int weight){
edges[v1][v2] = weight;
if(directed)
edges[v2][v1] = weight;
numOfEdges++;
}
//返回顶点个数
public int getNumOfVertex(){
return vertexList.size();
}
//获得边的个数
public int getNumOfEdges(){
return numOfEdges;
}
//通过索引获取对应的节点
public String getVertexByIndex(int i){
if(i < 0 || i>=vertexList.size())
throw new IllegalArgumentException("非法索引");
return vertexList.get(i);
}
//获取n和m的的权值
public int getWeight(int v1,int v2){
if(v1 < 0 || v1 >= edges.length || v2 < 0 || v2 >=edges.length)
throw new IllegalArgumentException("非法索引");
return edges[v1][v2];
}
//显示图对应的矩阵
public void showGraph(){
for (int[] edge : edges) {
System.out.println(Arrays.toString(edge));
}
}
public static void main(String[] args) {
int n = 5; //结点个数
String[] vertexs = {"A","B","C","D","E"};
Graph graph = new Graph(n,true);
//添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//添加边
//A-B A-C B-C B-D B-E
graph.insertEdges(0,1,1);
graph.insertEdges(0,2,1);
graph.insertEdges(1,2,1);
graph.insertEdges(1,3,1);
graph.insertEdges(1,4,1);
//显示邻接矩阵
graph.showGraph();
}
}
4.总结
这篇主要介绍了图的基本概念，图的两种存储方式，以及用邻接矩阵存储图的代码实现。关于图的邻接表存储方式，就不在用代码实现，下一篇介绍图的遍历。
本人微信公众号，点关注，不迷路
网友评论