图

# 基本概念

图包括有向图和无向图，有向图就是从一个点到另一个点是有方向的，无向图就是点和点之间没有方向。<v,w> 是有序的（有向图），(x,y)是无序的（无向图）

# 基本术语

子图就是图的子集当有G(V,E)和g(v,e)两个图，当v属于V 且e属于E，那么g就是G的子图
无向完全图 对于无向图，若具有 n(n-1)/2 条边，就称为无向为完全图，
有向完全图 如果具有n(n-1)条弧，就称为有向完全图
稀疏图和稠密图 如果很少边或弧(e<nlog2n)的图称为稀疏图
权和网 边上的数字叫权
邻接点
度、入度和出度 就是和某一个点相连的边数，入度就是以这个点为顶点的弧，出度就是以这个点为出发点的弧

# 表示方法

# 邻接矩阵

就是使用一个矩阵来表示每个图的链接情况

# 邻接表

使用链表来表示图

# 逆邻接表

邻接表反映的是出度的情况，而逆邻接表反映的是入度情况

# 十字链表

邻接表与逆邻接表结合起来，表的结构入下

实际效果

# 邻接多重表

十字链表主要针对有向图，而临接多重表则适用于无向图

data：存储此顶点的数据
firstedge：指针域，用于指向同该顶点有直接关联的存储其他顶点的节点

mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历
ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标
ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点
jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点
info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权

# 图的遍历

# 深度优先搜索 DFS

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

# 无向图的深度优先搜索

# 有向图的深度优先搜索

# 广度优先搜索 BFS

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。

它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。

# 无向图的广度优先搜索

# 有向图的广度优先搜索

# 最小生成树

设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网，下面就引出了最小生成树的问题

# 普里姆算法（加点法）

# 克鲁斯卡尔算法（加边法）

# 最短路径

# 迪杰斯拉特算法（从某源点到其余各顶点的最短路径）

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

比如我们来求下面这个图

首先初始化dis数组，其中v1和v3，v5，v6是之间相连的，所以可以先写出距离

我们的顶点集T的初始化为：T={v1}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。

既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果：

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，**v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。**更新后的dis数组如下图：

然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图：

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下：

# 弗洛伊德算法（每一对顶点之间的最短路径）

弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

待补充

# 算法的时间复杂度

Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

图最短路径算法之弗洛伊德算法（Floyd） | Echo Blog (houbb.github.io) (opens new window)

# 拓扑排序

# AOV网

说白了就是后面的活动依赖前面的活动，比如，在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》

# 拓扑排序

就是把AOV网中所有的顶点排成一个线性的序列

# 关键路径

# AOE网

与AOV-网相对应的是AOE-网(Activity On Edge) ，即以边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常， AOE-网用于估算工程的完成时间

一个典型的AOE网如下

AOE网通常需要解决下面两个问题

估算完成整项工程需要多少时间
判断那些活动是影响工程进度的关键

# 四个描述量

# 计算

首先我们求出各个状态的最早时间

这个过程是要从源点开始向汇点顺推：

V1是源点，其最早开始时间是0。
V2、V3、V4最早时间分别是是6、4、5。
对于V5而言，V2到V5所花费时间是6+1=7，而V3到V5所花费时间是4+1=5。我们要按最大计，也就是V5最早时间是max{7,5}=7，按最大计是因为只有活动a4和a5同时完成了，才能到达V5状态。V3到V5需要5分钟，但是此时a4活动尚未完成（7分钟），所以都不能算到达V5，故而要按最大计。
V6只有从V4到达，所以V6的最早完成时间是（5+2=）7。
同理，V7最早完成时间是16。
对于V8而言，和V5处理方法一致。V8=max{V5+7,V6+4}={7+7,7+4}=14。
V9可算出是18。