图是由顶点（vertex）的有穷非空集合和顶点之间的边（edge）的集合组成。

图的定义与术语

无向图：

任意两个顶点之间的边没有方向，则称这条边为无向边，由无向边组成的图称为无向图。

无向边用无序偶对来表示。

有向图：

有向图：任意一条边都是有方向的，则这条边是有向边，也成为弧（Arc），这样的图称为有向图。

有向边通过有序偶<vi, vj>来表示。其中vi称为弧尾，vj称为弧头。

简单图：

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

上图就不是简单图。

完全图：

无向图中任意两个顶点之间都存在边，则称为无向完全图。n个顶点含有

条边。

有向图中任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

n个顶点含有 n ×（n - 1）条边。

网：

图中的边或弧带有相关的数叫做权（weight），这种带权的图通常称为网（Network）。

子图

灰色部分的图是左侧图的子图。

路径的长度是路径上边或弧的数目。

第一个顶点到最后一个顶点相同的路径称为回路或环。序列中除了第一个和最后一个顶点之外，其他顶点不重复出现的回路，称为简单回路或简单环。

序列中顶点不重复出现的路径称为简单路径。

连通图

图中任意两个顶点之间都有路径的图，称为连通图（Connected Graph）。无向图称为连通图；有向图称为强连通图。

图中的极大连通子图称为连通分量。无向图称为连通分量；有向图称为强连通分量。

需要注意的是：

必须是子图
子图必须是连通的
连通子图含有极大的顶点数，以及依附于这些顶点的所有边

生成树

连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的 n-1 条边。

由此可知，当含有n个顶点，但是边的条数小于n - 1时，则是非连通图；但是如果多于n-1条边，必定构成一个环。

但是含有n-1条表的图，不一定是生成树。

图2，图3是图1的最小生成树，但是图4尽管含有n-1条边的条件，但是它不是生成树。

有向树：

若一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。

一棵有向树的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

图2和图3是图1的两棵有向树（只是一种情况）其中由有向树的定义可知，B与A,C要在一起，F要和E,G在一起。

图的存储结构

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此不能通过使用内存中的物理位置来表示元素之间的关系。但是幸运的是前人已经提出了五种不同的解决办法。

邻接矩阵

图是由顶点和边或弧两部分组成的，为了方便，分别表示边（弧）和顶点。

因为顶点不分大小主次，所以用一个一维数组存储。

边（弧）是由两个顶点决定的，因此需要一个二位数组来存储。

于是提出了邻接矩阵（Adjacency Matrix）的概念。

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中的边或弧的信息。

图中有n个顶点，则二维邻接矩阵是一个n×n的方阵，

通过这个邻接矩阵可以知道以下信息：

判断任意两个顶点是否有边无边就非常容易
可以通过特定顶点在邻接矩阵中相应的行（列）的元素之和就可以判断此顶点的度。
求特定顶点的邻接点，只要遍历邻接矩阵中相应行元素，值为1就是邻接点。

对于有向图，同样也可以通过邻接矩阵，得到特定顶点的入度、出度以及邻接点等信息。

对于网来说，就需要额外的考虑与边相关的权值了。

相应的邻接矩阵计算公式如下：

对于n个顶点和e条边的无向网图的创建，时间复杂度为O(n＋n^2+e)其中对邻接矩阵的初始化耗费了O(n^2)的时间。

邻接表

对于上图来说，使用邻接矩阵来说就存在存储空间的极大浪费。

因此考虑对边或弧使用链式存储的方式来避免空间的浪费问题。

通过使用数组来存储顶点信息，使用链表的形式来存储边或弧的信息的存储方式，称作邻接表（Adjacency List）

邻接表的处理办法：

图中的顶点用一个一维数组存储，同时，每个数据元素还需要存储指向第一个邻接点的指针，以便查找该顶点的边信息。
每个顶点的所有邻接点构成一个线性表，由于邻接点的个数不确定，因此可以使用单向链表来存储，无向图称为顶点的边表，有向图称为顶点作为弧尾的出边表。

但是由于有向图是有方向的，以顶点为弧尾来存储边表，这样就可以得到一个以顶点为弧尾的出边表；同时可以顶点为弧头来存储边表，可以得到一个以顶点为弧头的入边表，称作有向图的逆邻接表。

对于带权值得网图：

创建邻接表得时间复杂度为O(n+e).

十字链表

对于有向图来说，当使用邻接表时，当查找了出度问题，若想要了解入度则必须重新遍历整个图才能知道。反之，逆邻接表也有同样问题。为了解决这个问题，提出了十字链表（Orthogonal List）。

重新定义顶点表：

firstin 表示入边表头指针，指向该顶点得入边表中第一个结点；firstout表示出边表头指针，指向该顶点得出边表中得第一个结点。

重定义得边表结点结构：

tailvex指弧起点在顶点表得下标，headvex表示弧终点在顶点表中得下标，headlink指入边表指针域，指向终点相同得下一条边，taillink是指边表指针域，指向起点相同得吓一条边。

十字链表中得实线很好理解，就是正常得邻接表。重点是虚线得理解：其中虚线指向得就是以此顶点为弧头的弧，即通过firstin指针域出发，指向以此顶点为弧头的弧，同时若有多条弧进入，则可以通过边表结点中的headline指针域作为指向同一终点的下一条边的特性作为跳板，指向其他入弧。

十字链表的好处：

由于十字链表把邻接表和逆邻接表整合在一起，这样可以很容易求得顶点的出度和入度。十字链表的创建和邻接表的时间复杂度是相同的，因此在有向图中，十字链表是非常好的数据结构模型。

邻接多重表

在无向图中，若更多关注的是顶点，则选择邻接表是一个不错的选择。但是若选择更多的关注的是边则选择邻接表就不是一个明智的选择了，因为当删除某条边后，则需要找到这条边表格结点进行操作，这就会变得麻烦不简洁。可以借鉴十字链表的特点，对边表结点的结构进行改变。

重新定义的边表结点的结构如下：

ivex和jvex表示与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是多重表结构。

邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个节点表示，而在邻接多重表中只有一个结点。

若删除某条边，只需让相应的指针指向空即可，完成删除操作。

边集数组

边集数组是由两个一维数组构成。一个存储顶点的信息；另一个存储边的信息，这个边数组每个数据元素由一条边的起点下标、终点下标和权值构成。

边集数组关注的是变得集合，在边集数组中若要查找某个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关操作。

图的遍历

深度优先遍历

深度优先遍历（Depth_First_Search），也称为深度优先搜索，简称为DFS。

深度优先遍历就是从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。

对于非连通图来说，只需对图中各个连通图依次进行深度优先遍历。

邻接矩阵的深度优先遍历代码操作：

对于邻接表的深度优先遍历：

两种不同存储结构的深度优先遍历算法，由于邻接矩阵要查找每个顶点，需要访问矩阵中的所有元素，因此时间复杂度为O(n^2)；而邻接表查找某个顶点，需要的时间取决于顶点和边的数量，时间复杂度为O(n+e),故当点多边少的图来说，邻接表存储结构的深度遍历时间效率更高。

广度优先遍历

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。

广度优先遍历，即将确定开始的顶点作为第一层，与之相邻的顶点作为第二层，以此类推，把全部顶点按照层次从新排列，然后对每一层进行遍历。

邻接矩阵的广度优先遍历：

时间复杂度为O(n^2)。

邻接表广度优先遍历：

时间复杂度为O(n+e)，因为程序中的while(p)模块只有在for() i=0时执行一次，然后就不再执行了，只剩for()执行n-1次结束。

由此可以看出深度优先遍历和广度优先遍历算法在时间复杂度上是一样的。

深度优先遍历更适合目标明确，为找到目标为目的的情况；而广度优先遍历更适合不断扩大范围时寻找最优解的情况

图的应用

有环图应用

最小生成树

把连通网图中由n个顶点和n-1条边组成的极小连通子图（也称为生成树），把其中最小代价（权值和）生成树称为最小生成树（Minimum Cost Spanning Tree）。

普里姆（Prim）算法

Prim算法的操作代码如下：

其中17~25行代码，循环当前的lowcost数组，找到最小权值min以及最小权值下标k。

28~35行代码，判断以k为顶点的邻接顶点的权值与lowcost数组中相应的权值大小，若小则替代lowcost数组中对应的权值，完成lowcost数组的更新；并将adjvex数组中相应下标的值改为k，完成adjvex数组的一次更新。

Prim算法的时间复杂度为o(n^2).

克鲁斯卡尔（Kruskal）算法

Prim算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。

也可以直接以变为目的去建立最小生成树，即直接寻找权值最小的边来构建最小生成树。但是要考虑是否形成环路。

因此用到了图存储结构中的边集数组，把边集数组按照权值的大小进行排序。

Kruskal算法的操作代码：

其中最重要的是19~25的查找代码，准确的算出，n和m的值。

函数Find的时间复杂度为O(loge)，因此，kruskal算法的时间复杂度为O(eloge)

对比：

kruskal算法主要是针对边来展开，边数少时效率会非常高，对稀疏图有很大优势；prim算法对于稠密图，即边非常多的情况会更好。

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，最短路径是指两顶点之间经过的边数最少路径；对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且称第一个点为源点，最后一个顶点为终点。

迪杰斯特拉（Dijkstra）算法

Dijkstra算法是一个基于之前最短路径长度递增的次序，从而产生最短路径的算法。

Dijkstra算法的操作代码：

其实这个Dijkstra算法的操作思路和最小生成树中的Prim算法是一样的。都是以v0相关的权值信息来初始化数组（具体数组的功能不同）。

final[]数组是用来标记是否已经遍历过某顶点了。P[]数组存储当前最小距离的顶点下标。D[]数组存储当前的最小路径。

17~23行代码，表示寻找数组D[]中的最小值min，并令最小值的下标令为k。

25~32行代码，表示遍历以vk为顶点的邻接边的权值，通过比较之前得到的最短路径min与vk邻接边w权值之和与数组D[w]相比较，将较小的值替换掉数组D[w]中的值。同时更新数组P[w]中的值为k。

Dijkstra算法的时间复杂度为O[n^2]。

Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题，它的局限性就是只能求取特定源点的最短路径。

弗洛伊德（Floyd）算法

Floyd算法的操作代码：

由于所求的是所有顶点到所有顶点的最短路径，因此数组P[]、D[]都是二维数组。

Floyd算法的核心就是，遍历数组D[]中的元素的权值，同时与以各个顶点为跳转点的路径权值做对比，将较小的一组值保留在数组D[]中，同时更改数组P[]中的值（P[v][w]=kk是跳转顶点下标）。

经过上述代码，可以得到如下数组矩阵：

通过这两个数组，可以求出所有顶点到所有顶点的最短路径权值。

求任意最短路径的操作代码：

通过代码可知，时间复杂度为O(n^3)

当面临求所有顶点到所有顶点的最短路径时，Floyd算法是个不错的选择。

无环图应用

拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，这称之为AOV网（Activity On Vertex Network）AOV网中的弧表示活动之间存在某种制约关系。

图G是一个具有n个顶点的有向图，V中的顶点序列v1,v2,……,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必须在顶点vj之前，则称这样的顶点序列为一个拓扑序列。拓扑序列不止一条

拓扑排序，就是对一个有向图构造拓扑序列的过程

若此网的全部顶点都被输出，则说明它是不存在环的的AOV网；若输出顶点少了，哪怕是少了一个，说明这个网中存在环 ,不是AOV网。

拓扑排序算法

对AOV网进行拓扑排序的基本思路是：

从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

由于在拓扑排序中，需要删除顶点，显然用邻接表会更加方便。

顶点表结构如下：

in是顶点的入度。

在算法中，引入了栈的概念，目的是为了把入度为0的顶点存储到栈中，目的是为了避免每次查找时都要遍历顶点表中有没有入度为0的顶点。

下面是拓扑排序算法的操作代码：

核心代码是12~23行代码，实现了入度为0的顶点压入栈中，以及输出打印栈中顶点，统计输出顶点数以判断是否会存在回环，同时解决了删除相应弧后邻接点的何去何从的问题。

此算法的时间复杂度为O(n+e)。9~~11行对各顶点的遍历的时间复杂度为O(n)，12~~23行代码，主要完成每个顶点按照一定的排序依次输出，换句话说就是，把每条弧依次删除后，从而得到了顶点的输出顺序（这只是自己的理解，不对之处还请指教）因次此段代码的时间复杂度为O(e)。因此，此算法的时间复杂度为O(n+e)。

关键路径

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称为AOE网（Activity On Edge Network）

在AOE网中，没有入边的顶点称为源点或始点，没有出边的顶点叫做汇点或终点。

AOE网和AOF网还是有区别的，从名字上就可以看出，AOE网更注重Edge;而AOF网更注重的是Vertex，它只描述活动之间的制约关系。

把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫做关键路径，在关键路径上的活动称为关键活动（弧）

关键路径算法

为了获得关键路径，首先要找到所有的关键活动。那么关键活动如何寻找呢？如下：

找到活动的最早开始时间以及最晚开始时间，若最早和最晚开始时间相等，则说明此活动没有空闲时间，可以作为关键活动；反之说明含有空闲时间，不能作为关键活动。

定义以下几个参数：

事件的最早发生时间etv(earliest time of vertex)：即顶点最早发生时间（）
事件的最晚发生时间ltv(latest time of vertex)：即顶点最晚发生时间（）
活动最早开工时间ete(earliest time of edge)：即弧的最早发生时间（在数值上，和事件最早发生时间etv相同）
活动最晚开工时间lte(latest time of edge)：即弧的最晚发生时间（在数值上，为下一事件开始之前）

可以通过etv\ltv求出ete\lte，通过判断ete是否等于lte来判断是否为关键活动。

改进后的拓扑排序算法操作代码：

主要的改进就是加粗的部分代码，它主要新增了一个栈stack2用来存储输出的拓扑序列。同时求出了etv的数组值。

可知，计算顶点事件最早发生时间公式如下:

因为etv一开始初始化为0，所以当k!=0时就如所给公式中一样了。

求取关键路径的操作代码：

主要时通过求拓扑序列，得到的拓扑路径stack2和事件最早开始时间etv来求取：事件最晚开始时间ltv；活动最早发生时间ete,活动最晚发生时间lte.然后通过判断ete与`lte是否相等来判断关键路活动，从而得到关键路径。

在实际工程中，可能存在多条关键路径，此时必须同时提高在几条关键路径上的关键活动速度。