数据结构 - 图
目录：
- 基本概念
- 无向图
- 有向图
- 储存结构
- 邻接矩阵
- 邻接表
- 十字链表（有向图）
- 邻接多重表（无向图）
- 图的遍历
- 深度优先搜索
- 广度优先搜索
- 最小生成树
- 普里姆算法（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
过程：
- 选定一个点A，放入点集合
- 关于A的所有的边放入 待选边集合
- 从待选边集合选取权值最小的边 A - F (1)，放入边集合
- 边集合中提取出未在点集合的点F，放入点集合
- 刷新待选边集合，列出所有A和F有关的边
- 选出权值最小且不会与当前已选边形成闭环的边，然后放入边集合
- 以此类推，得出所有边，既是最小生成树
Prim算法后：
普里姆算法（Prim）后.png
克鲁斯卡尔算法（Kruskal）
克鲁斯卡尔算法（Kruskal）.png
过程：
- 列出所有边的集合
- 依次选取权值最小的边，同时将涉及的点加入点集合
- 选取的边不能与已选边构成闭合
- 当点集合中出现了所有点以后，需要让所有点能连通，形成生成树（边 = 点 - 1）
Kruskal算法后：
克鲁斯卡尔算法（Kruskal）后.png
最后
对数据结构的基本认识和理解到这里就结束了
关于图的代码实现，在有了队列，栈，线性表的实践过后，代码的转换肯定是没问题的
重点在于对上面所说知识点的深入理解和逻辑转换
再次感谢慕课网的James老师
PS:
后面我会写一写，从零开始的Android组件化开发的记录博文
网友评论