数据结构,图_数据结构完全图是什么

前言

一. 图的基本概念

二. 图的存储方式

     1. 邻接距阵存储

     2. 邻接表存储图

     3. 十字链表

三. 图的实际应用

    1. 存储微信或微博的好友关系

四. 图的遍历

      广度优先遍历（BFS）

      深度优先遍历简称 DFS

五. 学习过程中的疑问

前言

    相信大家都有听过《哥尼斯堡七桥》这个故事吧，正是这个故事引出了数学中的一个新分支—图论。

    引用百度百科《七桥问题》的图如下所示

    其实，在进行图学习之前，由于笔者的孤陋寡闻，只是在记忆中记得大学时好像有学习过图的一些知识。出来工作四年之久，但都未尝直接运用过图，因此对于图这种数据结构到底运用于编程中基本是空白的。

    在开始学习图之前，先考虑下如何存储微博或微信等社交网络好友的关系呢？

一. 图的基本概念

   什么是图：图(Graph )是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G (V,E )，其中，G表示一个图,，V是图G中顶点的集合，E是图G中边的集合。

   图(Graph)是一种比线性结构和树形结构更加复杂的数据结构。图研究的对象是多对多的关系，线性表是一对一，树是一对多。

  顶点 (vertex)：图中的元素；

  边 (Edge)：顶点与顶点之间的相连关系；

  无向图：顶点与顶点之间没有指向关系的图；

  度：表示一个顶点与多少个顶点连接或者说其有多少条边；

  如下图所示：下图各顶点之间并没有指向问题，为无向图，图中的每个字母为一个顶点，每个顶点与其他顶点相连形成的边则为图的边。以 A 顶点为例，其总共与BCD三个顶点相连，说明 A 的度为3，边数也为3。

有向图：顶点与顶点之间有指向的关系的图；如下图所示：

对于有指向关系的图，为了方便描述顶点与其他顶点的关系而引入了出度与入度的概念。

入度（Indegree）：顶点的入度表示有多少条边指向这个顶点；如上图 A 顶点为入度为 1。

出度（OutDegree）：顶点的出度表示有多少条边以该顶点为起点; 如上图 A 顶点的出度为 2。

    对应到微博中，入度就相当于有多少人关注了你，出度就相当于你关注了多少人。

带权图（通常也称为网）：顶点之间的边上带有权重的图；如下图所示：

例如 中好友之间还保存了好友之间的亲密关系，比如两个人经常联系则表示比较亲密（权重数高一点），像这样就关系就比较适合用带树图来表示了，其中权重表示亲密度。

带权有向图：对应带权无向图而言就是顶点与顶点之间多了指向；

二. 图的存储方式

    对于图来说常用的存储方式主要是邻接距阵与链表式存储了。

1. 邻接距阵存储

     原理：邻接矩阵的底层依赖一个二维数组。

     无向图：顶点 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] 为1 那么 A[j][i] 必定也为1，也就是说其实对于无向图只需要存储距阵中对应的一半元素则可，另外一半的空间就完全是浪费了。

   因此，对于稀疏图（顶点很多，但是顶点之间的形成的边并不多），例如微信用户有上亿，但每个用户的好友数一般只有几百，这样的数据构成的图则不适合用邻接距阵的方式进行存储，因为会造成相当大的空间浪费。那么对于这类图，我们可以通过什么方式进行存储呢？

2. 邻接表存储图

   通过数组与链表结合的存储方法就称为邻接表存储，其中，顶点存储在一维数组中，每个数组单元存储一个顶点与其指向的第一个链表指针。顶点与其他顶点形成的关系存储成单链表。（当然这里的数组其实也可以换成单链表）。

一图胜千言，如下图便是邻接表存储图了

   通过上图，感觉这似乎跟散列表一个样呀？

   邻接表存储图说明：每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。

   如上图为有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。

   对于无向图来说，也是类似的，不过，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。

   在学习散列时，为了解决散列冲突的问题，当链表过长时，为了加快检索的效率，我们会将链表转变成红黑树，由于该链表基本上跟散列表一个原理，因此也可以对该链表类似进行类似于散列表形式的优化。

   通过邻接表，我们可以很方便地找出每个顶点的出度，但是如果要找顶点对应的入度就特别麻烦了。比如上图，要查找有那些顶点指向 1 号顶点，这时只能是遍历整个邻接表了。因此，这里便引入了，逆邻接表。

逆邻接表：基本原理与邻接表一样，唯一的区别是邻接表存储的是顶点指向其它顶点的关系（或者说是顶点与其他顶点的出度关系），逆邻接表刚好相反，其存储的是顶点的入度关系。如下图所示：

  逆邻接表数组依然是存储顶点，但是链表存储的是那些节点指向了该顶点。

  有了逆邻接表后，当要查找有那些顶点指向 1 号顶点，直接查找逆邻接表就可以了。

  总结：邻接距阵与邻接表存储图的优缺点

  邻接距阵：基于数组存储，操作起来方便，比如将图相关的计算可转变成距阵的计算，很容易计算会每个顶点的度。但缺点是对于无向图或稀疏图如果用邻接距阵的方式就比较浪费存储空间。

  邻接表：操作起来没有邻接距阵那么快速与方便，查找某个顶点的出度还算方便，但是寻找顶点的入度就需要遍历整个邻接表了，优点是对于顶点多边少的稀疏表其占用空间小。

   通过上述邻接表与逆邻接表是可以快速实现查找顶点的出度也入度，但是对于每份数据需要存储两份，以及每插入一个数据时都需要维护正反邻接表，那么有没有什么方法可以其进行优化呢？这里就引入了十字链表。

3. 十字链表

    十字链表长什么样呢？用最直观的示意，是下面这样：

注：上图只是十字链表的一个示意图，真正的十字链表并不是这样的，但其实现的功能基本是这样的。（引自小灰漫画）

   不过，上图只是一个便于理解的示意图，我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中，链表的每一个节点不再是顶点，而是一条边，里面包含起止顶点的下标。

  十字链表节点和边的对应关系，如下图所示：

   因此，优化之后的十字链表，是下面这个样子：

     图中每一条带有蓝色箭头的链表，存储着从顶点出发的边；每一条带有橙色箭头的链表，存储着进入顶点的边。初学十字链表的时候，可能会觉得有些乱。

三. 图的实际应用

1. 存储微信或微博的好友关系

    对于微信来说，只有互相关注(暂且忽略其中一方被删除了的情况)，因此其形成的图是无向图，而微博为有向图。这里以微博为例说明：数据结构是为算法服务的，因此具体选择那种算法，与实际业务是有直接关系的，这里以如下业务场景来说明存储微博好友的关系，场景如下：

1. 判断用户A是否关注了用户B;
2. 判断用户A是否是用户B的粉丝;
3. 用户A关注用户B;
4. 用户A取消关注用户B;
5. 根据用户名称的首字母排序，分页获取用户的粉丝列表;
6. 根据用户名称的首字母排序，分页获取用户的关注列表。

   对于上述的场景，由于社交图是一种稀疏图，因而很自然地选择了邻接表的方式进行存储；

   这里有一个问题是，如果单纯用一个邻接表进行存储，获取指定用户关注了那些用户或用户的关注列表这方面是很容易求出。

   但如果要获取一个用户是否是另一个用户的粉丝或用户的粉丝列表就比较麻烦了，因此这里引入逆邻接表。

    邻接表存储了用户的关注关系，逆邻接表存储了用户被关注的关系；从图的定义上来说，邻接表表示的是顶点的出度，逆邻接表表示的是顶点的入度。

    当我们要查询指定用户关注了那些人则查邻接表，查询指定用户的粉丝则查逆邻接表。如下图所示：

   对于微博来说：为了快速查找用户之间的关系，由于单链表遍历只能从头开始遍历，因此基础的邻接表应该比较难以满足这个需求。在这里了，为了提升对链表的遍历速度，我们可以对邻接表进行升级改造，如将普通的单链表升级为跳表或平衡二叉树等（这个操作有点类似与JDK8 升级后的HashMap，HashMap当散列表中链表长度超过8后便将该链表转换成红黑树）；

   因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构再合适不过了。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是O(logn)，空间复杂度上稍高，是O(n)。

   最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。

   如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。

   但是如果像微博那样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。

   我们可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。

   如下图，在机器1上存储顶点1, 2, 3 的邻接表，在机器2上,存储顶点4, 5的邻接表。同理，逆邻接表的处理方式也一样。

  当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器,然后再在相应的机器上查找。

  当然，我们还可以将上述信息存储到硬盘中，如数据库。

  总结：在数据量比较大的情况下，为了加快链表的遍历，我们可以对邻接表进行升级改造，例如将链表改造成跳表、平衡二叉树等。

2. 图还可以应用在一些导航图或城市规划等形成的加权图；

3. 做为一些图数据库的底层思想存在；

四. 图的遍历

   图的遍历主要有深度遍历与广度遍历，深度优先遍历简称 DFS（Depth First Search），广度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种方式。

广度优先遍历（BFS）

   原理：类似“地坛式”的进行一层层由内到外的搜索，即从查询起点开始，先查近它最近的，然后依次向外扩展；其实这个类似树的层序遍历，示意图，如下图所示：

深度优先遍历简称 DFS

   假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

   走迷宫的例子很容易能看懂，我们现在再来看下，如何在图中应用深度优先搜索，来找某个顶点到另一个顶点的路径。你可以看我画的这幅图。

    搜索的起始顶点是s，终止顶点是t，我们希望在图中寻找一条从顶点s到顶点t的路径。如果映射到迷官那个例子， s就是你起始所在的位置， t就是出口。我用深度递归算法，把整个搜索的路径标记出来了。这里面实线箭头表示遍历，虚线箭头表示回退。从图中我们可以看出，深度优先搜索找出来的路径，并不是顶点s到顶点t的最短路径。

   实际上，深度优先搜索用的是一种比较著名的算法思想-回溯思想。这种思想解决问题的过程，非常适合用递归来实现。

遍历的代码实现

如下，引用小灰漫画中的代码

package test; import java.util.LinkedList; /** * 图的顶点 */ class Vertex { int data; Vertex(int data) { this.data = data; } } /** * 图（邻接表形式） */ class Graph { private int size; private Vertex[] vertexes; private LinkedList<Integer> adj[]; Graph(int size) { this.size = size; // 初始化顶点和邻接矩阵 vertexes = new Vertex[size]; adj = new LinkedList[size]; for (int i = 0; i < size; i++) { vertexes[i] = new Vertex(i); adj[i] = new LinkedList(); } } /** * 深度优先遍历 */ public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for (int index : graph.adj[start]) { if (!visited[index]) { dfs(graph, index, visited); } } } /** * 广度优先遍历 */ public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue) { queue.offer(start); while (!queue.isEmpty()) { int front = queue.poll(); if (visited[front]) { continue; } System.out.println(graph.vertexes[front].data); visited[front] = true; for (int index : graph.adj[front]) { queue.offer(index); } } } public static void main(String[] args) { Graph graph = new Graph(6); graph.adj[0].add(1); graph.adj[0].add(2); graph.adj[0].add(3); graph.adj[1].add(0); graph.adj[1].add(3); graph.adj[1].add(4); graph.adj[2].add(0); graph.adj[3].add(0); graph.adj[3].add(1); graph.adj[3].add(4); graph.adj[3].add(5); graph.adj[4].add(1); graph.adj[4].add(3); graph.adj[4].add(5); graph.adj[5].add(3); graph.adj[5].add(4); System.out.println("图的深度优先遍历："); dfs(graph, 0, new boolean[graph.size]); System.out.println("图的广度优先遍历："); bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>()); } } 

运行结果如下所示：

图的深度优先遍历： 0 1 3 4 5 2 图的广度优先遍历： 0 1 2 3 4 5

五. 学习过程中的疑问

疑问一：

    在学习图的邻接距阵存储的时候，其实有一个疑问我们要如何确定图中各顶点的位置关系，也就是说那个顶点对应数组中的那个位置？从而画出其对应的距阵图。

   其实有上述疑问，主要原因还是对图这种数据结构的定义不是那么清晰而引起的。对于图这种数据逻辑数据结构，其实它的任何一个顶点都可以说是图的第一个顶点，因此任何一个顶点与顶点之间的邻接关系（或边）也是不存在次序的。如下图仔细观察会发现它们都是同一个图（此处引用《大话数据结构》的部分内容），只是表象不一样罢了。

    对于图这种复杂的数据结构，任意两个顶点之间都可能存在着关系，因此不可能通过元素在物理内存中的位置关系来表示元素之间的关系。

   考虑到图是由顶点与边或弧两部分构成。合起来表示比较困难，因此很自然地想起用两种数据结构来存储它们。我们可以用一维数组不分次序存储顶点，然后用二维数组存储存储顶点与顶点之间的关系。引用《大话数据结构》一书的图如下所示：

    通过上图，我们可以知道二维数组的次序可以通过顶点对应的一维数组来确定，而顶点对应的一维数组是与顶点次序无关的。      通过上图我们还可以知道对于任一顶点的出度是通过将该顶点的行求和，入度则是列求和。

疑问二：为什么需要学习图这种数据结构呢？

   1. 线性表与树这些结构只能表示一对一或者一对多的关系，而图可以表示更加复杂的关系，比如多对对，因此引入图可以增强对关系的表示。

   2. 现如今有很多现成的图算法，当需要用到时只需要简单引用便可，大大减少了开发成本。

注：了解更多数据结构知识

该系列博文为笔者学习《数据结构与算法之美》的个人笔记小结

参考

漫画：什么是 “图”？（修订版）

漫画：深度优先遍历 和 广度优先遍历

数据结构：图（Graph）

《大话数据结构》

今天的文章
数据结构,图_数据结构完全图是什么分享到此就结束了，感谢您的阅读。