image.png

  1. 图，是一种数据结构
  2. 集合只有同属于一个集合，线性结构存在一对一的关系，树形结构一对多的关系，图形结构，多对多的关系。
  3. 微信中：许多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构当中的图。
  4. 导航的最优路径：耗时最少，路程最短的路径，推荐一个方便最快捷的路线，其实就是把经过的地方看作图上的一个一个的点，从起点出发，与另外的一个点或者其他的点产生了关联。
  1. 图的概念：
  2. 图：是一种比树更为复杂的数据结构，树节点之间是一对多的关系，并且存在着一个父与子的层级划分。多对多的关系，并且所有的点都是平等的，无所谓谁是父亲谁是儿子。在图里面最基本的单元是顶点（vertex）；顶点相当于树中的结点，顶点之间的关系：被称为边（edge）
  3. 自环：即一条连接一个顶点和自身的边
  4. 平行边：连接同一对顶点的两条边（也有可能是多条边）

image.png

  1. 图的分类：
  2. 按照连接的两个顶点的边的不同，可以把图分为以下几种：
  3. 1、无向图：边没有方向的图称为无向图，边的作用仅仅是连接两个顶点，没有其他的含义
  4. 2、有向图：边不仅连接两个顶点，并且具有方向性，可能是单向也可能是双向的
  5. 3、带权图：边可以带权重

image.pngimage.png

  1. 图的术语：
  2. 1、相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相连的，并且是依附于这两个顶点的。
  3. 2、度：某个顶点的度：是依附于这个顶点的边的个数
  4. 3、子图：一幅图中，所有边的子集组成的图，包含这些边的依附的顶点
  5. 4、路径：是由边顺序连接的一系列的顶点组成
  6. 5、环：是一条至少含有一条边且终点和起点相同的路径
  7. 6、连通图：如果图中，任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图我们称之为连通图。
  8. 7、连通子图：一个非连通图由若干个连通的部分组成，每一个连通的部分就可以称为该图的连通子图

image.png
image.png

  1. 1和3是相邻的，这条边依附于1和3
  2. 1顶点度：3
  3. 从7到9，会经过1，3，5这些顶点，这个叫路径
  4. 1，4，7组成叫做环
  1. 欧拉七桥
  2. 欧拉开创了新的学科：图论
  1. 图的存储结构：
  2. 1、顺序存储
  3. 2、链式存储
  4. 线性表：它仅有的关系就是线性关系
  5. 树形结构：有清晰的层次的结构
  6. 图形结构：集合中的每一个元素都有可能有关系
  7. 图是由顶点和边构成的，所以在图里边：要存储的图形结构的信息，无非就是存储图的顶点和图的边
  8. 顶点可以直接用数组去存储
  9. 边存储起来就比较麻烦了
  10. 存储结构：
  11. 1、邻接矩阵
  12.     矩阵是一个按照长方阵列排列的负数或者实数集合。
  13.   N*M数据的集合（九宫格）
  14.     去除表格线的九宫格就是矩阵的样式，矩阵是由行和列组成的一组数表。
  15.   邻接矩阵让每一个结点和整数相关联
  16.   用1来表示顶点与顶点有直接的关系，用零表示顶点之间没有关系
  17.   优点：表示非常明确，有向图：A->D:1
  18.     缺点：非常浪费计算机的内存，存储了太多0
  20. 2、邻接表
  21.     邻接表：由图中的每个顶点以及和顶点相邻的顶点列表组成，数组/链表/字典

邻接矩阵

image.png

邻接表

image.png

  1. 解析：A与B、C、D连接，B与A、E、F连接...

图的遍历

  1. 1、遍历：从某个结点出发，按照一定的搜索路线，依次访问数据结构中全部结点，而且每个结点访问一次。
  3. 2、二叉树中：树的遍历，从根节点出发，按照一定的访问规则，依次访问树的每个结点信息
  4.     （1）先序遍历
  5.   （2）中序遍历
  6.   （3）后序遍历
  7.   （4）层级遍历
  9. 3、广度优先遍历（BFS）
  10. 优先横向遍历图，广度优先的思想，从图中的某个顶点v出发，在访问了v以后，依次去访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发，依次访问他们的邻接点。
  11. 注意：图没有横向和纵向的概念
  13. 4、深度优先（DFS）
  14. 优先纵向遍历图，有一个递归的概念
  16. 5、图遍历的思路
  17.     （1）每一个顶点有三种状态
  18.           1、未发现（没有发现这个顶点）
  19.       2、已经发现（发现其他的顶点连接到这里，但是没有去查找这个顶点的全部连接的顶点）
  20.       3、已经探索（已经发现这个顶点连接的全部顶点）
  21.   （2）记录顶点是否被访问过，使用三种颜色来反映他们的状态
  22.           1、白色（未发现）
  23.       2、灰色（已经发现）
  24.       3、黑色（已经探索）
  25.   （3）广度优先的遍历过程
  26.           1、发现未发现顶点后，存放队列中，等待查找，并且将这些顶点标记为已发现
  27.       2、在队列中拿出已经发现的顶点，开始探索全部顶点，并且要跳过已经探索的顶点
  28.       3、遍历完这个顶点以后，将这个顶点标志为已经探索
  29.       4、循环在队列中探索下一个顶点
  30.   （4）深度优先的遍历过程
  31.           广度优先算法我们使用的是队列，深度优先的原理：使用递归
  32.       1、从某一顶点开始查找，并且将这个顶点标记为已经发现（灰色）
  33.       2、从这个顶点开始探索其他的全部的顶点，并且跳过已经发现的顶点
  34.       3、遍历完这个顶点以后，将这个顶点标记为已经探索（黑色）
  35.       4、递归返回，继续探索下一个路径的最深顶点

广度优先遍历（BFS）

image.png

深度优先遍历（DFS）

image.png

最短路径

  1. 1、路径：由边顺序连接的顶点组成的
  2.         寻找最短路径，所谓的最短路径指的是：如果从图中某一个顶点（起点，圆点）到达另外一个顶点（终点）路径不可能只有一条，如何找到一条路径使得沿这个路径的边上的权值总和（路径长度）达到最小。
  4. 2、回溯点
  5. 回溯点是离上一个顶点最近的顶点
  6. 回溯路径（所有的回溯点组成，回溯路径）
  8. 3、两种比较常见的求最短路径的算法
  9.     （1）迪杰斯特拉算法，是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径的问题
  10.     （2）Floyd算法，经典的动态规划算法