数据结构 - 图

---

目录：

• 基本概念
  • 无向图
  • 有向图
• 储存结构
  • 邻接矩阵
  • 邻接表
  • 十字链表（有向图）
  • 邻接多重表（无向图）
• 图的遍历
  • 深度优先搜索
  • 广度优先搜索
  • 最小生成树
    • 普里姆算法（Prim）
    • 克鲁斯卡尔算法（Kruskal）
• 最后

---

基本概念

图是由结点和他们之间连线的集合

无向图

无向图.png
无向图解析.png

• 连通图：当任意一个结点都能直接或间接到其他全部结点的时候，就称为连通图
• 完全图：边数 = 顶点数 *（ 顶点数 - 1 ） / 2
• 生成树 ： 边数 = 顶点数 - 1

有向图

有向图.png 有向图解析.png

• 上图，V1的出度是2，入度是1
• 权值：一条连线所代表的值
• 当两个结点互相指向，那么就等于一条直线

---

储存结构

储存结构.png

邻接矩阵

使用数组的形式来储存数据

• 在有向图中，当一个顶点能够指向另外一个顶点，则矩阵中的值为1，否则为0

有向图邻接矩阵.png

• 在无向图中，边是相当于两个顶点相互指向

无向图邻接矩阵.png

• 代码中邻接矩阵表示 ： int[][] martix ;

邻接表

使用顶点以及其弧的指向来储存数据

邻接表存储.png

• 顶点索引：顶点的唯一标识
• 出弧链表头指针： 顶点指向其他顶点的连接
• 顶点数据：顶点储存的数据
  </br>
• 在代码中，邻接表的结构表示

邻接表代码构造.png

十字链表（有向图）

使用顶点以及其弧的指向来储存数据

十字链表数据储存.png

这里以V1顶点为例说明：

• 顶点索引：0
• 顶点数据：1（假定的）
• 以该顶点为弧尾的弧的结点指针： V1 -> V3， V1 -> V2, V1 -> V4
• 以该顶点为弧头的弧的结点指针： V4 -> V1
  这里以V1 -> V4 的弧为例说明：
• 弧尾顶点索引：0
• 弧头顶点索引：3
• 弧尾相同的下一条弧的指针： V1 -> V2 , V1 -> V3
• 弧头相同的下一条弧的指针： V3 -> V4
• 弧的数据：V1V4(假定的)
  </br>
• 代码实现的结构：

十字链表代码构造.png

邻接多重表（无向图）

使用顶点以及边的连接指向来储存数据

邻接多重表数据储存.png

顶点表示很清晰简单
这里以V1 ->V4边为例说明：

• A点索引 ： 0（V1）
• B点索引：3 （V4）
• 与A点相连接的下一条边的指针： V1 -> V2 或者 V1 -> V3, 取决于哪一条更早建立连接
• 与B点相连接的下一条边的指针 ： V3 -> V4
  </br>
• 代码实现的结构：

邻接多重表代码构造.png

---

图的遍历

实例-图.png

深度优先搜索

对于上图
从A顶点开始进行深度优先搜索的顺序为：
A - B - C - E - F - D - G - H
丢弃了 F - B , H -D 这两条边，形成了一棵树

• 规则：
  顺着一个顶点不断向下搜索，当搜索到的顶点与前面搜索过的顶点形成环的时候就停止
  有点类似树的前序遍历

广度优先搜索

对于上图
从A顶点开始进行广度优先搜索的顺序为：
A - B - D - C - F - G - H - E
丢弃了E - F 和 G - H 这两条边，形成了一棵树

• 规则：
  按层来不断进行搜索

最小生成树

当遍历的时候涉及边的权值问题，就要使用最小生成树来解决

最小生成树前.png

如图：上面的数值是边的权值，可以理解为修路的成本，每个顶点可以理解为一个城市，如何最节约成本完成城市之间的连通就需要使用最小生成树。
最小生成树后：

最小生成树后.png

普里姆算法（Prim）

普里姆算法（Prim）.png

过程：

1. 选定一个点A，放入点集合
2. 关于A的所有的边放入 待选边集合
3. 从待选边集合选取权值最小的边 A - F (1)，放入边集合
4. 边集合中提取出未在点集合的点F，放入点集合
5. 刷新待选边集合，列出所有A和F有关的边
6. 选出权值最小且不会与当前已选边形成闭环的边，然后放入边集合
7. 以此类推，得出所有边，既是最小生成树

Prim算法后：

普里姆算法（Prim）后.png

克鲁斯卡尔算法（Kruskal）

克鲁斯卡尔算法（Kruskal）.png

过程：

1. 列出所有边的集合
2. 依次选取权值最小的边，同时将涉及的点加入点集合
3. 选取的边不能与已选边构成闭合
4. 当点集合中出现了所有点以后，需要让所有点能连通，形成生成树（边 = 点 - 1）

Kruskal算法后：

克鲁斯卡尔算法（Kruskal）后.png

---

最后
对数据结构的基本认识和理解到这里就结束了
关于图的代码实现，在有了队列，栈，线性表的实践过后，代码的转换肯定是没问题的
重点在于对上面所说知识点的深入理解和逻辑转换
再次感谢慕课网的James老师
PS:
后面我会写一写，从零开始的Android组件化开发的记录博文