什么是图

• 表示多对多的关系
• 包含：
  • 一组顶点（vertex）
  • 一组边（edge）
  • 不考虑重边和自回路

图的表示方法

• 邻接矩阵。
  

  

  邻接矩阵结构
  
  用一个矩阵来表示两个顶点之间是否有边存在，或者存储边的权值。
  优点：直观，方便检查定点之间是否存在边，方便计算度。
  缺点：在表示无向图的时候，浪费了一半的存储空间，当为稀疏举证的时候，内存利用效率也不高。 对于无向图只保存n(n+1)/2个元素（下三角元素个数），那么访问i行j列元素，可以访问下标为i(i+1)/2位置的元素。所以邻接矩阵的主要问题在于空间利用率低。
  遍历时间复杂度：O(n^2)。

• 邻接表。
  

  

  邻接表结构
  
  所有节点保存在顺序数组中（节点信息），链表存储每个节点的相邻节点（边的信息），有多少个节点就构成多少个链表。
  优点：方便访问邻接点，在稀疏图中，一定程度上可以节省内存，对于无向图方便计算定点的度。
  缺点：对于有向图，只可以计算出度。需要构造逆邻接表来计算入度，检查任意两个顶点之间是否存在边，是不太方便的。并且要访问一个节点或者判断两个顶点之间是否有边都不容易，需要遍历整个表。并且在无向图中，每个边都被重复存储了两遍。
  遍历时间复杂度：O(v+e)

• 十字链表

  
  
  

  十字链表结构
  
  

  将邻接表和逆向邻接表统一在一个表里。在这个结构中，对出度入度的操作就十分方便。唯一的缺点在于，结构比较复杂。

图的遍历

将途中所有的顶点访问一遍，且没有重复访问。遍历策略主要是基于深度优先或者广度优先。

深度优先搜索（DFS）

st=>start: 开始
e=>end: 结束
st->e->

时间复杂度：再不同的存储方式中，时间复杂度是不同的。

广度优先搜索（BFS）

时间复杂度同深度优先搜索是一样的。

优缺点比较：

• dfs使用比bfs更加广泛，原因是dfs递归的编写方式更容易实现。

• dfs实现过程中使用的是堆栈，bfs使用的是队列。
• dfs由于是递归，所以图的规模较大时，会有溢出的风险。
• 一般情况下，使用dfs能解决的问题，bfs同样可以解决。
• 一般dfs用于连通性检查，bfs用于最短路径搜索。

连通分量：是图（无向图）的一个子图且它是连通的，再增加一个定点后者一条边，它都变的不在连通（“极大”的意思）。
强连通：（有向图）两个顶点之间，a和b之间存在双向路径。a可以到b，b也可以到a。
弱连通：不是强连通，但是是连通的。
强连通分量：有向图的极大强连通分量。

对于实际问题中重要的是抽象出什么图的顶点，什么是图的边