概念

• 强连通图：如果在一个有向图中任意两个顶点可以相互到达，则称这张图为强连通图；
• 弱连通图：反之，若不满足强连通图的定义，但是将所有的有向边修改为无向边后原有向图能构成连通图，则称该有向图为弱连通图。

图存储

• 集合的方式：
  • 维护两个集合，即一个顶点集合V和一个边集合E。
  • 顶点集合中保存了所有顶点的信息以及序号，边集合保存了被一条边连通的两个顶点的序号以及边的代价（无权图可认为每一条边代价都是一样的）。
  • 由于稀疏图占了日常生活中的图的绝大多数，因此集合的方式是保存图的主要方式。
  • 必须以O(N)的代价进行查找任意两个节点之间的连通情况
  • 入度和出度，边集合往往只能快速统计其中的一项，而统计另一项开销较大
• 矩阵的方式：
  • 矩阵的方式取消了边集合，改用一个矩阵保存每两个顶点之间的代价。
  • 顶点与自己的代价是0，与邻居的代价已知，与不直接相连的顶点代价为无穷大。
  • 只有在绝大多数顶点都彼此直接相连的情况下，矩阵的方式才能更节省空间。
  • 是更直观的，可以以O(1)的代价查找任意两个节点之间的连通情况
  • 在统计入度和出度上矩阵的方法看上去也更快。根据具体需求选择时间换空间或者空间换时间是算法选取的一大原则。
• 矩阵的链式存储
  • 为了节省矩阵的空间开销，矩阵的链式存储应运而生。
  • 这种方法只关心矩阵中存在的元素，而忽略不存在的元素。
  • 每一个矩阵会被存储为一个行数组和一个列数组，以及一系列节点。
  • 两个数组中的每个元素各带有一个指针，指向该行或该列的第一个元素；每个节点保存了行号和列号，同时带有两个指针，分别指向该行的直接后继和该列的直接后继。
  • 使用这种结构的矩阵平衡了空间和时间的开销，对于稀疏矩阵提升尤其明显，但是随着矩阵中元素数量的增加效率会降低。
• 邻接表
  • 集合的方式这边也拿出了邻接表来进行快速查找。
  • 邻接表就是很简单的使用链表，为每一个节点建立一个链式的出度表，从而达到快速查找的目的。如果需要统计入度，那么应同时维护一张逆邻接表来对入度建立索引。当然，无向图可以把出度和入度混在一起记录，反正是无向的。
  • 为了克服需要同时维护两张表的缺陷，人们发明了十字链表和邻接多重表，分别用于处理有向图和无向图。十字链表将每一条边作为节点，这个节点记录弧头和弧尾，同时拥有一个head指针和一个tail指针；每个顶点也拥有两个指针，一个指向第一条入度的边，另一个指向第一条出度的边。
  • 使用时，顶点的入度指针沿着head指针一路找过去，完成对入度的遍历；而出度指针沿着tail一路找过去，完成对出度的遍历。我本来不太喜欢画图的，但是这东西不用图讲不明白了：
  • 考虑这样一张有向图，并假设顶点集合和边集合都已经整理好了。那么，根据这两个集合，我们可以建立十字链表：其中绿色的就是入度指针。从图中我们可以看出顶点A的入度一共有CA和DA两条边，因此沿着head指针能找到这两条边；同理，黄色的是出度指针，沿着tail指针就可以完成对出度的遍历。十字链表巧妙地节省了一张表。
  • 邻接多重表基于对邻接表的改进。由于其适用于无向图，所以不存在head和tail，但是依旧有两个指针。邻接多重表的节点结构与十字链表类似，并且同样用于存放边，不同的是每一个顶点后面紧跟着一个指针，并且每个节点还多出来了一个标志位用来存放是否被访问过。
  • 举例来讲，假设一个节点其中的顶点序号是2和5，那么2后面的指针会指向下一个出现了2的顶点（顶点顺序无所谓），而5后面的指针指向下一个出现了5的节点。顶点节点只保留一个指针，指向第一条连接此顶点的边。假设顶点序号是2，那么只要跟随每一个节点中编号为2的顶点后面的指针就可以完成对出入度的遍历。由于与十字链表类似我就不画图了。

图遍历

• 遍历就是从一个顶点出发，沿某一种规则访问全部的顶点，并且每个顶点只访问一次。
• 遍历主要分为两种
  • 深度优先遍历：
    • 就是一条路走到黑再回头。
    • 深度优先使用一个栈，对于每一个顶点先把它全部邻接的、未被访问的顶点都压入栈，然后从栈顶弹出一个节点作为接下来要访问的顶点。
    • 形象地说，当顶点有邻居1时会去访问邻居1，然后访问邻居1的邻居1，直到没有新的邻居再退回来访问邻居2。当栈被清空时遍历结束。
    • 深度优先遍历在诸如迷宫求解的时候应用较好，如果途中有环则需要记录已经访问过的顶点，否则不需要
  • 广度优先遍历：
    • 则是每条路都走一点
    • 广度优先则使用一个队列，对于每一个顶点先把它全部邻接的、未被访问的顶点都压入队列，然后从队列头弹出一个节点作为接下来要访问的顶点。
    • 形象地说，当顶点有邻居1时会去访问邻居1，然后访问邻居2，直到没有新的邻居再退回来访问邻居1的邻居1。当队列被清空时遍历结束。
    • 广度优先遍历适合浅层的关系，比如AI寻路（作为A算法的基础），比如通过社交关系网查询两个用户之间的距离。当然不使用队列和栈也可以，那样就要使用递归

图的最小生成树

• 作用：去除图中的环，同时使整体代价尽可能的小。
• 常用算法：
  • 普里姆算法（Prim）
    • 思想是将图划分为已连通和未连通部分，初始时已连通部分为任意顶点，在每一次迭代中计算每一个已连通部分的直接邻居到已连通部分的代价，然后选取代价最小的顶点连通，直至最后连通整张图。
    • 这只是思路，实现上并不是这么写的，有很多玄妙的部分，但是这里我懒得写了，因为要用到太多的辅助图。
  • 克鲁斯卡尔算法（Kruskal）
    • 则是首先将所有的边按照代价排序，并假设所有的顶点各自处于一个聚类中，每次迭代选取一条连接两个不同聚类的、代价最小的边（即连接同一个聚类的边即使代价更小也必须舍弃），然后将这两个聚类划拨为同一个聚类，直至最后只剩下一个聚类
• 最小生成树算法
  • 可以应用于网络布设中，使用最低成本达到连通所有节点的目的。
  • 但是，这种做法并不能保证任意两个节点之间的距离都是最短的，同样也容易造成星型布局，并使得上游节点遭受随之而来的带宽压力。但这种做法可以使总成本最低。
• 迪杰斯特拉算法
  • 如果需要求某一个顶点到所有顶点的最短路径，常用的算法是迪杰斯特拉算法
  • 迪杰斯特拉算法会维护一张表，记录该顶点到所有顶点的距离。
  • 初始时只把该顶点的直接邻居全加入并更新代价，从中选取代价最小的邻居作为新的起点，再把新的起点到它的所有的直接邻居的代价加上起点到它的代价与表中已有代价对比，选择代价较小的保留，比较结束后选择代价最小的留下，作为更新的起点，直至最后所有顶点都被留下。
  • 在计算机网络中有大量应用（OSPF协议），也就是在路由器估计网络拥塞状况并智能选择更空闲的路径。计网中还有一种RIP协议，你们学到了就知道了。