相对于树形结构的描述节点与节点之间的“层次”关系，图形结构是讨论两个顶点之间“连通与否”的关系。

如果为图形中连接两顶点的边填上权限值（也叫成本），就叫“网络”。

（“图”和“图形”是同一概念）

7.1.1 欧拉环与欧拉链

这里不得不说7桥问题，“是否有人在只经过每一座桥梁一次的情况下，把所有地方都走过一次而且回到原点”。

欧拉当时的方法就是以图形结构来进行分析的。他以顶点表示城市，以边表示桥梁，并定义了连接每个顶点的边数，该顶点就是度数。

最后的结论是：“当所有顶点的度数都为偶数时，才能从某顶点出发，经过每条边一次，再回到起点”又因为每个顶点的度数都是奇数，所以欧拉所思考的问题是不可能发生的。

这就是“欧拉环”（Eulerian Cycle）理论。

而对应的条件改成从某顶点出发，经过每条边一次，不一定要回到起点，即只允许其中两个顶点的度数为奇数，其余则必须全部为偶数，符合这样的结果称为欧拉链（Eulerian Chain）

7.1.2图形的定义

图是由“顶点”和“边”所组成的集合，有无向图与有向图两种。

7.1.3 无向图

无向图（Graph）是一种边没有方向的图，即同边的两个顶点没有次序关系。

7.1.4 有向图

有向图（Digraph）是一种每一条边都可使用有序对

7.2.1 邻接矩阵法

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。

无向图的邻接矩阵一定是对称的，而对角线一定为 0。而有向图的邻接矩阵不一定对称。

优点：

借着矩阵的运算有许多特别的应用，要在图中加入新边时，这个表示法的插入与删除操作相当简易。

缺点：

稀疏矩阵有空间上的浪费问题，如果要计算所有顶点的度数，其时间复杂度为

7.2.2 邻接表法

邻接表法（Adjacency List）就是将一个 n 行的邻接矩阵表示成 n 个链表，这种做法比邻接矩阵更节省空间，而计算所有顶点的度数时，其时间复杂度为

缺点：如有新边加入图中或从图中删除边时，就要修改相关的连接，比较麻烦费时。

7.2.3 邻接复合链表法

邻接复合链表是处理无向图的另一种方法，其节点用于存储边的数据。

M：用于记录该边是否是被找过的字段，此字段为一个位（比特）。

V1和V2：所记录的边的起点和终点。

LINK1：在尚有其他顶点与V1相连的情况下，此字段会指向下一个与V1相连的边节点，如果已经没有任何顶点与V1相连，就指向None。

LINK2：在尚有其他顶点与V2相连的情况下，此字段会指向下一个与V2相连的边节点，如果已经没有任何顶点与V2相连，就指向None。

7.2.4 索引表格法

索引表格表示法是一种用一维数组来按序存储与各顶点相邻的所有顶点，并建立索引表格来记录各顶点在此一维数组中第一各与该顶点相邻的位置。

树的遍历目的是访问树的每一个节点一次，可用的方法有中序法、前序法和后序法3种。

而图的遍历的方法有两种：“深度优先遍历”和“广度优先遍历”，也称为“深度优先搜索”和“广度优先搜索”。

7.3.1 深度优先遍历法

深度优先遍历的方式有点类似于前序遍历。

深度优先搜索，是图论中的经典算法。其利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

1. 首先从一个未走到过的顶点作为起始顶点，比如1号顶点作为起点。
2. 沿1号顶点的边去尝试访问其它未走到过的顶点，首先发现2号顶点还没有走到过，于是来到了2号顶点。
3. 再以2号顶点作为出发点继续尝试访问其它未走到过的顶点，这样又来到了4号顶点。
4. 再以4号顶点作为出发点继续尝试访问其它未走到过的顶点。
5. 但是，此时沿4号顶点的边，已经不能访问到其它未走到过的顶点了，所以需要返回到2号顶点。
6. 返回到2号顶点后，发现沿2号顶点的边也不能再访问到其它未走到过的顶点。此时又会来到3号顶点（2->1->3），再以3号顶点作为出发点继续访问其它未走到过的顶点，于是又来到了5号顶点。
7. 至此，所有顶点我们都走到过了，遍历结束

1. 首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；
2. 当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直到所有的顶点都被访问过。

“一路走到头，不碰壁不回头”。

7.3.2 广度优先遍历法

所谓广度，就是一层一层的，向下遍历，层层堵截，还是这幅图，我们如果要是广度优先遍历的话，我们的结果是

广度优先搜索的思想：

a.访问顶点

b.访问vi 的所有未被访问的邻接点

c.依次从这些邻接点（在步骤 b 中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；

• 两种搜索优缺点对比：

1、深度优先算法占内存少但速度较慢，广度优先算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。

2、深度优先与广度优先的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。

3、这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度优先下一次扩展的是本次扩展出来的子节点中的一个，而广度优先扩展的则是本次扩展的节点的兄弟点。在具体实现上为了提高效率,所以采用了不同的数据结构。

若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。

7.4.1 DFS生成树和BFS生成树

一棵生成树也可以利用深度优先搜索法（DFS）与广度优先搜索法（BFS）来产生，所得到的生成树则称为深度优先生成树（DFS生成树）与广度优先生成树（BFS生成树）。

7.4.2 最小生成树

G=(V,E)为连通无向图，V为结点的集合，E为结点的可能连接边

对每条边(u ,v)都赋予权重W(u ,v)

目标：找到一个无环子集T, 既能将所有结点连接起来，又具有最小权重。

T是由G生成的树，并把这种问题叫做最小生成树问题。

Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。

用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。

最常用的路径算法有：Dijkstra算法

Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

活动网络可以用来描述生产计划，施工过程，生产流程等工程中个子工程的安排问题，活动网络可以分为两种：AOV网络和AOE网络。

AOV网络就是用顶点表示活动（Activity On Vertices）的这样一个有向图，记作AOV网络。

在AOV网络中，有向边的起点标表示的活动必须在终点表示的活动之前完成。而且AOV网络中的前驱与后继关系有传递性；此外任何活动不得以它自己为前驱，也就是说这种关系具有反自反性，因此，AOV网络中不能出现有向回路，即AOV网络是一个有向无环图。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在（回路）的AOV网；如果输出顶点少了，哪怕是少了一个，也说明这个网存在环路，不是AOV网。

AOE 网络是一个带权的有向无环图。其中用顶点表示事件，弧表示活动，权值表示两个活动持续的时间。AOE网是以边表示活动网络。

关键路径是指在AOE网中从源点到汇点路径最长的路径。这里的路径长度是指路径上各个活动持续时间之和。在AOE网中，有些活动是可以并行执行的，关键路径其实就是完成工程的最短时间所经过的路径。关键路径上的活动称为关键活动。

1. 事件

ve(i)=Max{ve(k)+(<k,j>∈)|<k,j>T,1≤i≤n−1}

ve(i)=Max{ve(k)+(<k,j>∈)|<k,j>T,1≤i≤n−1}

其中T是所有以第i个顶点为弧头的弧的集合，dut(<k,j>)dut(<k,j>)表示弧<k,j><k,j>对应的活动的持续时间。

2. 事件

vl(i)=Min{vl(k)−dut(<i,k>)|<i,k>∈S,0≤i≤n−2}

vl(i)=Min{vl(k)−dut(<i,k>)|<i,k>∈S,0≤i≤n−2}

其中S是所有以第i个顶点为弧尾的弧的集合，dut(<i,k>)dut(<i,k>)表示弧<i,k><i,k>对应的活动的持续时间。

3.活动

4.活动

5.活动

当e(i)=l(i)时，对应的活动

求AOE网的关键路径的算法：

1. 对AOE网中的顶点进行拓扑排序，如果得到的拓扑序列顶点个数小于网中顶点数，则说明网中有环存在，不能求关键路径，终止算法。否则，从源点v0v0开始，求出各个顶点的最早发生时间ve(i)。

2. 从汇点

3. 由各顶点的最早发生时间ve(i)和最晚发生时间vl(i)，求出每个活动aiai的最早开始时间e(i)和最晚开始时间l(i)。

4. 找出所有满足条件e(i)=l(i)的活动

求AOE网的关键路径的算法：

1. 对AOE网中的顶点进行拓扑排序，如果得到的拓扑序列顶点个数小于网中顶点数，则说明网中有环存在，不能求关键路径，终止算法。否则，从源点v0v0开始，求出各个顶点的最早发生时间ve(i)。

2. 从汇点vnvn出发vl(n-1)=ve(n-1)，按照逆拓扑序列求其他顶点的最晚发生时间vl(i)。

3. 由各顶点的最早发生时间ve(i)和最晚发生时间vl(i)，求出每个活动aiai的最早开始时间e(i)和最晚开始时间l(i)。

4. 找出所有满足条件e(i)=l(i)的活动

---

如果对你有帮助欢迎来大家来QQ群吐槽：883610200

http://qm.qq.com/cgi-bin/qm/qr?k=YQXvDYlhmKLxw2ZIeaXP43PGwgFQFWCl (二维码自动识别)

——本文原创版权归知乎SwordsS（剑星）所有