图

目录

• 是什么
• 表示方式
• 搜搜算法
• 应用

图

图是一种非线性数表据结构，比树复杂。图由顶点、边构成，涉及：度（出度、入度）、权重等概念。

元素&概念

• 顶点
  树中的元素我们称为节点，图中的元素我们就叫做顶点（vertex），上图中A-F都称为顶点。
• 边
  一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边（edge）,图中1-9标识的是边。
• 度
  一个顶点有条边，就叫做这个顶点的度。顶点A有2条边，可以描述为顶点A的度为2。在有向图中顶点可以为起点、也可以为终点。可以称为：
  • 出度，顶点为起点。
  • 入度，顶点为终点。

分类

• 图，包含：顶点、边
• 有向图，边增加方向属性
• 带权图，边增加权重属性
• 稀疏图，顶点很多、每个顶点的边很少

表示方式

邻接矩阵

• 2维数组
• 无向图,{a,b}、{b,a}同时标记1
• 有向图,{a,b}标记1
• 带权图,{a,b}标记权重值

邻接表

针对上面邻接矩阵比较浪费内存空间的问题，我们来看另外一种图的存储方法，邻接表（Adjacency List）。

• 链表可以优化为红黑树

无向图使用邻接表标识如下：

搜索算法

算法是作用于具体数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。搜索算法有：

• 深度优先(DFS)
• 广度优先(BFS)
• A*
• IDA*

深度优先

广度优先

应用

微博用户关系

微博用户关系特点：

• 方向性、A关注吧，B不一定关注A
• 稀疏图、海量用户，每个用户关注并不多
• 功能性
  • 字母排序，分页查看我关注的用户
       - 字母排序，分页查看关注我的用户
       - 关注用户A
       - 取消关注用户A
• 推荐2、3度好友

微信用户关系

微信用户关系特点：

• 无方向性、A是B的好友，B一定是A的好友
• 稀疏图、海量用户，每个用户最多5000好友
• 功能性
  • 字母排序，分页查看我的好友
       - 删除好友
       - 申请添加好友