图

图表示多对多地关系。包含

• 一组顶点：通常用V表示顶点集合。
• 一组边：通常用E表示边的集合。
  • 边是顶点对：（v,w）∈E，其中v，w∈V
  • 有向边表示从v指向w的边（单行线）
  • 不考虑重边和自回路

常见术语

图中所有路径都是右方向的称为无向图，有方向的称为有向图。

顶点的度指顶点相连接的边的条数。在有向图中，入度表示有多少条边指向这个顶点。出度表示有多少条边是以这个顶点为起点指向其他顶点。带权重的图称为网络。

图的表示

邻接矩阵

• 使用二维数组来存储，若有边为1，无边则为0。如果用一个长度为N(N+1)/2的1维数组A存储，则Gij在A中对应的下标是(i*(i+1)/2+j)
• 好处
  • 直观、简单、好理解
  • 方便检查任意一对顶点间是否存在边
  • 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
  • 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
    • 无向图：对应行非0元素的个数
    • 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”。
• 坏处
  • 浪费空间，存稀疏图有大量无效元素

邻接表

• G[N]维指针数组，对应矩阵每行一个链表，只存非0元素。
• 好处
  • 方便找任一顶点的所有邻接点
  • 节约稀疏图的空间
  • 对于无向图方便计算任一顶点的度，对于有向图只能计算出度，需要构造逆邻接表来方便计算入度。
  • 不方便检查任意一堆顶点间是否存在边。

图的遍历

深度优先搜索(DFS)相当于树的先序遍历。
广度优先搜索相当于树的层序遍历。，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后 是次近的，依次往外搜索。

广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终 止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先 搜索的时间复杂度都是O(E)，空间复杂度是O(V)。

最短路径问题的抽象
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径，第一个顶点为源点，最后一个顶点为终点。

无权图的单源最短路算法
按照递增的顺序找出到各个顶点的最短路。相当于BFS。