数据结构学习（五）

                                  第六章 图

                                            2009-8-15

（1）图(graph)：

图是比树更复杂的一种非线性数据结构。图中的每个结点都可以和其他任何结点相连接。图的应用非常广泛，一方面是因为很多实际问题和图有关，例如通信线路，交通运输，集成电路分布图（莫非网络表就是这样实现的？？？）等等；另一方面还有很多实际问题可以间接的用图来表示，处理起来比较方便，例如工程进度的安排。

 

（2）图的定义和基本术语：

     图G由V(G)和E(G)两个集合组成，记成G=(V,E)，其中V是顶点(vertex)的非空集,E是边(edge)的集合，特殊情况下，E可以是空集（不得不佩服，别人的这个模建的，叫我想上一年，也不知道能不能想出用集合来表示图这种东西）。

     无向图：对于一个图G，若边集合E(G)为无向边的集合，则称该图为无向图。相对应的就是有向图了，定义不多说了，猜也能猜出来了。这里有的问题就出来了，有向图的话，从顶点1到顶点4和从顶点4到顶点1那就是两条不同的边了，图中可以同时有这两条边哦。

     完全图：首先要是无向图，其次要两两顶点之间都有一条边。

     权和网络：有些图，对应的边有一个相应的权值（这个好，就好像公路一样，每两个城市之间的公路的长度就是权值）。

     子图：一个图的子集，理解好理解，怎么描述好呢？我不太清楚了。

     顶点的度：每个顶点的边数。对有向图，则有入度和出度，入度和出度，这是什么意思应该能猜到吧。

     路径：在一个图中从顶点1 到顶点 2，中间会经过些顶点，这整个的顶点序列就是一条路径。有向图，路径的方向可是有一定限制的。

     路径长度：对无权图（不是无向图哦）路径长度指经过的顶点的数目；有权图，则还要乘上各自的权值。

     简单路径：路径经过的每个顶点不超过一次（这么说来简单路径不是指最短的那条了）。

     环路：从顶点出发，最后回到该顶点（按照简单路径的定义，环路就没有简单路径了，HOHO）。

     连通：在无向图中，若两顶点之间有路径，则它们是连通的。如果图中任意一对顶点都是连通的，则称此图是连通的(这定义虽然和数学里面的不同，不过证明下的话，估计这两个定义是等价的)。

连通分量：在非连通图中，连通的部分叫连通分量（我还以为是连通图中连通的各个部分。。。。）。

强连通图：有向图中，顶点到顶点都有路径（包括来回哦），则成为强连通。

强连通分量：非强连通图中的强连通的部分叫强连通分量（有点绕）。

定义好多，其实却很好理解。

 

（3）图的存储方式：

邻接矩阵：是表示顶点之间相邻关系的矩阵。假设顶点数为N，建个N*N的方阵，方阵里面的各个元素的值，根据各顶点之间是否有边来赋值，有边赋1，无边赋0。这样的话，所有的无向图的邻接矩阵都是对称的。如果各边带权的话，也可以用邻接矩阵表示（怎么表示，你应该想到了吧）。

邻接表：是图的一种链式存储结构。对图中的每个顶点建立起一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边。邻接表中每个表结点均由两个域组成，其一是邻接点域，其二是链域。要注意哦，对无向图来说，链接表中表结点的数目是边数的两倍，有向图中，边数和表结点书相同。（这个很好理解啦）。

对一个图，邻接矩阵是唯一的，邻接表可不是唯一的（不知道为什么吗？查书去）。

（4）图的遍历：

从图中某个顶点出发，沿着一些边沿访问图中所有的顶点，且使每个顶点仅访问一次，这个过程叫遍历。图的遍历很复杂，常用方法如下：

深度优先法（depth first search DFS）：

基本思想是：从某指定的初试顶点1出发，访问相邻的任意连接的结点2，在从结点2出发，访问未曾访问过的和2连接着的顶点3，一直这样，直到没有未曾访问过的结点i，再回溯到i-1结点，再这样不停的回溯。

广度优先法（breadth first search BFS）:相对应与深度优先法，这里就不写了。不过广度优先搜索不是递归过程，不能采用递归形式的算法，深度优先法可以。其算法实现挺麻烦的，想了解的可以查查书（都比较懒了，代码都不抄了。。。）。

（5）最小生成树：在一个无向连通图中，如果取它的全部顶点和一部分边构成一个子图G’。则称E(G’)是原图的生成树。生成树的特点有两个：多一条边，构成环路；少一条边，就是非连通图。N个顶点的无向连通图生成树，有N的N-2次幂个生成树。对于带权的连通图，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且，将权最小的生成树称为最小生成树。

（6）生成最小生成树的算法主要有两个：既普里姆算法和克鲁斯卡尔算法。

算法内容很多，不过原理都挺简单的，看下就会明白的，代码长，我就不抄了。

（7）最短路径：从一顶点到另一顶点，路径上各边的权值之和最小。这里又有个算法 狄克斯特拉算法，也很好理解，这里我简单的描述下，描述的不对，别见怪啊，假设一个图有N个顶点，选定一个初试顶点1，以后陆续的将已求的最短路径的顶点加入到表中，直到所有顶点。详细内容和代码我就不抄了。

（8）拓补排序（topological sort）是有向图的一种重要运算。这里涉及到AOV网络这个概念，不好描述，能用图的话会好描述点，看下书，很快就会明白。为什么需要拓补排序，这里就不再介绍这个理由了。

 首先要知道的一点，对一个AOV网络，拓补排序的结果不止一个。

 其次要知道的是 拓补排序的方法：第一步 在网络中选取一个没有前驱的顶点，输出该顶点；第二步 从网络中删去该顶点和以该顶点发出的所有有向边；第三步 重复前面的两个步骤，直到所有顶点被输出。要进行拓补排序，必须用链接表的方式存储图。拓补排序的算法，这里不抄了。

（9）关键路径法：这是管理科学中的一个重要方法，也称为统筹法。这个，我没怎么看，今天就到此为止吧。