什么是图？

• 图结构是与树结构有相似的数据结构
• 图论是数学的一个分支，并且，在数学的概念上，树是图的一种
• 它以图为研究对象，研究顶点和边组成的图形的数学理论和方法
• 主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系

一组顶点：通常用V(Vertex)表示 表示顶点的集合
一组边：通用用E(Edge) 表示边的集合
边是顶点和顶点之间的连线
边可以是有向的，也可以是无向的
例如A—-B 是无向的
A—->B 是有向的 A可以去B 但是B不可以去A 是单向的

术语

• 顶点：表示图中的一个节点
• 边：表示顶点和顶点之间的连线
• 相邻节点：由一条边连接在一起的顶点称为相邻节点
• 度：相邻节点的数量
• 路径
  • 简单路径：不包含重复节点
  • 回路：第一个顶点和最后一个节点是相同的节点
• 有向图：边是有方向的
• 无向图：任何边没有方向
• 无权图：图中的边是没有其它意义的，就只有是顶点间的连接意义
• 有权图：每条边有权重，权重不同，规划的路径就不一样，权重代表的意义不一样例如地图上，权重就是距离等
• 稀疏图：顶点和顶点之间的边非常少

图的表示

一个图包含很多顶点，另外包含顶点和顶点之间的连线，也就是边

边的表示 邻接矩阵

邻接矩阵让每一个节点和一个整数相关联，该整数作为数组的下标值
我们用一个二位数组来表示顶点之间的连接

在二维数组中，0表示没有连线，1表示有连线
通过二维数组，可以很快的找到一个顶点和哪些顶点有连线
比如A顶点，直接遍历第一行就好了
A-A，B-B 顶点到自己的连线，就是自回路，用0表示
如果每条边有权重，改成>0的数字即可，因为0表示没有连线

问题：
稀疏图是严重的问题，矩阵中存在大量的0，造成空间的浪费

邻接表

邻接表是由图中每个顶点以及顶点相邻的顶点列表组成
列表可以采取很多种方式来存储，例如数组、链表、字典等都可以

出度：指向其他顶点的数量
入度：别的顶点指向自己的数量

问题：
计算“出度”是比较简单的。
计算“入度”就需要遍历每一个顶点，看看有没有指向自己

逆邻接表

和正邻接表不同的是，存储的是指向自己的顶点

图的遍历

需要将图中每个顶点访问一遍，并且不能有重复的访问

遍历算法

• 广度优先搜索(Breadth-First Search 简称BFS)
  • 基于队列，入队列的顶点先被探索

会从第一个顶点开始遍历图，先访问其所有的相邻点，就像依次访问图的一层

• 深度优先搜索(Depth-First Search 简称DFS)
  • 基于栈或使用递归，同过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问

都需要明确指定第一个被访问的顶点