o7.1.1 图的定义 图（Gragh）是一种网状数据结构，其形式化 定义如下： Gragh=(V,R)/由顶点集和顶点间的关系构成 V=x|xDataObject R=VR VR=|P(x,y)(x,y V)o无向图ACEFDB有向图ACEFDB无向网有向网15101120643边edge弧arc15101120643o完全图、稀疏图、稠 密图ACEFDB4阶完全图稀疏图ABDCABC 3阶完全图ABC3阶有向完全图o子图ACEFDBG1的子图H1G2的子图H2ACFE无向图G1有向图G2ACEFDBACEFDBo邻接点，度、入度和 出度对于无向图G1，通常采 用如下的方式描述：而对于有向图G2， 也有类似的描述ACEFDBACEFDBG1=V,E V=A,B,C,D,E,F E=(A,B),(A,C),(A,F), (B,D),(C,E),(D,E),( E,F)G2=V,E V=A,B,C,D,E,F E=, ,(E,D,相邻332 222(2，1)(0，2)(2，0)(1，1)(1，2)(1，1)若图中有n个顶点，e条边或弧，则图中的度 与边数的关系为：e=( )/2对于有向图，所有顶点的入度之和等于所有 顶点的出度之和o路径与回路，连通图ACEFDBACEFDBACEFDBABCo7.2.1 邻接矩阵表示法 图的邻接矩阵表示法既是图的顺序存储表 示法，又称为数组表示法。通常采用两 个数组来表示一个图：一个是用来存储 顶点信息的一维数组，另一个是用来存 储顶点之间的相邻关系的二维数组，该 二维数组被称为邻接矩阵。o不同的图以及它们的邻 接矩阵无向图G1有向图G2ACEFDBACEFDBo不同的图以及它们的邻 接矩阵无向网G1有向网G2ACEFDB15101120643ACEFDB15101120643邻接矩阵表示法C语言描述 #define MAX_VERTEX_NUM 20/*定义最多顶点个数*/ #define INFINITY 32768/*定义无穷大*/ /*描述图的类型，用枚举型类型来说明*/typedef enumDG,DN,UDG,UDNGraphKind; /*定义顶点数据类型*/typedef char VertexData; /*定义邻接矩阵中元素值(即边信息）的数据类型*/typedef int ArcNode; /*定义图的邻接矩阵类型：一个顶点信息的一维数组，一个邻 接矩阵、当前图中包含的顶点数、边数以及图类型（有向图 、有向网、无向图、无向网）*/typedef struct VertexData vertexMAX_VERTEX_NUM;ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vertexnum,arcnum;GraphKind kind; AdjMatrix;/图的邻接矩阵表示类型o7.2.2 邻接表表示法 图的邻接表表示法是图的链式存储表示法 ，比较适合存储稀疏图。在邻接表中， 首先建立一个表头结点表，该表的作用 类似于邻接矩阵中的顶点数组，表中存 储着所有顶点的信息。将该表中的每个 元素作为链表的头结点，对图中的每个 顶点建立一个单链表，该单链表中的结 点就是与此顶点关联的边对应的另一个 顶点信息以及边的信息（比如权值等） ，因此称这样的结点为边结点或者弧结 点。所以，图的邻接表表示也是由两部 分构成：表头结点表和边链表。o表头结点结构、边（弧）结点结构及实 例图的表头结点结构 边（弧）结点结构vexdata firstarcadjvex info nextarcAB CD01232 6 1 15 3 80 10ACDB151086o构造图的邻接表图中的邻接表，都包含一些什么信息呢？AB CD01232 61 15 3 80 10存放顶点信息的结点 数组，其每个结点相 当于单链表的头结点与顶点A相邻的 边结点链表ACDB151086o邻接表存储结构 /*定义最多顶点个数*/ #defined MAX_VERTEX_NUM 20 /*枚举图的种类*/ typedef enumDG,DN,UDG,UDNGraghKind; /*边结点类型*/ typedef struct ArcNodeint adjvex;/与表头顶点相邻的顶点的坐标值int info;/存储边的信息，如权值struct ArcNode *nextarc;/指点下一条边 （弧）的指针 ArcNode; /*定义表头结点数据类型*/ typedef strcut VertexNodechar data;ArcNode *firstarc; VertexNode; /*定义图的邻接表的基本状态信息*/ typedef struct /*存放图的顶点信息的表头结点 数组*/VertexNode vertexMAX_VERTEX_NODE ;/*具体图的顶点数和边（弧）数 */int vexnum,arcnum;GraghKind kind； AdjList；/定义一个基于邻接表的 图类型让我们来分析一下如何正确的使用邻接表存 储一个图。第一步：初始化。在该步骤中给出图的顶点数、边（ 弧）数以及表头结点组。AB CD0123例如对于下图，其初始的状态为： G.vexnum=4; G.arcnum=4;ACDB151086第二步：输入边结点信息，建立与各个表头结点邻接 的边结点链表。输入15,6,8,10后，分别建立4 个边结点结点，存储这些边结点信息，然后将这些边结 点插入到相应的表结点链表中。可是关键的问题是如何 根据输入的边结点信息找到正确的链接位置？利用一个定位函数（类似邻接数组的方法）， LocateVertex（G，v）得到顶点v在表头结点数组中的 位置即可。o7.3.1 深度优先搜索遍历DFS 图的深度优先搜索遍历是指按照深度方向 的搜索（纵向搜索），类似于树的先序 遍历。其基本思想是： （1）从图中某个顶点v0 出发，首先访问 v0 。 （2）找出刚访问过的顶点的第一个未被 访问过的邻接点，然后访问该顶点。以 该顶点为新顶点，重复此步骤，直到刚 访问的顶点没有未被访问的邻接点为止 。 （3）返回前一个访问过的且仍有未被访 问过的邻接点的顶点，找出该顶点的下 一个未被访问的邻接点，访问该顶点。 然后执行步骤（2）。o深度优先搜索遍历的递归算法 首先对v0 所在的连通子图的深度优先搜索 用递归算法实现： （1）访问出发点v0 。 （2）依次以v0 的未被访问的邻接点为出发 点，深度优先搜索图，直至图中所有与v0 有路径相通的顶点都被访问。 若是非连通图，则图中一定还有顶点未被访 问，需要从图中另选一个未被访问ideas 顶点作为起始点，重复上述深度优先搜索 过程，直到图中所有顶点均被访问过为止 。o7.3.2 广度优先搜索遍历BFS 图的深度优先搜索遍历是指按照广度方向的 搜索（横向搜索），类似于树的层次遍历 。其基本思想是： （1）从图中某个顶点v0 出发，首先访问v0 。 （2）依次访问v0 的各个未被访问的邻接点 。 （3）分别从这些邻接点出发，依次访问它 们的各个未被访问的邻接点。重复（3） 直到所有结点都被访问为止。分析：下图中从顶点A出发的深度优先搜索 和广度优先搜索遍历结果分别是什么？ ABCFEDHGI深度优先搜索：ABCFEGDHIADGHIEBCFABEGDHICF 广度优先搜索：ABDECGFHIAEDBGCHFIABEDCGFHIo7.4.1 图的连通性问题 1 无向图的连通分量 2 图中两个顶点之间的简单路径 3 生成树和最小生成树(1) Prim算法（2）Crusckal算法o7.4.1 图的连通性问题 1 无向图的连通分量ACEFDB2 两个顶点之间的简单路径 ABCFEDHGI从A到G的简单路径： A-B-E-G A-D-G 3 图的生成树和最小生成树ABCFEDHGI（1）生成树：一个连通图的生成树是指一个极小 连通子图，它含有图中的全部顶点。ABCFEDHGIABCFEDHGIABCFEDHGI最小生成树：在一个连通网的所有生成树中，各边的 代价之和最小的那棵生成树称为该连通网的最小代 价生成树，简称最小生成树（MST）ABCFEDHGI65 43866357ABCFEDHGI438663573. 3. 克鲁斯卡尔克鲁斯卡尔 ( (KruskalKruskal) ) 算法算法27(1) (1) 算法思想算法思想假设假设 N N = = ( (V V, , E E) ) 是一个连通网，则令最小生成树是一个连通网，则令最小生成树初始状态为只有初始状态为只有 n n 个顶点而无边的非连通图个顶点而无边的非连通图 T T = = ( (V V, , ) )，图中每个顶点自成一个连通分量。克鲁斯卡尔图中每个顶点自成一个连通分量。克鲁斯卡尔 ( (KruskalKruskal) )算法执行如下操作：算法执行如下操作：在在 E E 中选择代价最小的边，若该边依附的顶点落在中选择代价最小的边，若该边依附的顶点落在 T T 中不同的连通分量上，则将此边加入到中不同的连通分量上，则将此边加入到 T T 中，否则舍中，否则舍去此边而选择下一条代价最小的边。依此类推，直至去此边而选择下一条代价最小的边。依此类推，直至 T T 中所有顶点都在同一连通分量上为止。中所有顶点都在同一连通分量上为止。Crusckal算法过程演示：EFDCBA65 1 5246635EFDCBA12EFDCBA1EFDCBA123EFDCBA1243EFDCBA1 5243552. 2. 普里姆普里姆 (Prim) (Prim) 算法算法29(1) (1) 算法思想算法思想假设假设 N N = = ( ( V V, , E E ) ) 是一个连通网，是一个连通网，TETE 是是 V V 上最小上最小生成树边的集合。普里姆生成树边的集合。普里姆 (Prim) (Prim) 算法从算法从 U U = = u u0 0 ( ( u u0 0 V V ) )，TETE = = 开始。重复执行如下操作：开始。重复执行如下操作：在所有在所有 u u U U，v v V V- -U U 的边的边 ( (u u, , v v) ) E E 中寻找一中寻找一条代价最小的边条代价最小的边 ( (u u0 0, , v v0 0) ) 并入集合并入集合 TETE，同时同时 v v0 0并入并入 U U，直至直至 U U = = V V 为止。此时为止。此时 TETE 中必有中必有 n n-1 -1 条边，则条边，则 T T = = ( ( V V, , TETE ) ) 为为 N N 的最小生成树。的最小生成树。Prim算法过程演示：EFDCBA65 1 5246635FA1AF1B2FCA14C4D3EFDCBA65 1 5246635EFDCBA65 1 5246635EFDCBA65 1 5246635B2FCA14E5EFDCBA65 1 5246635B2FCA14E5EFDCBA65 1 5246635给定带权有向图给定带权有向图 G G = = ( (V V, , E